算法设计与分析实验三

算法设计与分析实验三（共8篇）

1.算法设计与分析实验三 篇一

计算机工程学院

实验报告书

课程名：《

操作系统原理A

》

题

目：

虚拟存储器管理

页面置换算法模拟实验

班

级：

学

号：

姓

名：

评语：

成绩：

指导教师：

批阅时间：

****年**月**日

一、实验目的与要求

1.目的：

请求页式虚存管理是常用的虚拟存储管理方案之一。通过请求页式虚存管理中对页面置换算法的模拟，有助于理解虚拟存储技术的特点，并加深对请求页式虚存管理的页面调度算法的理解。

2.要求：

本实验要求使用C语言编程模拟一个拥有若干个虚页的进程在给定的若干个实页中运行、并在缺页中断发生时分别使用FIFO和LRU算法进行页面置换的情形。其中虚页的个数可以事先给定（例如10个），对这些虚页访问的页地址流（其长度可以事先给定，例如20次虚页访问）可以由程序随机产生，也可以事先保存在文件中。要求程序运行时屏幕能显示出置换过程中的状态信息并输出访问结束时的页面命中率。程序应允许通过为该进程分配不同的实页数，来比较两种置换算法的稳定性。

二、实验说明

1．设计中虚页和实页的表示

本设计利用C语言的结构体来描述虚页和实页的结构。

pn

pfn

time

pn

pfn

next

虚页结构

实页结构

在虚页结构中，pn代表虚页号，因为共10个虚页，所以pn的取值范围是0—9。pfn代表实页号，当一虚页未装入实页时，此项值为-1；当该虚页已装入某一实页时，此项值为所装入的实页的实页号pfn。time项在FIFO算法中不使用，在LRU中用来存放对该虚页的最近访问时间。

在实页结构中中，pn代表虚页号，表示pn所代表的虚页目前正放在此实页中。pfn代表实页号，取值范围（0—n-1）由动态指派的实页数n所决定。next是一个指向实页结构体的指针，用于多个实页以链表形式组织起来，关于实页链表的组织详见下面第4点。

2．关于缺页次数的统计

为计算命中率，需要统计在20次的虚页访问中命中的次数。为此，程序应设置一个计数器count，来统计虚页命中发生的次数。每当所访问的虚页的pfn项值不为-1，表示此虚页已被装入某实页内，此虚页被命中，count加1。最终命中率=count/20*100%。

3．LRU算法中“最近最久未用”页面的确定

为了能找到“最近最久未用”的虚页面，程序中可引入一个时间计数器countime，每当要访问一个虚页面时，countime的值加1，然后将所要访问的虚页的time项值设置为增值后的当前countime值，表示该虚页的最后一次被访问时间。当LRU算法需要置换时，从所有已分配实页的虚页中找出time值为最小的虚页就是“最近最久未用”的虚页面，应该将它置换出去。

4．算法中实页的组织

因为能分配的实页数n是在程序运行时由用户动态指派的，所以应使用链表组织动态产生的多个实页。为了调度算法实现的方便，可以考虑引入free和busy两个链表：free链表用于组织未分配出去的实页，首指针为free_head，初始时n个实页都处于free链表中；busy链表用于组织已分配出去的实页，首指针为busy_head，尾指针为busy_tail，初始值都为null。当所要访问的一个虚页不在实页中时，将产生缺页中断。此时若free链表不为空，就取下链表首指针所指的实页，并分配给该虚页。若free链表为空，则说明n个实页已全部分配出去，此时应进行页面置换：对于FIFO算法要将busy_head

所指的实页从busy链表中取下，分配给该虚页，然后再将该实页插入到busy链表尾部；对于LRU算法则要从所有已分配实页的虚页中找出time值为最小的虚页，将该虚页从装载它的那个实页中置换出去，并在该实页中装入当前正要访问的虚页。

三、程序流程图

四、主要程序清单

#include

#include

/*全局变量*/

int

mSIZE;

/*物理块数*/

int

pSIZE;

/*页面号引用串个数*/

static

int

memery[10]={0};

/*物理块中的页号*/

static

int

page[100]={0};

/*页面号引用串*/

static

int

temp[100][10]={0};

/*辅助数组*/

/*置换算法函数*/

void

FIFO();

void

LRU();

void

OPT();

/*辅助函数*/

void

print(unsigned

int

t);

void

designBy();

void

download();

void

mDelay(unsigned

int

Delay);

/*主函数*/

void

main()

{

int

i,k,code;

printf(“请输入物理块的个数(M<=10)：“);

scanf(“%d“,&mSIZE);

printf(“请输入页面号引用串的个数(P<=100)：“);

scanf(“%d“,&pSIZE);

puts(“请依次输入页面号引用串(连续输入，无需隔开)：“);

for(i=0;i

scanf(“%1d“,&page[i]);

download();

do

{

puts(“输入的页面号引用串为：“);

for(k=0;k<=(pSIZE-1)/20;k++)

{

for(i=20*k;(i

{

if(((i+1)%20==0)||(((i+1)%20)&&(i==pSIZE-1)))

printf(“%d＼n“,page[i]);

else

printf(“%d

“,page[i]);

}

}

printf(“*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*＼n“);

printf(“*

请选择页面置换算法：＼t＼t＼t

*＼n“);

printf(“*

-----------------------------------------*＼n“);

printf(“*

1.先进先出(FIFO)

2.最近最久未使用(LRU)

*＼n“);

printf(“*

3.退出

*＼n“);

printf(“*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*＼n“);

printf(“请选择操作：[

]＼b＼b“);

scanf(“%d“,&code);

switch(code)

{

case

1:

FIFO();

break;

case

2:

LRU();

break;

case

3:

OPT();

break;

case

4:

system(“cls“);

//system(“color

0A“);

exit(0);

default:

printf(“输入错误，请重新输入：“);

}

printf(“按任意键重新选择置换算法：>>>“);

getchar();

}

while

(code!=4);

getchar();

}

/*载入数据*/

void

download()

{

printf(“＼nFinish.＼n载入成功!“);

}

/*设置延迟*/

void

mDelay(unsigned

int

Delay)

{

unsigned

int

i;

for(;Delay>0;Delay--)

{

for(i=0;i<124;i++)

{

printf(“

＼b“);

}

}

}

/*显示设计者信息*/

void

print(unsigned

int

t)

{

int

i,j,k,l;

int

flag;

for(k=0;k<=(pSIZE-1)/20;k++)

{

for(i=20*k;(i

{

if(((i+1)%20==0)||(((i+1)%20)&&(i==pSIZE-1)))

printf(“%d＼n“,page[i]);

else

printf(“%d

“,page[i]);

}

for(j=0;j

{

for(i=20*k;(i{

if(i>=j)

printf(“

|%d|“,temp[i][j]);

else

printf(“

|

|“);

}

for(i=mSIZE+20*k;(i

{

for(flag=0,l=0;l

if(temp[i][l]==temp[i-1][l])

flag++;

if(flag==mSIZE)/*页面在物理块中*/

printf(“

“);

else

printf(“

|%d|“,temp[i][j]);

}

/*每行显示20个*/

if(i%20==0)

continue;

printf(“＼n“);

}

}

printf(“----------------------------------------＼n“);

printf(“缺页次数：%d＼t＼t“,t+mSIZE);

printf(“缺页率：%d/%d＼n“,t+mSIZE,pSIZE);

printf(“置换次数：%d＼t＼t“,t);

printf(“访问命中率：%d%%＼n“,(pSIZE-(t+mSIZE))*100/pSIZE);

printf(“----------------------------------------＼n“);

}

/*计算过程延迟*/

void

compute()

{

int

i;

printf(“正在进行相关计算，请稍候“);

for(i=0;i++<30;printf(“＼b“));

for(i=0;i++<30;printf(“

“));

for(i=0;i++<30;printf(“＼b“));

}

/*先进先出页面置换算法*/

void

FIFO()

{

int

memery[10]={0};

int

time[10]={0};

/*记录进入物理块的时间*/

int

i,j,k,m;

int

max=0;

/*记录换出页*/

int

count=0;

/*记录置换次数*/

/*前mSIZE个数直接放入*/

for(i=0;i

{

memery[i]=page[i];

time[i]=i;

for(j=0;j

temp[i][j]=memery[j];

}

for(i=mSIZE;i

{

/*判断新页面号是否在物理块中*/

for(j=0,k=0;j

{

if(memery[j]!=page[i])

k++;

}

if(k==mSIZE)

/*如果不在物理块中*/

{

count++;

/*计算换出页*/

max=time[0]

for(m=2;m

if(time[m]

max=m;

memery[max]=page[i];

time[max]=i;

/*记录该页进入物理块的时间*/

for(j=0;j

temp[i][j]=memery[j];

}

else

{

for(j=0;j

temp[i][j]=memery[j];

}

}

compute();

print(count);

}

/*最近最久未使用置换算法*/

void

LRU()

{

int

memery[10]={0};

int

flag[10]={0};

/*记录页面的访问时间*/

int

i,j,k,m;

int

max=0;

/*记录换出页*/

int

count=0;

/*记录置换次数*/

/*前mSIZE个数直接放入*/

for(i=0;i

{

memery[i]=page[i];

flag[i]=i;

for(j=0;j

temp[i][j]=memery[j];

}

for(i=mSIZE;i

{

/*判断新页面号是否在物理块中*/

for(j=0,k=0;j

{

if(memery[j]!=page[i])

k++;

else

flag[j]=i;

/*刷新该页的访问时间*/

}

if(k==mSIZE)

/*如果不在物理块中*/

{

count++;

/*计算换出页*/

max=flag[0]

for(m=2;m

if(flag[m]

max=m;

memery[max]=page[i];

flag[max]=i;

/*记录该页的访问时间*/

for(j=0;j

temp[i][j]=memery[j];

}

else

{

for(j=0;j

temp[i][j]=memery[j];

}

}

compute();

print(count);

}

/*最佳置换算法*/

void

OPT()

{

int

memery[10]={0};

int

next[10]={0};

/*记录下一次访问时间*/

int

i,j,k,l,m;

int

max;

/*记录换出页*/

int

count=0;

/*记录置换次数*/

/*前mSIZE个数直接放入*/

for(i=0;i

{

memery[i]=page[i];

for(j=0;j

temp[i][j]=memery[j];

}

for(i=mSIZE;i

{

/*判断新页面号是否在物理块中*/

for(j=0,k=0;j

{

if(memery[j]!=page[i])

k++;

}

if(k==mSIZE)

/*如果不在物理块中*/

{

count++;

/*得到物理快中各页下一次访问时间*/

for(m=0;m

{

for(l=i+1;l

if(memery[m]==page[l])

break;

next[m]=l;

}

/*计算换出页*/

max=next[0]>=next[1]?0:1;

for(m=2;m

if(next[m]>next[max])

max=m;

/*下一次访问时间都为pSIZE,则置换物理块中第一个*/

memery[max]=page[i];

for(j=0;j

temp[i][j]=memery[j];

}

}

if(k==mSIZE)

/*如果不在物理块中*/

{

count++;

/*得到物理快中各页下一次访问时间*/

for(m=0;m

{

for(l=i+1;l

if(memery[m]==page[l])

break;

next[m]=l;

}

/*计算换出页*/

max=next[0]>=next[1]?0:1;

for(m=2;m

if(next[m]>next[max])

max=m;

/*下一次访问时间都为pSIZE,则置换物理块中第一个*/

memery[max]=page[i];

for(j=0;j

temp[i][j]=memery[j];

}

}

五、程序运行结果

①FIFO

②LRU

六、实验体会

在做该次作业的时候，通过对课本相关内容的温习，以及对自己在网络上找到的一些资源的了解。我对操作系统中页面调度的算法有了很大程度的了解，加深了对课程上知识的理解，也懂得了如何在程序中将这些算法实现，在程序中基本上实现了所要求的算法以及相关的性能分析，基本上实现了课程的要求。

这次作业也暴露了自己在某些方面的不足之处，自己的语言功底有一定的不足，以及一开始对某个算法不够熟悉，将算法实现设计的比较复杂，此次自己的程序存在一些思想上的漏洞，反映出此次程序设计的要求有了一定的限制。

2.算法设计与分析实验三 篇二

1 回溯算法描述

回溯算法也叫试探法,它是一种系统地搜索问题的解的方法。回溯算法是搜索算法中的一种控制策略[2]。回溯算法解决问题的一般步骤是,首先针对所给问题,定义问题的解空间,它至少包含问题的一个(最优)解,然后确定易于搜索的解空间结构,使得能用回溯法方便地搜索整个解空间,最后以深度优先的方式搜索解空间,并且在搜索过程中用剪枝函数避免无效搜索。回溯算法在用来求问题的所有解时,要回溯到根,同时要求满足根结点的所有子树都已被搜索遍才结束。回溯算法并不要求得到最优解,只要得到符合条件的解即可。这种以深度优先的方式系统地搜索问题的解的算法称为回溯算法。其算法思想为:

2 排课系统设计与实现

2.1 系统需求分析

本系统是在教师接到教学任务后,有实验室使用需求的教师能够通过实验室排课系统选择申请使用实验室,专业性强的课程直接申请使用相关专业的实验室(要求实验室类别中标明所属专业或公共实验室),非专业课程选择公共实验室,在公共实验室不够,而专业实验室有空的情况下可以选择专业实验室(专业实验室是在满足公共实验室的要求下添加相关的软硬件),然后由系统统一排课,必要时由实验室排课管理人员手动调整。如果用户需要调课或额外添加上机则可以查看实验室使用情况后选择申请使用实验室。

2.2 系统功能模块划分

从系统应用的角度来看,本系统用户主要有:学生、教师、系统管理员、实验室管理员,要求能够实现如下功能:实验室排课、教师/班级/实验室课表查询、实验室使用申请、实验室使用情况分析等几个功能模块,如图1所示:

(1)基本信息检索模块:该模块提供给任意用户进行的信息检索模块,即教师/班级/实验室课表查询。使用该模块能够根据用户输入(教师姓名、班级名称、实验室门牌号等)信息来判断,并调出相关课表。同时也为教师用户再次申请使用实验室时了解实验室信息提供帮助。

(2)用户登录模块:该模块提供了根据用户登录信息及用户角色(教师、实验室排课管理员、部门领导)进行判断,从而进入实验室使用申请模块或管理模块。

(3)实验室使用申请模块:该模块主要提供教师用户需要使用实验室时申请备案用的,教师用户调出自己的教学任务表,添加特殊需求并提交申请即可。只有申请使用实验室的教学任务,方可安排到实验室;同时有效帮助用户查看实验室信息,随时了解所需实验室的使用情况,并选择所需的实验室。

(4)管理模块:该模块主要由实验室排课管理员和部门领导使用,通过该模块实验室排课管理员可以随时根据实际情况对教学任务、实验室信息、用户信息、实验室排课信息进行管理;实验室排课管理实现了排课的自动生成和手动调整;另外管理员可以通过分析模块得出各个实验室利用率,综合得出各个实验室管理人员的工作量,为年底实验室管理人员工作核算提供依据。

排课的具体操作是教师用户登录后有实验室使用需求的教师调入自己的教学任务,并根据教学任务选择相关实验室,同时添加备注(特殊情况下时间地点的要求),这样教学任务表就可以初步得到实验室所涉及的课程、班级及教师的一个汇总表,只需选择相应的时间即可。管理员用户登录后查看教学任务表,并根据教师的备注信息重新设置教学任务优先级,否则默认按照课程属性优先级排课,最后按照优先级由高到低排序生成教学任务待排课表,特殊情况可手动修改。具体操作流程如图2所示:

由于本系统仅用于实现实验室排课、课表查询和实验室管理工作量分析使用,因此数据库设计相对较简单。主要涉及到如下几个关系模式。

实验室信息表:实验室门牌号、教学楼号、可用机位、类别(软件、多媒体、应用、网络、公共实验室)、实验室管理员工号、备注(软硬件配置)。

教学任务表:教学任务编号(自增序列)、教师工号、课程编号、班级编号、开始周次、结束周次、周课次、优先级、实验室类别。

课程信息表:课程编号、课程名称、课时数、课程属性、所属专业。

班级信息表:班级编号、班级名称、班级人数、所属专业、班主任编号。

实验室排课表:排课编号(自增序列)、实验室门牌号、教学任务编号、上课周节(每两课时算一次课,该字段有两位数组成,第一位表示周几,第二位表示第几次课)。

系统用户表:工号、姓名、角色(教师、实验室管理员、系统管理员)。

专业信息表:专业编号、专业名称、所属系部。

它们之间的关系如图3所示:

2.3 排课算法

2.3.1 约束规则

作为学院的专任教师,一定是熟悉各个实验室的基本配置,尤其是专业实验室配置情况。因此在实验室安排方面让专任教师根据自己的需求选择地点是最简单的了。需要注意的是教师在申请使用实验室时注意以下几个约束规则:

(1)同一教室同一时间只能容纳一个教学任务;

(2)同一教师同一时间只能在一个实验室教学;

(3)为了保证教学效果,实验室不支持大班授课;

然后根据教师申请汇总表进行排课,在进行实验室安排时,有两个排序条件:

(1)软件要求。有些软件运行对机器要求比较高,这些软件,只在特定实验室进行了安装,与这软件对应的课程,也就只能安排在相应实验室内;

(2)课程属性。课程属性分为核心课程、专业课程、专业基础课程与公共基础课程,首先安排核心课程,最后安排公共基础课程。

以上两个条件,如相互冲突时,优先考虑第一个条件。

2.3.2 排课算法设计

本系统采用了基于优先级的回溯算法。在排课过程中一定是按照教师申请使用单中的优先级进行排序,然后读入申请教师设定的实验室信息,判断是否有可用时间,有则加入排课表,如无可用时间则回到实验室信息表重新选择可用实验室信息,再去选择时间,依次类推,知道遍历完所有教学任务,特殊情况可手动调整。具体排课算法如图4所示:

如果用户需要临时添加上机,只需申请选择指定时间下有空的实验室,实验室排课管理员直接加入相应课表即可。

3 结束语

本文设计的排课系统,是在分析了实验室排课存在的现实问题的基础上提出的,基于优先级回溯算法,采用B/S结构。系统设计思路清楚,开发流程简单。目前该排课系统已经处于试用期,通过试用能够较好的完成排课任务,解决了实验室排课这一难题,具有一定的实践价值,后期在在调停课处理等方面还需进一步完善。

参考文献

[1]谭定英,蔡逸仪,李学征.基于遗传算法的排课系统研究[J].现代计算机:下半月版,2009(9):22-25.

[2]宗薇.高校智能排课系统算法的研究与实现[J].计算机仿真,2011,28(12):389-392.

[3]王凤红.回溯算法[J].中国现代教育装备,2011(14):88-90.

[4]张林.基于蚁群算法的排课系统研究与设计[D].安徽大学,2005,34-38.

3.算法设计与分析实验三 篇三

一、揭开神秘的面纱

对学生来说，算法与程序设计课是一个陌生学科，大多学生有很大的神秘感。首先我们注意帮助学生揭开“算法与程序设计”这个神秘的面纱，让学生沿着正确的轨道去汲取新鲜的知识。我是从处理信息的原始工具讲起，逐渐讲到当今处理信息的最先进的工具——计算机。提到计算机，学生就不那么陌生，引导他们回答在哪些地方见到过计算机，这样便引出计算机的广泛应用。由此介绍计算机的发展过程，从原始的计算机的构造及功能讲到当今最先进的计算机的构造及性能，让学生清楚地知道计算机的基本结构的演变和性能的提高，了解计算机这个高科技产物的惊人发展速度，继而从心里佩服这个先进的产物，逐渐开启好奇之门。有了这些基础，接下来的工作就很容易做了，讲述计算机中的信息是怎样表示的；计算机是怎样处理信息的；算法与程序设计中的几个热点问题及计算机的安全问题等等。

二、登堂入室

经过上述的教学，让学生从实质上了解了算法与程序设计、计算机技术及其中的一系列问题，基本上打破了算法与程序设计的神秘感，并且激发了学生的兴趣。下一步就要真正接触到怎样使用计算机这个先进的工具了。

先讲述现在常用的操作系统软件，让学生明白自己所进行的操作都是通过操作系统软件来完成的。接着讲解现在最常用的windows xp操作系统。在这里，我们注意了把微机从开机到windows xp启动成功这个过程讲清楚，这有助于建立学生的整体意识。讲述windows xp时，我们遵循学生的认知规律：先讲清最基本的鼠标操作，让学生反复练习，这里我们增加了一些学生感兴趣的小游戏，如纸牌、扫雷等加强鼠标操作的训练。实践证明，学生很快掌握了鼠标的使用方法。然后可以从最直观的桌面讲起，逐渐扩展到窗口操作、任务栏的作用及各种菜单等等。

三、自由探寻

通过上述的教学，学生已会简单地使用计算机了。但是，毕竟学生的求知欲比较强，这样在后期的教学中，我们采取让学生自主地发现问题、发散思维，让他们对自己感兴趣的问题尽情地去探索、去研究，在不断的探索中提高自己的水平。

四、理论与实践相结合

任何教学活动总离不开理论与实践相结合这条主线，算法与程序设计更是如此。在学习书本知识阶段，由于学生一周一节课，理论与实践时间差大，我们通过对比总结，把原来在教室内上一节理论课，再从微机房上一至两节实践课，改为全部在微机室上课，四十五分钟时间，基本按“讲——练——讲——练——总结”这个模式，教师利用10分钟左右的时间通过教师主机边讲边操作演示，把每一个知识点视难易程度，进行一至二遍讲解和演示，然后让学生模仿练习15分钟左右，接着教师利用5分钟的时间对学生练习中出现的问题及重点进行第二次讲解，之后学生再练习10至15分钟，最后5分钟时间教师抓住教学重点进行总结，把所学知识点系统起来。每一节课根据教学内容不同，可以有不同的时间安排。这样一路走下来，学生基本上能够掌握所学知识。

五、教师要不断更新知识、提高自身素质

算法与程序设计领域发展迅速、更新很快，新知识、新产品、新术语几乎天天出现。作为算法与程序设计教师，只有不断地更新自己的知识，不断地提高自身的素质，不断地自我加压，才能将信息知识更流畅地、轻松地、完整地讲授给学生，才能让学生始终走在算法与程序设计知识的前端，跟上不断发展的时代的步伐。

六、结合现状，激发学生为强国而学习的信心和决心

我认为，算法与程序设计课，不仅仅是让学生学会几种操作，更重要的是培养学生的一种思想、一种意识，为我国各产业的长足发展营造一种良好的氛围。学生，是未来国家的建设者，如何使将来有更多的有志者为我国的算法与程序设计产业作贡献，这就需要我们教师在教学中不断地把我国算法与程序设计业的现状讲述给学生，让他们知道我国算法与程序设计业在世界上的位置，不断激发起他们好好学习、为国效力的决心和毅力，让我国的IT业快速发展，以期早日赶上和超过IT业的发达国家。

4.《算法设计综合实验》教案 篇四

统计与应用数学学院

2012年5月11日制

实验一 数据类型、运算符和表达式

实验目的：

1、掌握C语言数据类型，熟悉如何定义一个整型、字符型和实型的变量，以及对它们赋值的方法；

2、掌握不同的数据类型之间赋值的规律；

3、学会使用C的有关算术运算符，以及包含这些运算符的表达式，特别是自加和自减运算符的使用；

4、学会使用赋值运算符及复合赋值运算符；

5、进一步熟悉C程序的编辑、编译、连接和运行的过程。

实验环境：

Windows操作系统、Visual C++6.0

实验学时：2学时； 实验内容：

1、整型变量实型变量、字符型变量的定义与输出，赋整型常量值时的情形，以及给整型变量赋字符常量值时的情形；

2、各类数值型数据间的混合运算；

3、要将“China”译成密码，密码规律是：用原来的字母后面第4各字母代替原来的字母。例如，字母“A”后面第4个字母是“E”，用“E”代替“A”。因此，“China”应译成“Glmre”。请编一程序，用赋初值的方法使c1、c2、c3、c4、c5这5个变量的值分别为’C’、’h’、’i’、’n’、’a’，经过运算，使c1、c2、c3、c4、c5分别变为’G’、’l’、’m’、’r’、’e’，并输出。

实验二 顺序结构程序设计

实验目的：

1、掌握C语言中赋值语句的使用方法；

2、掌握各种类型数据的输入输出方法，能正确使用各种格式转换符；

3、学习调试程序。

实验环境： Windows操作系统、Visual C++6.0 实验学时：2学时； 实验内容：

1、掌握各种格式转换符的正确使用方法；

2、设圆半径r=1.5，圆柱高h=3，求圆周长、圆面积、圆球表面积、圆球体积、圆柱体积。用scanf输入数据，输出计算结果。输出时要有文字说明，取小数点后两位数字。

3、编程序：用getchar函数读入两个字符给c1、c2，然后分别用putchar函数和printf函数输出这两个字符。上机运行程序，比较用printf和putchar函数输出字符的特点。

实验三 选择结构程序设计

实验目的：

1、了解C语言表示逻辑量的方法（以0代表“假”，以非0代表“真”）。

2、学会正确使用逻辑运算符和逻辑表达式。

3、熟练掌握if语句和switch语句。

4、学习调试程序。

实验环境：

Windows操作系统、Visual C++6.0 实验学时：2学时； 实验内容：

1、有一函数

(x1)xy2x1(1x10)3x11(x10)

用scanf函数输入x的值，求y值（运行程序，输入x的值，检查输出的y值是否正确）。

2、给出一个百分制成绩，要求输出成绩等级A、B、C、D、E，90分以上为A，80～89分为B，70～79分为C，60～69分为D，60分以下为E。要求：（1）事先编好程序，要求用switch语句来实现，运行程序，并检查输出结果是否正确。（2）修改程序，当输入分数为负值，或大于100时，通知用户“输入数据错误”，程序结束。（3）修改程序，要求用if结构来实现，运行程序，并检查输出结果是否正确。

3、给一个不多于5位的正整数，要求求出它是几位数，打印出每一位数字，并按逆序打印出各位数字。

4、输入4个整数，要求按由小到大的顺序输出。

5、求方程axbxc0的解。2实验四 循环结构程序设计

实验目的：

1、熟练掌握用while语句，do-while语句；

2、掌握for语句实现循环的方法，掌握在程序设计中用循环的方法实现一些常用算法（如穷举、迭代、递推等）；

3、掌握break语句和continue语句的使用；

4、掌握循环结构程序中典型的算法；

5、进一步学习调试程序；

实验环境：

Windows操作系统、Visual C++6.0 实验学时：3学时； 实验内容：

1、编程计算1!+2!+3!+„„n!的值，其中，n值由键盘输入。

2、输入一行字符，分别统计出其中的大小写字母、空格、数字和其他字符的个数。

3、输入两个正整数m和n，求它们的最大公约数和最小公倍数；

4、猴子吃桃问题。猴子第一天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了一个。第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第10天早上再吃时，见只剩下一个桃子了。求第一天共摘了多少桃子。

5、求s=a+aa+aaa+„+aa„a之值，其中a是一个数字，n表示a的位数；

6、有一分数序列：2/1,3/2,5/3,8/5,13/8,21/13„„，求出这个数列的前20项之和。

实验五 数组

实验目的：

1、掌握一维数组和多维数组的定义、赋值和输入输出的方法；

2、掌握两种排序算法：冒泡法排序和选择法排序；

3、掌握字符数组和字符串的使用；

4、掌握字符串处理函数的应用；

实验环境：

Windows操作系统、Visual C++6.0 实验学时：5学时； 实验内容：

1、求两个2×3和3×2的矩阵之积，并把结果显示出来。2、10个人的成绩存放在score数组中，编写程序，将不及格的人数，最低分和最高分显示出来。

3、任意给定三个字符串，编写程序：用两种方法给出最大的一个。

4、编写程序，实现矩阵(5行6列)的转置(即行列互换)。

5、输出杨辉三角（要求输出10行）。

6、编程：将一个十进制整数转换成二进制数。

7、将两个字符串连接起来，用strcat函数和不用strcat函数两种情形；

实验六 函数

实验目的：

1、掌握定义函数的方法；

2、掌握函数实参与形参的对应关系，以及“值传递”的方式。

3、掌握函数的嵌套调用和递归调用的方法；

4、掌握全局变量和局部变量、动态变量、静态变量的概念和使用方法；

实验环境：

Windows操作系统、Visual C++6.0 实验学时：6学时； 实验内容：

1、编程序：通过一个函数判断字符串是否为回文?若是则函数返回1，主函数中输出yes，否则返回0，主函数中输出no。回文是指顺读和倒读都是一样的字符串。

ncm2、编程实现由主函数输入m，n并输出最终结果，按下述公式计算的值：

ncmm!nn!(mn)!，其中函数f的功能是计算阶乘，函数g的功能是求cm的值。要求三个函数分别存在三个不同的文件中。

3、编写一个函数fun，它的功能是：将字符串a中所有下标为奇数位置上的字母转换为大写(若该位置上不是字母，则不转换)。主函数只能用来输入输出字符串。

4、小软件。功能是：输入1，测试姓名的得分；输入2，测试两个名字的缘分；输入3，测试某一天的幸运度。要求：三个功能要用三个独立的函数编写，主函数只能用来输入输出结果。

5、写一个判别素数的函数，在主函数输入一个整数，输出是否素数的信息。本程序应当准备以下测试数据：17、34、2、1、0。分别运行并检查结果是否正确。

6、编程序：用递归法将一个整数n转换成字符串。例如，输入483，应输出”483”。n的位数不确定，可以是任意的整数。

7、编程序：求两个函数的最大公约数和最小公倍数，用一个函数求最大公约数。用另一个函数根据求出的最大公约数求最小公倍数。（要求：不用全局变量，分别用两个函数求最大公约数和最小公倍数。两个整数在主函数中输入，并传送给函数1，求出的最大公约数返回主函数，然后再与两个整数一起作为实参传递给函数2，以求出最小公倍数，返回到主函数输出最大公约数和最小公倍数。）

8、编程序：用全局变量的方法，分别用两个函数求最大公约数和最小公倍数，但其值不由函数带回。将最大公约数和最小公倍数设为全局变量，在主函数中输出它们的值。

实验七 指针

实验目的：

1、通过实验进一步掌握指针的概念，会定义和使用指针变量；

2、能正确使用数组的指针和指向数组的指针变量；

3、能正确使用字符串指针和只想字符串的指针变量；

4、了解指向指针的指针的概念及使用方法。

实验环境：

Windows操作系统、Visual C++6.0 实验学时：6学时； 实验内容：

1、编程序：用指针方法编写程序，输入3个整数，将它们按由小到大的顺序排列输出。然后将程序改为：输入3个字符串，按由小到大的顺序输出。

2、编程序：将一个3×3的矩阵转置，用一函数实现之。在主函数中用scanf函数输入以下矩阵元素：

1357911131519

将数组名作为函数实参，在执行函数的过程中实现矩阵转置，函数调用结束后在主函数中输出已转置的矩阵。

3、编程序：用一个函数实现两个字符串的比较，即自己写一个strcmp函数，函数的原型为：int strcmp(char *p1,char *p2);设p1指向字符串s1，p2指向字符串s2，要求s1＝s2时，函数返回值为0；如果s1≠s2，返回它们二者第一个不相同字符的ASCII码差值（如 “BOY”与 “BAD”，第二个字母不相同，“O”与“A”之差为79－65＝14）；如果s1>s2，则输出正值；如s1

4、编程序：用指向指针的指针的方法对n个整数排序并输出。要求将排序单独写成一个函数。n和各整数在主函数中输入。最后在主函数中输出。

实验八 综合训练

实验目的：

综合运用C语言知识，设计实用的一个小系统。实验环境：

Windows操作系统、Visual C++6.0 实验学时：6学时； 实验内容：

请编写完成如下功能的程序：

在主函数main()中输出如下形式的菜单： Management System of Scores Input the data Out the data Sort the data Search one data Exit the System 然后，输出：

Please input your choice: 接收键盘上输入的选择，分别完成输入数据、输出数据、排序数据、查找数据以及结束程序运行的功能。其中前4个功能分别编写函数 input(), output(), sort(), search()实现，第5个功能可以通过调用系统函数 exit(0)实现。

实验九 结构体与共用体

实验目的：

1、掌握结构体类型变量的定义和使用；

2、掌握结构体类型数组的概念和使用；

3、掌握链表的概念，初步学会对链表的操作；

4、掌握共用体的概念与使用。

实验环境：

Windows操作系统、Visual C++6.0 实验学时：4学时； 实验内容：

1、编程序：有5个学生，每个学生的数据包括学号、姓名、3门课的成绩，从键盘输入5个学生的数据，要求输出3门课总平均成绩，以及最高分的学生的数据（包括学号、姓名、3门课的成绩、平均分数）。要求用一个Input函数输入5个学生数据：用一个average函数求总平均分；用max函数找出最高分学生数据；总平均分和最高分的学生的数据在主函数中输出。

2、编程序：13个人围成一圈，从第1个人开始顺序报号1、2、3。凡报到“3”者退出圈子，找出最后留在圈子中的人原来的序号。

5.算法设计与分析实验三 篇五

1.课程基本信息

课程编号：

课程名称（中文）：算法设计与分析

课程名称（英文）：The design and analysis of algorithms 开课学期： 见培养方案与教学计划 课程类别： 专业基础课程

课程学时数与学分： 56学时（4学分，不含实验课时，4学时/周）

实验学时数与学分： 28学时（学分计算并入计算机科学实验课程，4学时/次/周）先修课程： 高等数学或数学分析，线性代数或高等代数，概率论与数理统计，离散数学，高级语言程序设计，数据结构

教学形式： 课堂讲授 + 课外教学 + 实验教学（实验课程实行单列）使用教材：

张德富，算法设计与分析，国防工业出版社，2009,8。教学参考书：

[1] T.H.Cormen, C.E.Leiserson, R.L.Rivest and C.Stein, Introduction to Algorithms(the second edition)，The MIT Press，2001 该书国内已引进，见《算法导论（第二版）》（影印版，中文本），高等教育出版社，2003 [2] M.H.Alsuwaiyel，Algorithms Design Techniques and Analysis，World Scientific Publishing Company，1998 M.H.Alsuwaiyel，吴伟昶 等译，《算法设计技巧与分析》（中文版），电子工业出版社，2004 [3] Sartaj Sahni著，汪诗林等译，《数据结构、算法与应用--C++语言描述》，机械工业出版社，2003 [4] 王晓东编著，《计算机算法设计与分析》，电子工业出版社，2005 [5] Gilles Brassard, Paul Bratley.《FUNDAMENTALS OF ALGORITHMICS》(算法基础)，清华大学出版社，2005 注：[1]和[2]两本书为主要教学参考书。

大纲制定者： 张德富、赵致琢、苏 畅（厦门大学计算机科学系）大纲审定者： 赵致琢（厦门大学计算机科学系）

2．课程性质、类别与任务

“算法设计与分析”是计算机科学与技术专业一门重点专业基础课程，也是学科核心专业基础课程之一，属于必修课程。本课程主要介绍算法的基础知识，包括抽象计算模型、算法基本概念、算法复杂性分析基础、算法设计的基本方法、以及算法复杂性理论基础。通过本课程的学习，要求学生理解并熟练掌握：了解可支持算法运行的抽象机器计算模型，算法的定义和复杂性概念，算法设计的基本技术方法，包括递归与分治法、贪心法、动态规划方法、回溯法、分支限界法以及高级图论算法等，理解并掌握算法复杂性的分析方法、NP完全性理论基础等计算复杂性的基本知识以及完全性证明概要。通过教学和实践，培养学生运用数学工具和方法分析问题和从算法的角度运用数学工具解决问题的基本能力，培养学生设计算法和分析算法复杂性的基本能力，训练学生的逻辑思维能力和想象力，从而使他们能够正确地分析和评价一个算法，进一步设计出真正有效或更有效的算法，并使之了解算法理论的基础知识和发展概况。在教学中，鼓励学生运用算法知识解决各个学科的实际计算问题，培养学生初步的独立开展科研工作的能力和理论联系实践，解决实际问题的能力，同时，为后续课程以及将来的研究工作提供必要的算法设计与分析的基础。

此外，配合实验课程的教学，学生应理论联系实际，理论指导实践，通过规范地完成一系列算法设计实验进一步巩固所学的相关书本知识，在知识、能力、素质上得到进一步的提高。

3．课程教学的基本要求（教学内容和教学重点）

“算法设计与分析”内容的重点是各种常用的算法设计方法和复杂性分析方法，包括递归与分治法、贪心法、动态规划方法、回溯法、分支限界法，以及高级图论算法、时空复杂性的分析方法、NP完全性理论基础。课程教学的基本要求是通过教学活动，使每一个学生较好地掌握课程的主要内容，同时具备对实际问题应用所学知识设计出有效算法并编程实现这些算法的能力。课程的教学内容主要包括如下知识点，其中，属于重点的内容用黑体标示，今后教学改革拟增加的内容用“{„„}”标示，部分非重要内容用括弧标注为“一般了解”： 基本概念：问题;抽象计算模型；算法的概念；算法正确性;算法效率；问题下界 算法的评估：时间复杂性和空间复杂性分析；算法的最优、最差和平均效率；渐近复杂性符号和基本效率类型；非递归算法的数学分析；{概率分析（一般了解）；分摊分析（一般了解）；算法的经验分析；算法可视计算方法}； 递归：递归设计；递归算法转非递归算法；递归算法的设计实例；递归算法的数学分析，{三种求解递归方程的方法}；

分治法：分治法的基本思想；分治法设计的特点；分治法的时间复杂性；分治法的应用（大整数乘法和Strassen矩阵乘法；棋盘覆盖）； 基本的排序算法及其复杂性分析：插入排序；堆排序；快速排序；排序算法复杂度分析及其比较（此处的教学重点在于算法分析，透过算法分析从中深入了解算法的特性，进一步揭示设计更为有效的算法的思路和途径）； 动态规划方法：动态规划的基本要素（含最优性原理）；矩阵连乘问题；0/1背包问题；装配线的调度问题；最长公共子序列；

贪心算法：贪心算法的基本要素；背包问题；哈夫曼编码；活动选择问题；{贪心算法的理论基础（一般了解）}；

回溯法：回溯法的基本思想；装载问题；0/1背包问题；旅行商问题；批处理的作业调度问题；n皇后问题；子集合问题；回溯法的效率分析；

分支限界法（分支定界法）：分支限界算法的基本思想；装载问题；0/1背包问题；旅行商问题；批处理的作业调度问题；分支限界法的效率分析；

网络与高级图论算法：最短路径问题（Prim算法；Kruskal算法；Dijkstra算法；Warshall算法和Floyd算法）；最大流问题（Ford-Fulkerson标号算法等）；最小费用最大流问题（最小费用算法等）；{匹配问题及其求解算法}； 问题的复杂性：NP完全性理论基础（P类与NP类问题，NP完全性问题及其归约；NP完全性证明；典型的NP完全问题）；{ 如何求算法复杂性的下界（一般了解）}。

4．关于教学目标、教学内容的建议和教学过程中应该注意的事项

算法设计与分析是计算机科学的核心问题之一。由于计算机科学与技术的大多数研究都与算法紧密相关，因此，高起点的算法理论基础逐步成为了高素质计算机科学与技术专门人才应该具备的必要的理论修养。设计算法的目的是要解决大量实际问题，对于较复杂的问题要求能设计出有效的算法。大量的研究实践表明，一个问题求解质量和效率的高低，主要取决于算法设计的质量。因此，算法设计与分析的重点是掌握算法的概念和基础理论，运用数学工具分析问题，从计算方法的角度如何给出非数值计算问题的计算方法、采用算法设计的常用方法设计算法，掌握分析和估计算法复杂性的方法，并特别注意以下几点：

第一，在介绍算法的基本概念时，应该着重介绍计算模型、算法的概念、考察算法的角度和算法评估的标准、复杂性分析的方法以及算法研究的目标与实际问题的关系；

第二，在介绍一些数据结构已经学习过的排序算法时，不应过多强调算法设计，而应该重点结合算法分析技术，用分析的方法评价算法的优劣，从分析结果得到设计更优算法的启示。在介绍高级的数据结构时，重点应放在对数据结构的复杂性分析上；

第三，在介绍算法设计的基本方法（例如分治法、贪心法、动态规划方法、回溯法与分支限界法）时，应该通过对大量经典问题的算法设计与分析，使学生逐渐掌握算法设计与分析的技巧，并特别注意各种算法的比较分析。例如，递归与分治、贪心与动态规划、回溯与分支限界；

第四，在介绍NP完全性理论时，应该着重从问题的分类以及各类问题的性质、相互关系入手进行研究，揭示问题的本质，从而为算法的设计提供方法指导。另外，应该着重掌握问题的转化及NP完全性理论的有关证明思想；

第五，在介绍线性规划问题及其相应算法时，应该着重介绍该算法的应用；

第六，鼓励教师将自己的研究或最新算法设计与分析的思想，结合到教学过程之中，鼓励和帮助学生运用所学的知识去解决实际问题，掌握理论与实践相结合的思想方法。第七，鼓励教师结合学科范型（也称范式），将学科方法论的内容融入教学过程之中（对教师暂不作基本要求），以帮助学生建立与“算法设计与分析”课程内容相关的科学的思想方法。

5．课外教学要求

本课程的课外教学内容和形式主要由学生阅读经典教材，任课教师辅导、答疑、批改作业、实践环节等几部分构成。本课程要求学生在有时间的情况下，尽可能完成教材中所有的习题。学生应在任课教师的帮助下，认真听课，反复思考，大量完成作业，在学习中反复进行阅读、思考、做习题，通过阅读、思考、做习题、分析、联想、概括、归纳、总结等多种有效的方式方法，比较全面、准确地掌握课程的主要内容和教学重点。

任课教师（包括助教）每周安排1次辅导、答疑，每次2小时。每次辅导、答疑至少应有一位教师参加，一般不得合并执行。主讲教师应批改全班学生作业量的5%，参加辅导、答疑的次数不少于总次数的1/5，以掌握教学的效果，调控教学进度。

课程对学生作业的质量要求是：正确、简洁、规范。

要求做题正确，意味着学生必须掌握基本概念、基本原理、基本方法、基本技术等课程的基本知识，基本知识不掌握，就很难正确解答问题，这是对学生知识水平和解决问题能力的考核。要求做题简洁和规范，意味着在正确解题的情况下，不应该存在“拖泥带水”和“东拉西扯”的问题，书面表达简练、规范，与教材中例题求解的表述基本一致。这些，正反映出学生在这方面训练有素，这是对学生素质的考核。

6．课程的实验教学

实验课程将安排一些有代表性的上机实验单元与本课程相呼应，目的是通过实验让学生体会理论与实践高度统一的学科特点，进一步认识理论、抽象、算法设计等三个过程及其相互关系，形成对学科范型更深入的体会和认识。它要求学生从分析问题出发，利用所学的算法设计技术去解决某一实际问题。通过实验工作，借助程序设计语言，掌握运用数据结构、算法和程序解决一些实际问题的方法。

学生应按照理论联系实际，理论指导实践的要求，在实际操作中规范地完成各项实验。通过实验工作，借助程序设计语言，设计并实现算法，进一步掌握运用数学工具，分析问题，提出求解方法，设计算法，分析算法的复杂性，对算法进行科学的评价等方面得到严格的训练。

实验教学按照实验单元进行，一个实验单元完成后或相近内容的一组实验单元完成后，每一个学生要撰写和提交实验报告。任课教师应依据每一个学生的实验报告和完成实验的情况，在学期结束时给出学生该门课程的学术评语和成绩，并与四个学年所有实验课程评语一起，最终产生对学生的实践能力作出综合评定的学术评语与成绩。学术评语应着重从发展的眼光和视角，考察学生是否能够理论联系实际，理论指导实践，按照实验课程的教学要求，规范地完成实验单元，较好或基本掌握了实验教学的内容。

在实验课程单列之前，课程的实践环节拟安排28学时（实际执行7次共7*4=28学时），教学内容由大纲确定，实验课程单列之后，实验考核成绩单独计算，不计入课程考核成绩。各实验单元和内容如下：

实验单元一：用贪心法求解一个具体问题的实验（程序实现）； 实验单元二：用动态规划方法求解一个具体问题的实验（程序实现）； 实验单元二：用回溯法求解一个具体问题的实验（程序实现）； 实验单元四：用分支限界法求解一个具体问题的实验（程序实现）； 实验单元五：用高级图论算法求解一个具体问题的实验（程序实现）。

上述五个实验完成后，每个学生应提交二个实验报告。前三个实验完成后提交一个实验报告，后两个实验完成后，提交一个实验报告。

7．考核的方式方法

课程结束考核方式： 闭卷考试 课堂考试时间： 3小时（180分钟）

考试命题： 任课教师命题，教研室分管该课程的负责人和分管教学的系副主任审题； 课程考试的命题内容要从大纲的要求出发，围绕本课程的教学内容、知识点和教学要求，着重从知识、能力、素质三个方面对学生进行全面的考核，重点考核学生运用知识解决问题的能力，同时考察学生的综合素质。考核范围为除了最后一周教学的内容外，其他大纲确定的知识点都在考试范围之内，课程考试的试卷命题范围不得免除期中考试已经考过的内容。试卷中不少于85%的内容应来自课程重点内容的范围，不少于10%的内容应来自课程非重点内容的范围，要求学生全面复习，以达到系统掌握，全面考核的目的。试卷的题型要力戒避免文科标准化试卷的题型，避免出现简单概念问答题和简答题。试卷题目数量一般为5、6、7题，以优秀学生在全部会做的情况下正常书写速度能够在120分钟内完成为宜。试卷题目数量的减少与全面考核的目的并不矛盾。由于考核的范围是明确的，只要教师不透露题型和范围，学生就必须全面复习，这样，即使题目不覆盖某些教学内容，也不会影响实际的教学效果。

随堂监考授权： 主讲教师和助教

6.算法设计与分析实验三 篇六

本册教学内容分为三个单元，1、播放儿时的音乐，请两位同学穿上幼时的服装走一走，2、尝试体验。全班同学尝试。

3、交流感受。

4、揭示话题。师：“同学们已经开始了新学期的学习。虽然大家的姓名不同，生活经历也不一样，但每个人都有一个温暖的家，每个同学都是从一个小娃娃成长为一名三年纪的学生，今天让我们一起来回忆自己长大的历程。”（板书：我长大了）

二、小组合作——探究“长大”

1、那我们和刚上一年级相比，我们有那些变化，先看书上这两个同学再干什么？

2、师：“每位同学都和课本上的小朋友一样，经历了一个成长的过程。今天我们一起来开展一个有趣的活动——我的‘昨天’和‘今天’。”

1）小组测量。测量每个人的身高和体重，与自己出生时的情况作比较。

2）小组评一评。各小组向全班介绍：自己小组哪位同学体重增加最多，哪位同学身高增加最多。3）填写书上的成长记录卡。

三、交流故事——分享“长大”的快乐 1）小组展示照片，感悟长大是一个过程。2）小组交流

3）教师事先布置的任务：选择一件自己幼年时期最有趣的事情讲给大家听，尤其是那些令爸爸妈妈和自己难忘的事。选择一件自己幼年时期的用品。

四、活动：比比谁的本领大。

师：同学们通过两年的学校生活，随着年龄的增长，无论在学习上，还是在生活上都发生了很大的变化，学会了很多本领，下来我们就来比一比，看谁的本领大。

游戏一：系鞋带 游戏

二、记忆单词。

五、教师总结：“通过今天的课堂活动，我们知道了每一位同学从呱呱坠地的婴儿到今天，都长大了许多。更重要的是，同学们比以前更深刻地懂得了‘长大‘的含义。希望同学们经常想到这一点，像个‘长大’的孩子。”也希望大家在以后有更大的进步。

学生活动

1.尝试体验。全班同学尝试。2。交流感受。

学生阅读教材。

1、小组测量每个人的身高和体重与自己出生时的情况作比较。

2、小组成员互相评一评哪位同学体重增加最多，哪位同学身高增加最多。小小组交流自己幼年时期最有趣的事情，展示 一件自己幼年时期的用品。

每组请一位同学代表回答（其他组选择不同现象回答）

教学过程： 教师活动：谈话导入

师：同学们，我们已经知道，是爸爸妈妈给我们以生命，是他们无微不止地关心我们，哺育我们健康成长。随着我们不断长大，我们懂得的事情会越来越多。如今我们已经使三年级的学生，无论在学校还是在家里，都应该变得懂事。

板书课题：我懂事了 提问：什么叫懂事？

二、小小交流会 1.探究活动：

让学生阅读课本插图。

同桌互相来说说妈妈说了些什么孩子会说些什么？

2、课前老师布置同学们了解一下家长的工作，你们了解吗？同学互相说一说。

3、讨论交流 :哪些事情我们三年级学生已经可以自己做了，可以让爸爸、妈妈下班回来后多休息一会儿，能让他们感到高兴。”举例说一说自己是一个懂事的孩子。

3.老师调查同学们在家里做得不好的地方例如：撒娇、任性、在学校不懂礼貌。欺负同学等等，如果出现这种情况那我们同学应该怎么做？

请一位同学写一个准备在今后执行的小计划，可以参考刚才大家讨论过的，写在黑板上的内容。

4.教师要说明计划的要求：

1)一定是自己力所能及的、经常需要做的日常生活家务劳动，而且要求一旦写 了，今后就要坚持下去，不能“三分钟热气”直到现在为止，还是爸爸、妈妈在做 的家务劳动。内容不要过多，一两项就可以了，最 多不超过三项。

师：大家制定了计划，就要按照计划去做，而且实现不要告诉爸爸、妈妈，给他们一个惊喜。他们一旦发现，一定会非常高兴，一定会夸奖说：“我们的孩子真的长大了！

3.教师总结。“爸爸、妈妈为了家庭的生活而操劳，工作很辛苦。我们已经是三年级的学生了，应该懂事了，要减轻爸爸、妈妈的负担，做一个好孩子。”

4补充资料：“母亲节的由来”，并介绍父亲节。

三、布置作业

落实自己的计划，并且了解家长的反应。

落实计划几天后，完成课本P13右上角“我的感受”。

学生活动

学生交流“母亲节的来历”。

2、我的优点与不足

我的优点和不足

教学目标 ：

知识目标

1、知道人各有所长，懂得取人之长，补己之短的道理。能力目标 ：观察同学身上的闪光点，学会欣赏和尊重别人。

情感目标： 了解自己的优点和不足，并有意识地发扬优点和克服不足。教学重点 ：敢于和同学交流彼此之间的优点与缺点。教学难点 ：设计和书写调查问卷，能正确评价和书写。

1.教学准备 请学生准备能代表或证明自己优点的物品，如证书、奖状、照片等以备展示自己的优点时使用。2.为小小辩论会准备正方和反方两个牌子。

3.根据班级人数，准备相应的纸条，其中若干张写有“被评价人的字样以备抽签时使用。4.请学生准备好若干张调查问卷。

5.与各科教师协商，请他们帮助评价学生。课时安排： 两课时

板书设计

我的优点与缺点

实话实说评自己 小小辩论会

1．学生搜集名人兴趣爱好广泛的小故事。2．学生准备能展现自己特长的作品。3．制作课件：海伦•凯勒的故事。教学过程

一、动画导入，畅谈兴趣

教师创设情境：同学们，你们喜欢交朋友吗？今天我给大家带来一位新朋友，你们想认识他吗？你们看，他来了。（出示课件）

教师提问：谁愿意先说说你最感兴趣的事? 学生畅所欲言，谈自己的兴趣爱好。教师根据学生发言，及时评价。

小结：听了大家的话，老师心里特别高兴。你们知道这是为什么吗？因为从你们的发言中，老师了解到大家的兴趣是健康的、有益的。这些良好的兴趣爱好有利于我们身心的健康发展。在广泛的兴趣和爱好中，你最拿手的是什么？和你志趣相投的朋友结成小组，在一起说一说，看一看。一会儿每个小组选出最棒的同学在全班展示。

二、小组合作，展示自我

学生根据兴趣结成小组，交流自己的特长和作品。

三、师生互动，因势导行

教师鼓励学生展示自己的特长：谁愿意 1.教师以两种方式和学生问好（一种不自信“上„上„上„课”，一种精神饱满地“上课”）。2.师：你们喜欢老师的哪一次问好方式？为什么？

3.师：老师对付自己的不自信是有方法的，我在放弃、退缩的时候，就在心里默默地告诉自己三个字，你们猜是哪三个字？（认可学生所猜，板书：我能行！）

4.师小结：无论做什么事情，要想做好，首先要相信自己，只要相信自已行，才会我能行！（板书：相信）

二、开展活动，体验情感 活动一：“丁丁和甜甜的苦恼”

1.师：在许多事情中，为什么有的同学敢于表现自己，有的同学却自我放弃和退缩呢？今天，老师给大家请来了两位带有苦恼的小朋友。

2.出示课件：丁丁和甜甜的苦恼

3.师：你对于丁丁和甜甜的表现有什么看法？ 4.我们帮着他们出出主意好吗？

5.师：同学们的方法可真多啊，真是赛过小诸葛，你们在生活中怎样解决问题，排除烦恼呢？——生讨论。老师这儿还有一些排解烦恼的小方法，送给大家。课件出示：①多运用“我能行”、“我会继续努力”等语言激励自我。②把烦恼讲给身边的人听。③面对镜子微笑1分钟。④闭上眼睛深呼吸2分钟„„

活动二：正视不足，明理导行

1.导语：老师在教学中也遇到了小朋友有苦恼的情况，他把苦恼讲给我听，我给他出了个小主意。

2.教师讲教材P13“张小波的故事”。3.分步引导：

你在课堂上有没有不敢举手发言的时候，在学英语时有没有单词记不住，觉得自己特别笨，不想学的时候，在跑步中有没有因为落后而不想跑的时候？„„

（1）原因是什么？（生说原因）

（2）长期这样下去会怎么样呢？（生说不自信的危害）（3）今后准备怎么做？（生畅谈想法）

4.小结：同学们找到了自己的不足，了解了缺乏自信的原因，认识到了缺乏自信的危害，用自己的方法解决了问题，你们真棒！请同学们听听好朋友大嘴青蛙的忠告：（课件出示学生读）要想让自己各方面得到锻炼，就要敢于表现，把自己展示出来。

5.哪些同学愿意展示一下？（学生展示）师：展示自己，表现自己，我能行.

1、情感、态度、价值观

1）感受家庭成员间的亲情，知道自己的成长离不开家庭，感激父母长辈的养育之恩。2）关心家庭生活，愿意分担家务，有一定的家庭责任感。

3）体会健康文明的生活方式对个人身心健康和家庭幸福的影响，原理陋习，养成良好的生活习惯，崇尚健康文明的生活方式。

4)热爱生活，养成自主、乐观向上、热爱来动、勤俭节约的生活态度。

2、能力与技能

1）能以恰当的方式表达对父母长辈的尊敬、感激，关心、孝敬父母长辈。2）学习料理自己的生活，自己的事情自己做，养成健康文明的生活习惯。3）初步学会合理消费、勤俭节约。

4）能主动与父母长辈交流，并正确处理自己与家庭成员之间的矛盾。5）学习搜集、处理、分析和运用信息，能够运用信息说明问题。

3、知识

1）了解自己家庭成员的组成、职业、爱好、个性特点，以及家人和亲属的社会关系。2）了解自己的成长历程以及在自己成长历程中父母亲人付出的辛劳。3）知道家庭的经济来源，了解家庭生活必要的开支。4）知道在家庭生活中必要的待人接物的礼节。

5、说说我的家 教学内容 我的家庭成员与亲属 教学目标 ：

知识目标 ： 知道自己家庭成员的组成,初步了解家人的民族职业爱好和个性特点,以及家人和亲属的社会关系.能力目标 ： 学习调查的方法获取信息,运用类推的方法进行问题分析.情感目标 ： 关爱家人,了解家人.教学重点 ： 知道自己家庭成员的组成,初步了解家人的民族职业爱好和个性特点,以及家人和亲属的社会关系.教学难点 ：学习调查的方法获取信息,运用类推的方法进行问题分析.教学准备： 教师学生家人的全家福 学生事先了解自己的家庭成员 家庭成员与亲属的关系结构图.课时安排： 两课时

二.了解成员与亲属的关系

师：在家庭中你是爸爸妈妈的孩子，你知道爸爸妈妈又是谁的孩子呢？与爸爸妈妈同辈的还有谁？ １、指导学生看家庭成员与亲属的关系表． ２、放＜亲属歌＞

３、师生配合一问一答：如：爸爸的爸爸叫什么？生：爸爸的爸爸叫爷爷；了解类似姥姥姥爷的孩子． ４、指导学生填写书中的问题．

总结：同学们这节课我们学的是家庭成员与亲属的关系，你们明白了吗？相时考考再巩固． 作业布置：将未完的书中作业填写完整．

6、我是怎样长大的

教学目标 ：

知识目标： 使学生知道自己的成长离不开家庭,感受家庭成员间的亲情懂得感激父母长辈的养育之恩.能力目标：通过观察和体验,学习透过现象表面看事物本质,发现和理解生活的丰富内涵学习搜集处理分析和运用信息,并能够解决生活中实际问题.情感目标：能以恰当的方式表达对父母长辈的尊敬和感激,懂得关心和孝敬父母长辈.教学重点：使学生知道自己的成长离不开家庭,感受家庭成员间的亲情懂得感激父母长辈的养育之恩.教学难点：能以恰当的方式表达对父母长辈的尊敬和感激,懂得关心和孝敬父母长辈.1.教学准备 学生儿时用的纪念品.2.学生的影集.课时安排：两课时

情感目标：能以恰当的方式表达对父母长辈的尊敬和感激,懂得关心和孝敬父母长辈.教学重点：使学生知道自己的成长离不开家庭,感受家庭成员间的亲情懂得感激父母长辈的养育之恩.教学难点：能以恰当的方式表达对父母长辈的尊敬和感激,懂得关心和孝敬父母长辈.教学准备：学生儿时用的纪念品；学生的影集.爸爸妈妈抚育我教学过程： 一.谈话导入新课: 师:孩子们,是你们的爸爸妈妈带你来到这个世界上,你们的每一步成长饱含着爸爸妈妈的关爱,每一个小小的进步都离不开他们的耐心教诲.1.看书21页图,分别指名四位同学说说图意.2.师:其实孩子们你们的爸爸妈妈在抚育你的过程中付出很多艰辛.下面来开展爸爸妈妈抚养我们成长的故事会.二.活动:学会感谢

1.师: 爸爸妈妈这么辛苦,我们作为孩子的应该怎样感谢爸爸妈妈呢? 2.学生分别谈自己的感谢的方法,给孩子充分的空间尊重他们的个性.3.书上也有两位同学谈了谈自己的看法,你们讨论一下他们感谢父母的方式有几种? 师:其实孩子们的想法分为两方面,一方面对自己作好自己应该做的事另一方面则是对家人孩子在家庭中应该懂事,学会孝敬父母长辈..4.交流汇报一下,你是哪一种? 5.给爸爸妈妈一个惊喜.1)请同学们把书翻到22页,看看这里的孩子怎样给自己父母一个惊喜的.学生谈看后感受.2)说说你准备怎样给父母一个惊喜呢? 6.记住这些特殊的日子

1)你知道爸爸妈妈的生日吗? 2)你知道你们的家日吗? 3)你还知道一些重要的节日吗? 如:母亲节,父亲节,老人节 学生看书,指名的同学说图意.同桌互相说故事会.同桌先互相说一说.各组选派的同学在会上发言.学生来谈自己如何感谢父母.将感谢的方法分为两类.7、爸爸妈妈真辛苦 教学目标 ：

知识目标 ：通过观察,探究活动,使学生能感受父母的辛苦.能力目标 ：能够体察父母的辛苦.情感目标 ：对父母的辛苦能理解,并愿意承担一部分家务.减轻父母的负担.教学重点 ：通过观察,探究活动,使学生能感受父母的辛苦.教学难点 ：能够体察父母的辛苦,了解父母的烦心事,并能想法给父母减压.1.教学准备 ：跟随父母一天,认真观察父母的工作和做家务的情况.2.小调查,调查了解父母的内心烦恼.课时安排：两课时

5.思考:爸爸妈妈为什么要这样辛苦?不这么做可以吗? 活动二.了解爸爸妈妈的烦心事.思考:爸爸妈妈不仅要努力地工作,还要抚养子女,照顾老人,有时还会遇到一些烦心事,爸爸妈妈有哪些烦恼呢? 1.教师引领学生阅读教材 1.通过评价与反思,认识自己在哪些方面做得不够好,还需要在哪些方面继续努力.2.填写”我的承诺”

3.师:孩子们在这里我借助大嘴青蛙的一句话作为结束:自己承诺的事,可一定要做到啊!五.布置作业: 将我的承诺完成.8、不当家不知柴米贵

教学目标;知识目标:了解自己家的经济来源的组成和具体有哪些项生活支出。能力目标:培养学生参与家庭生活，分担家庭责任的能力。

情感目标：懂得自己父母挣钱的不易，懂得珍惜父母的劳动收入，同时明白自己家的家生活支出有那些以及自己的花销占多少。

教学重点;了解自己家的经济来源的组成和具体有哪些项生活支出 教学难点:培养学生参与家庭生活，分担家庭责任的能力。

教学准备:教师了解劳动收入和非劳动收入，了解所带班级同学家庭收入来源。学生向家长调查统计家里的一个月固定支出及一年的不固定支出。课时安排：两课时

教学目标：

知识目标 ：学会健康的生活，远离不健康和不文明的生活习惯，生活方式。

能力目标;乐于养成文明、礼貌的行为习惯。情感目标:具有自尊自爱的生活态度。教学重点:学会在家里的正确待客之道。

教学难点 ；学会将家里的文明礼貌行为进行归类。教学准备 ：准备一些茶具水果等在表演的时候使用； 学生准备彩笔，添涂“我的表现怎么样”评价表使用 课时安排：三课时 板书设计：

家庭中的礼节

家庭起居 文明语言 文明就餐 行走坐卧

师：有的同学一下觉得无从说起，那好，书中给大家一个提示我们一起来看看。

1、仔细阅读 2）能与同学平等相处，互相宽容谅解，避免不必要的矛盾。3）能用合适的方法化解与同学间的矛盾，形成良好的人际关系。

4）学会合理安排时间，掌握正确的学习方法，养成良好的学习习惯，能够轻松愉快地学习。5）能选择恰当的方式与同学合作，共同分享快乐。

3、知识

1）了解班级成员组成，班主任、班长是谁，男女生人数，以及班级曾今获得过哪些荣誉。2）了解自己好朋友的兴趣、爱好、个性特点。3）知道怎么样去化解矛盾、增进同学间友谊。

4）了解取得好成绩的同学的学习方法，自己如何去做才能养成良好的学习习惯，并能使学习成为乐趣。5）知道合作需要分工、程序和秩序，积极参与和默契配合。

10、说说我们班 教学难点：学会在班集体中与人交流,合作分享快乐积极参加集体活动.教学准备：准备“假如我是”的演说稿 和班主任携手共同举办好这次竞职演说。教学过程：

一、谈话导入新课：

同学们，王老师知道大家非常热爱我们的班级，想为我们的班级出点力，让我们的班变得更好，更出色，老师想在今天这节课上开展一次别开生面的演讲会，大家喜欢吗？

二、演讲前的准备

1.同学们，提前准备好了就职演说，现在在小组内读一读，让本组的同学为你提出好的意见。2.演讲开始

师：那一位同学 应该怎样做.师:真正的朋友应该互相关心,互相帮助,遇到困难应该共同想办法,而不是共同去做坏事,如果友谊用不平等的交往进行,那么迟早他都会失横的.所以友谊的天平必须是平等的.那么平等的友谊表现在哪些方面: 师:你能举个例子吗? 总结:朋友是什么,朋友是你干渴时的一杯水,朋友是你寒冷时的一丝温暖的阳光,马克思与恩格斯两位朋友共同完成了<资本论>,所以,孩子们珍惜你们之间的友谊吧,黄金有价,友谊无价.四.布置作业

7.静态排序算法设计与分析 篇七

关键词：静态排序,算法复杂度,记录比较,记录移动

0 引 言

随着各行各业的飞速发展,计算机需要存储与处理的数据也在以惊人的速度增加。在如此庞大的数据群中,人们为了便于检索,通常希望能在计算机中保存的数据是按关键字值大小排列的有序表。在现今的计算机系统中,有相当大的一部分CPU时间开销是用于对数据的排序整理上的,而在这一部分CPU时间开销中,记录移动所引起的CPU时间开销又占据了相当大的一部分,并且如果待排序的记录相当大(即每个记录所占空间较多)时,记录移动所引起的CPU时间开销将对整个数据排序的CPU时间开销起到决定性的作用。因此,学习和研究各种排序算法,分析并设计出高效适用的排序算法,是摆在计算机科学工作者面前的重要课题之一。为了解决大量的记录移动而引起的CPU时间开销问题,本文提出了静态排序算法。这是一种记录移动次数(2n)恒定的稳定的内部排序算法。

1 算法的定义与核心思想

1.1 定 义

静态排序算法是一种通过对数组Value[1…n]中任意两个记录比较来计算出每个记录在已排序数组中的索引值并把其储存在数组Index[1…n]中,进而由Result[Index [i]]=Value[i]直接得到已排序数组Result[1…n]以达到对数据排序的目的稳定的内部排序算法。

1.2 核心思想

每个记录在已排序数组中的索引值与其所在的数组中比它本身大(小)的记录的个数有关。具体而言,若在一个数组中小于记录A的记录有k(0<=k<n-1)个,则当对该数组排序后所得到的数组中记录A的索引值一定为k(规定:若Value[i]== Value[j]且i<j则Value[i]< Value[j])。由原数组记录值及各个记录在已排序数组中的索引值直接构成有序数组。

2 算法的实现

2.1 排序实现

静态排序算法的实现过程主要分为三步。

第一步 通过记录值比较来求得各个记录在已排序数组中的索引值。求索引值的过程中有两种不同的情况。情况一:数组中任意两个记录的值大小都不相同,此时在数组中比记录A的值小的记录的个数则为记录A在已排序数组中的索引值。情况二:数组中至少存在两个记录的值相同,假设这两个值相同的记录分别为记录C和记录D,此时比记录C和记录D的值(假设记录D比记录C在原数组中的索引值大)小的记录的个数则不可能同时是记录C和记录D在已排序数组中的索引值。为了保持静态排序是稳定排序的特性,假设记录D的值要比记录C的值大。综合上述两种情况所述,若记录X的值小于比其索引值大的记录Y的值则记录Y在已排序数组中的索引值加1,否则记录X在已排序数组中的索引值加1。当对数组中任意两个记录进行比较后,就可以得到所有记录在已排序数组中的索引值。

第二步 由数组Value[1…n]与数组Index[1…n]直接构成有序数组。其中巧妙地应用了两个数组相同位置的对应关系,即Index[i]中存储的索引值恰巧是Value[i]在已排序数组中的索引值。因此,可以得出Result[Index[i]]=Value[i]。这是一个有序有目的地插入记录的过程。当遍历了整个数组Index[1…n]后,所有的记录就有序地插入到了结果数组中,最终得到有序数组Result [1…n]。

第三步 把结果数组Result [1…n]中的所有记录拷贝到原数组Value[1…n]中,最终实现原数组的排序目的。下面是用算法语言描述静态排序的过程。静态算法如算法1所示[1,2,3]。

2.2 测试结果

如图1所示:原先数组是一个无序数组,调用静态排序算法排序后得到一个有序的数组,从而验证了静态排序算法的正确性。

3 算法及测试结果的分析

表1是在测试静态排序算法过程中各变量值及存储值的变化情况(表中CC是记录的比较次数)。

从表1可得每一趟比较都会得出在数组中比该记录小的记录的个数,这个数值也正好是该记录在已排序数组中的索引值。分析静态排序的效率:

时间复杂度:

$Y={\displaystyle \sum _1^{n-1}i}=n(n-1)/2$

需进行n(n-1)/2次比较,且移动记录2n次。因此,总的时间复杂度为Ο(n2)。

空间复杂度:

需要借助一个长度为n的整型数组空间和一个原数组相同的数组空间。所以空间复杂度为О(n)。

4 各种算法的比较与分析

4.1 各种算法的平均复杂度

如表2所示,从时间复杂度上看,静态排序、起泡排序、插入排序、选择排序的平均时间复杂度均为Ο(n2),而希尔排序、快速排序和归并排序的平均时间复杂度均为Ο(nlog2n)。从空间复杂度上来看,起泡排序、插入排序、希尔排序、选择排序仅需一个存储空间,空间复杂度为О(1)。静态排序与归并排序都需要与n同级别的空间,空间复杂度为О(n)。而快速排序需要的空间与原数组中记录的顺序有关,需要(log2n,n)个存储空间,空间复杂度为О(n)。

4.2 各种算法的记录的比较次数与移动次数

4.2.1 根据记录比较与移动次数的理论值分析比较算法

各种算法的记录比较次数的理论值如表3所示。

各种算法的记录移动次数的理论值如表4所示。

4.2.2 根据记录比较与移动次数的实验值分析比较算法

以下四张图是根据1000次实验得到的数据绘制而成的。为了真实地模拟实际中的排序问题,每次的测试数据都由随机数构造而成。

图2是各种排序算法中记录移动次数的总体比较,从图中可以看出起泡排序的记录移动次数是最多的,且比其它的排序方法的移动次数要多很多,插入排序的移动次数次之。其余五种排序方法的移动次序要少很多。

图3是图2中其余五种排序算法的记录移动次数的详细比较图,从图中可以得出静态排序的移动次数是最少的,快速排序次之,接着是选择排序,然后是希尔排序,最后是归并排序。所以只从记录的移动次数来看,静态排序是最优的。

图4是各种算法中记录比较次数的总体比较图,从图中可以直观地发现静态排序、起泡排序、静态排序的比较次数是最多的,大约是n2/2,插入排序的移动次数次之,大约是n2/4。

图5是图4中其余三种排序算法中记录比较次数的详细比较图,从图中可以看出归并排序的比较次数是最小的,快速排序次之,再次是希尔排序。同时根据各种排序算法的比较次数曲线变化幅度可以得出快速排序和希尔排序的比较次数受记录初始顺序的影响较大,而归并排序的比较次数受到记录初始顺序的影响却很小。

4.3 各种算法的稳定性

根据排序算法稳定性的定义以及各种算法的核心思想及实现可得静态排序、插入排序、起泡排序、选择排序和归并排序是稳定的,而希尔排序与归并排序是不稳定的。

4.4 各种算法的简单性

从算法简单性看,静态排序、插入排序、选择排序和起泡排序是简单算法,而希尔排序、快速排序和归并排序是经过改进后的算法,因此是复杂算法。

5 结 语

数据排序所引起CPU时间开销主要由排序过程中的记录比较次数和移动次数决定。从待排序的记录个数n的大小看,n越小,采用简单排序方法越合适,n越大,采用改进的排序方法越合适。因为n越小,Ο(n2)同Ο(nlog2n)的差距越小,并且输入和调试简单算法比输入和调试改进算法要少用许多时间。 从记录本身信息量看,若记录本身信息量越大,则移动记录所花费的时间就越多,所以对记录的移动次数较多的算法不利。在这种情况下,移动次数越小的算法将越有优势,本文提出的静态排序算法也就是为了更好地适应这种情况而提出的。

起泡排序是最简单的排序算法,在各个算法中平均效率是最低的,但便于理解,适用于记录个数n较小的排序中。

选择排序是一种简单排序算法,它的比较次数非常大,但是移动次数相对较小,所以适用于记录个数n较小而记录本身信息量较大的排序中[5]。

插入排序也是一种简单排序算法,它的比较次数和移动次数都比较大,约为n2/4,适用于记录个数n较小的排序中[6]。

希尔排序中当n在某个特定的范围内时,所需的比较次数约为n1.3,移动次数约为3n1.3,适用于记录个数较大而记录本身信息量较小的排序中[7]。

快速排序的平均时间为klog2n,从平均时间性能而言,快速排序最佳[4],适用于记录个数n较大的排序中[8]。

归并排序的平均时间复杂度为Ο(nlog2n),空间复杂度为О(n),适用于记录个数n较大而记录信息量也较大的排序中[9]。

静态排序是一种稳定的简单排序算法,它的记录比较次数非常大,但移动次数却是所有算法中最小的,并且记录的比较次数和移动次数仅与记录个数n有关而与记录的初始顺序无关,因此适应于记录个数n较小而记录信息量非常大的排序中。

参考文献

[1]阿霍,霍普克劳夫特,乌尔曼.计算机算法的设计与分析[M].黄林鹏,王德俊,张仕,译.机械工业出版社,2007.

[2]科曼,等.算法导论[M].潘金贵,等译.机械工业出版社,2006.

[3]郑宗汉,郑晓明.算法设计与分析[M].电子工业出版社,2010.

[4]严蔚敏,吴伟民.数据结构[M].清华大学出版社,2010.

[5]张明亮,李兴良.选择排序的一种改进及分析[J].苏州科技学院学报,2007,24(2).

[6]李宝艳,马英红.排序算法研究[J].电脑知识与技术,2007,2(8).

[7]杨智明.希尔排序算法实现与分析[J].电脑编程技术与维护,2010(2).

[8]杨锋英,刘会超.改进的快速排序算法[J].科技广场,2010(1).

8.算法设计与分析实验三 篇八

关键词：ACM-ICPC；算法分析与设计；实践教学

中图分类号：G642 文献标志码：B 文章编号：1673-8454（2015）10-0065-03

一、引言

算法分析与设计是面向设计的计算机专业核心课程，主要通过对经典算法的学习和研究，使学生掌握算法的设计策略和算法复杂度的分析方法，培养学生分析和解决实际问题的能力，为开发高效的软件系统奠定了坚实的基础。该课程教学内容繁多，涉及的知识面很广，主要内容包括算法分析方法、递归算法、分治算法、贪心算法、动态规划、回溯算法、分支限界、近似算法、概率算法等经典的算法，覆盖了多项式、数论、矩阵、集合、图论、几何、模式匹配等数值和非数值计算问题。

目前，各高校该课程分配的课时普遍较少，教学方法也都是以讲解为主，即使设置了实验课，在实践环节通常也只是一味地对算法进行验证，很少考虑到算法的运行效率分析、测试数据的规模以及实际的应用场景。学生对算法的学习主要以理解和记忆为主，缺乏对知识的重构和对算法的灵活运用，遇到实际问题便无从下手。而且，在传统实践教学中，学生抄袭代码的情况严重，不能有效提高学生的实践能力，无法体现实践教学的真正作用。在这种教学模式下，学生缺乏对实际问题进行抽象和分析的能力，思维创新和实践能力难以得到有效提高。本文结合我校实际教学情况，将ACM-ICPC竞赛模式与算法分析与设计课程的建设相结合，达到了良好的教学效果。

二、课程现状

算法分析与设计课程的建设在我校起步较晚，我校从2010年开始招收计算机科学与技术专业本科学生，从2012年开始为计算机科学与技术专业学生开设算法分析与设计课程。第一届课程只有理论课，学生缺少实践机会。该课程的开设是面向计算机科学与技术专业大三的学生，学生在学习该课程之前，已经学习了C/C++程序设计、数据结构、Java程序设计、高等数学和离散数学等课程，但是由于学生欠缺良好的计算思维，逻辑分析能力相对不足，编程实践能力仍然比较弱，学生在学习该课程时倍感吃力。

目前，我校在算法分析与设计课程信息化建设方面有许多不足，主要体现在以下几点：

（1）课程之间的联系不够紧密

算法分析与设计课程与其他课程的关系是很密切的，如数据结构，它们之间相互作用，从而提高计算机专业学生的实践能力，为学院培养高素质的应用型人才。由于这些课程的前后都没有很好地衔接，课程之间的重点和难点没有对应上，所以学生在上算法分析与设计课程时需要重新复习之前所学的课程，从而增加了学生学习的工作量。

（2）教学资源不足

当前课程并没有信息化系统的支持。学生只能通过网络搜索所需的资源，获取教师的PPT也只能通过教师，教学资源没有实现整合和共享。

（3）编程竞赛平台不多

程序设计能力的提升需要学生多思考多编程，而这方面实践能力的获取最有效的方式就是竞赛活动。在参加或举办程序设计类竞赛方面，学生只参与了国内的“蓝桥杯”这一个程序设计类竞赛，学院内部并没有开展此类竞赛活动。

三、ACM-ICPC模式下的课程建设

1.ACM-ICPC在课程中的作用

ACM国际大学生程序设计竞赛（ACM-ICPC）是由美国计算机协会（ACM）主办的，是一项旨在展示大学生创新能力、团队精神和在压力下编写程序、分析和解决问题能力的年度竞赛。经过40多年的发展，ACM-ICPC已经发展成为最具影响力的大学生计算机竞赛。竞赛时间为5个小时，重点考察选手的算法和程序设计能力。选手通过网络提交程序，评委负责将结果（正确或出错的类型）通过网络尽快返回给选手。

将ACM-ICPC竞赛模式引入算法分析与设计的教学中，可以激发学生的主动学习积极性，鼓励学生勤思考、多实践，相对于传统的实践教学具有以下几方面的优势：

（1）在网上进行实践教学，没有时间和空间的局限性。教师可以在测评系统中对同一个实验项目布置多个难度各异的题目，学生可以根据自己的掌握情况，从易到难选择合适的时间完成训练题目。学生完成编程提交代码后可以立刻得到评测结果，这样可以激发学生的学习热情。教师也可以分析学生提交程序是否正确或错误，并进行针对性的讲解。

（2）对创造校园的学术交流氛围有良好的促进作用。学生在课余时间通过在网上提交自己编写的程序源代码，自主进行算法和程序的交流，有利于培养学生的学术修养，实现学生与教师、学生与学生之间的交流和互动。

（3）减轻教师实践教学时的指导负担。传统的实践教学在机房进行，教师需要在整个机房进行巡视，为有疑问的同学进行解答。这让教师在实践教学中的指导负担非常繁重，教师的指导范围也不能全面覆盖整个班级，在一定程度上打击了学生的积极性。而ACM-ICPC竞赛模式的在线测评系统可以对学生提交的作业进行评测，大大减轻了教师的负担。

2.测评系统的设计与开发

我们将基于ACM-ICPC竞赛模式的在线测评技术引入算法分析与设计课程的教学中，开发了一个程序在线测评系统。该系统基于Java EE，是一个程序在线评判、程序设计竞赛和交流的平台，可不断扩展题库供学生进行程序设计练习，系统自动对提交的程序源代码进行编译、运行并评判程序的正确性。系统可供课程日常训练和网上实时竞赛使用，也具备站内交流和站内全文检索功能。考虑到后期改进和后续开发的需要，系统的开发采用的是目前主流的MVC架构，使用的是Struts框架。系统有两个版本的评判模块，一个基于纯Java，另一个基于C++，两者均可在Windows平台下运行。

学生在系统提交程序后，系统先将程序保存至数据库，再写入评判队列，由系统评判内核进行编译、运行并返回结果，返回的结果类型有AC、WA、RTE、TLE、PE、MLE、CE。每个题目可能有多个测试数据，内核在读取主系统传递给它的参数后，编译程序，生成可执行文件，之后对于每个测试数据运行一次“验证测试数据”的操作，只有当所有测试数据均验证无误，才返回AC，如果在某次验证返回错误，则返回相应的错误信息，在任何时候遇意外终止将返回RTE。评判内核的程序流程如图1所示。

系统用户分为四种：普通用户、高级用户、论坛版主及系统管理员。任何学生都可注册成为普通用户。普通用户可以做练习题，提交程序并得到系统的评判和结果反馈；可以根据程序提交情况参与用户排名；拥有并可使用自己的站内信箱；可以查看、保存和管理自己提交的源代码；可以在论坛发帖，参与问题讨论；可以参加程序设计竞赛，并查看比赛结果和统计数据。任何解答题目超过20道的普通用户，可自动升级为高级用户。高级用户拥有普通用户的所有权限，还可以上传题目和测试数据，并可对自己上传的题目进行管理、修改等。高级用户上传的题目，经管理员确认后，便可加入系统的正式题库，系统在题目信息中记录上传题目者的相关信息。论坛版主为系统管理员授予，拥有普通用户的所有权限，同时对相应的论坛板块拥有管理权。系统管理员管理系统的日常运行，拥有所有的管理权限，需要对题目和测试数据进行筛选，检查系统运行情况，组织程序设计竞赛。

3.课程设置

结合我校实际情况，我们在算法分析与设计课程的实践教学内容上设计了递归算法、分治算法、动态规划算法、贪心算法、回溯算法、分支界限算法共6个经典算法的实验项目。由于实践教学课时有限，传统的教学方式每个实验项目只能设计2-3道题目。引入ACM-ICPC模式之后，学生可以利用课余时间通过网络完成程序设计，每个实验项目题量增加到6-8个，题目难度各异，学生可以根据自己的知识掌握程度和能力选择合适的时间完成。较容易的题目可以先完成，具有一定的综合性、难度较大的题目，可以在有相当的训练量之后完成。

这种循序渐进的训练方式，更有利于学生对算法原理的理解和掌握，也更有利于形成由浅入深的思维模式，有效提高学生的分析问题、解决问题的能力。测评系统中的部分习题如表1所示。

课程的考核参考学生提交程序的次数、通过率、提交程序的难度等，作为学生平时成绩的考核依据，这样可以鼓励和督促学生积极参与实践。

四、课程建设实践成果

实施ACM-ICPC竞赛模式的程序在线测评系统以后，学生的学习积极性得到了较大的提高。学生对经典算法的掌握程度和实践能力也大大提高了。

学生在各种全国性考试和比赛中取得了较好的成绩。以我校参加“蓝桥杯”全国软件专业人才设计与创业大赛的情况为例，不仅在报名人数上大幅增长，获奖人数和获奖等级也有了明显的提高，具体如图2所示。

在课程的实践教学中，学生设计算法的训练量加大，平均每人每学期完成习题数量为34题，较实施前增长88.9%。学生的自主学习能力有所提高，教师在实验课上的空闲率由原来的0.4%增长到33.3%，学生对教师的依赖程度大大降低。

五、结语

基于ACM-ICPC模式的算法分析与设计课程将理论学习与实际操作相结合，注重培养和提高学生分析和解决实际问题的能力，以公平、公正、公开的竞争形式带动学生的自主学习，调动学生交流和研究的积极性，为课程的开展提供了良好的氛围。在后续的研究和开发中，我们将把基于ACM-ICPC模式的程序测评系统扩展到全系范围内的更多的程序设计类课程。

参考文献：

[1]龚宇平，梁丽.计算机专业大学生创新思维的培养[J].教育与职业，2014（8）.

[2]陆慧.应用型本科高校创新型人才培养存在的问题与对策[J].教育与职业，2013（35）.

[3]赵春风.基于J2EE技术ACM竞赛程序在线评测系统的设计与实现[D].厦门：厦门大学，2013.10.

[4]李华，赵建平，李奇等.基于ACM-ICPC的算法设计与分析课程改革[J].计算机教育，2013（7）.

[5]赵晖，付秀花.计算机语言程序设计课程的教学创新[J].教育与职业，2013（23）.

[6]王伟嘉，张洪萍，宁亚辉等.关于《数据结构》课程与ACM-ICPC竞赛结合的探讨[J].计算机工程与科学，2014（S1）.

[7]芶生平，杨鹏，汪小平等.以ACM/ICPC竞赛为载体 探索课程体系建设与创新人才培养新模式[J].中国大学教学，2010（7）.

[8]ZHU Jie-ao， SUN Mian， LIU Xue， LI Hao. Learning Software Engineering through Experience of ACM-ICPC Training and Practicing Exercises[C].Proceedings of 2010 Third International Conference on Education Technology and Training（Volume 1），2010.11.