数据结构教程第三课算法及算法设计要求

文章作者 100test 发表时间 2007:03:10 18:30:05
来源 100Test.Com百考试题网

本课主题： 算法及算法设计要求

教学目的： 掌握算法的定义及特性，算法设计的要求

教学重点： 算法的特性，算法设计要求

教学难点： 算法设计的要求

授课内容：

一、算法的定义及特性

1、定义：

ispass(int num[4][4])

{ int i,j.
for(i=0.i<4.i )

for(j=0.j<4.j )

if(num[i][j]!=i*4 j 1)/*一条指令，多个操作*/

return 0.

return 1.
}/*上面是一个类似华容道游戏中判断游戏是否结束的算法*/

算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作；此外，一个算法还具有下列五个重要特性：

2、算法的五个特性：

有穷性	一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成；
确定性	算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。有任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。
可行性	一个算法是能行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。
输入	一个算法有零个或多个的输入，这些输入取自于某个特定的对象的集合。
输出	一个算法有一个或多个的输出。这些输出是同输入有着某些特定关系的量。

例：

有穷性	haha() {/*only a joke,do nothing.*/ } main() {printf("请稍等...您将知道世界的未日..."). while(1) haha(). }
确定性	float average(int *a,int num) {int i.long sum=0. for(i=0.isum =*(a ). return sum/num. } main() {int score[10]={1,2,3,4,5,6,7,8,9,0}. printf("%f",average(score,10). }
可行性
输入
输出	getsum(int num) { int i,sum=0. for(i=1.i<=num.i ) sum =i. } /*无输出的算法没有任何意义，