第2章算法及其描述课件.ppt

1、Ahead Institute of Software and Technology第第2章章 算法及其描述算法及其描述 （程序的灵魂）Ahead Institute of Software and Technology2.1 算法2.1.1 什么是算法？算法是对问题的思维方法和过程体现.1.算法的特征:(1)确定性,确定唯一的意义,不能有二意性.(2)有限行,执行时有限时间内结束,解决问题.(3)可行性,控制操作是可实现的.2.算法的结构:(1)顺序结构：。(2)选择结构：如果成立 执行 否则执行。(3)循环结构：重复执行直到成立。Ahead Institute of Software an

2、d Technology2.1.2 算法的描述算法是解决问题的方法和步骤在计算机上的表示 任何问题的求解都有一定的“算法”计算机算法有很大不同 算法是人设计出来的 计算机算法是严谨的,不能有二意性.算法可分为两类：数值运算算法：主要用于科学运算 非数值运算算法：如信息检索、人工智能等Ahead Institute of Software and Technology2.1.3 算法的举例:例：判断任意整数 n（n3）是不是素数？素数是只能被1和自身整除（余数为零）的整数算法分析：用 n 做被除数，依次用 2 到（n 1）之间的各个整数做除数，求所有的余数，如果所有余数都不为零，则n为素数；只要

3、有一个余数为零就可以断定n不是素数算法：1）任意输入n2）令 i=2（i 做除数，i=2,3,.,n-1）3）计算 n/i，得余数 r4）若 r=0，则打印“n不是素数”，转到7；否则继续5）令 i=i+16）若 i=0？输出-n输出n例2-2：输出一个数的绝对值解题思路：1、判断n=0;2、是输出n;否则输出-n.输入 nn=0？是否输出n输出-nAhead Institute of Software and Technology例 算法的举例:例：求s=1+2+3+100问题：求100个整数的和s，结果是s 这100个整数是从1到100的所有自然数算法一：设 s 为累加单元1)将1送到S中

4、；2)把2加到S中（即S中的内容1加2后再送回S中，下同）3)把3加到S中；100)把100加到S中；101)把S中的结果输出。Ahead Institute of Software and Technology1=SS+2=SS+3=SS+100=S输出 S例 用流程图与盒图描述算法1 =SS+2=SS+3 =SS+100 =S输出 SAhead Institute of Software and Technology例：求s=1+2+3+100问题：求100个整数的和s，结果是s 这100个整数是从1到100的所有自然数算法二：设 n 为计数单元，s 为累加单元1)将 0 送到S中，将 0

5、 送到 n 中；2)将 n+1 送到 n 中，再把 n 加到 s 中；3)判断 n 的值是否大于等于100？4)若 n n0=Sn n S+n=S例用流程图与盒图描述算法0=S,nn+1=nS+n=S输出 Sn 100是否Ahead Institute of Software and Technology例2-3 输入10个数，求它们的平均值。例2-4 输入50个学生成绩，统计出不及格的人数。Ahead Institute of Software and Technology例例 求求Fibonacci数列：数列：1，1，2，3，5，8，的前的前40个数个数。F1=1 (n=1)F2=1 (n

6、=2)Fn=Fn-1+Fn-2 (n3)1534233159710946750255142293524578241578171 18 855553773772584258417711177111213931213938320408320405702887570288739088169390881692 213138989610610418141812865728657196418196418134626913462699227465922746563245986632459863 321211441449879876765676546368463683178113178112178309217

7、83091493035214930352102334155102334155/*c5_12.c*/#include main()long int f1,f2;int i;f1=1;f2=1;for(i=1;i=20;i+)printf(%12ld%12ld ,f1,f2);if(i%2=0)printf(n);f1=f1+f2;f2=f2+f1;f1=1,f2=1for i=1 to 20输出输出f1,f2f1=f1+f2f2=f2+f1Ahead Institute of Software and Technology例例 判断判断m是否素数是否素数/*c5_13.c*/#include#i

8、nclude main()int m,i,k;scanf(%d,&m);k=sqrt(m);for(i=2;i=k+1)printf(%d is,m);else printf(%d is not,m);printf(a prime numbern);例例6.9 求求100200间的全部间的全部素数素数读入读入mi=2当当ikm被被i整除整除真真假假用用break结束循环结束循环i=i+1ik+1真真假假输出输出:m”是素数是素数”输出输出:m”不不是素数是素数”k=mAhead Institute of Software and Technology2.2.3流程图应用举例例2-5求Y=1!+

9、3!+5!+49!问题：求1到50之间奇数的阶乘之和.Ahead Institute of Software and Technology2.3伪代码伪代码伪代码的使用伪代码的使用 Usage of Pseudocode伪代码(Pseudocode)是一种算法描述语言。使用为代码的目的是为了使被描述的算法可以容易地以任何一种编程语言(Pascal,C,Java,etc)实现。因此，伪代码必须结构清晰，代码简单，可读性好，并且类似自然语言。下面介绍一种类伪代码的语法规则。伪代码的语法规则伪代码的语法规则在伪代码中，每一条指令占一行(else if 例外，)，指令后不跟任何符号（Pascal和C中

10、语句要以分号结尾）；书写上的“缩进”表示程序中的分支程序结构。这种缩进风格也适用于if-then-else语句。用缩进取代传统Pascal中的begin和end语句来表示程序的块结构可以大大提高代码的清晰性；同一模块的语句有相同的缩进量，次一级模块的语句相对与其父级模块的语句缩进；Ahead Institute of Software and Technology 伪代码表示的算法用传统的流程图和N-S图表示算法直观易懂，但画起来比较费事，在设计一个算法时，可能要反复修改，而修改流程图是比较麻烦的。因此，流程图适宜于表示一个算法，但在设计算法过程中使用不是很理想的(尤其是当算法比较复杂、需要反

11、复修改时)。为了设计算法时方便，常用一种称为伪代码的工具。伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法。它如同一篇文章一样，自上而下地写下来。每一行(或几行)表示一个基本操作。它不用图形符号，因此书写方便、格式紧凑，易懂也便于向计算机语言算法(即程序)过渡。可以用英文、汉字、中英文混合表示算法，以便于书写和阅读为原则。用伪代码写算法并无固定的、严格的语法规则，只要把意思表达清楚，并且书写的格式要写成清晰易读的形式。Ahead Institute of Software and Technology例如：xy x20*(y+1)xy30 以上语句用Pascal分别表示为：x:=y

12、;x:=20*(y+1);x:=30;y:=30;以上语句用C分别表示为：x=y;x=20*(y+1);x=y=30;Ahead Institute of Software and Technology2.3.1 伪代码及其分类自然语言描述（如上）通俗、冗长、易“歧义”1）类 伪代码简洁、易实现、不直观常用语：BEGIN END IFELSE FOR WHILE DO.Ahead Institute of Software and Technology例如：求任意两个数 a 和 b 的和算法：1）输入 a 和 b2）计算 a+b，结果存入 sum3）打印 sum用伪代码表示：BEGININPU

13、T a,ba+b=sumPRINT a,+,b,=,sumENDAhead Institute of Software and Technology2)类 C 伪代码(1)顺序结构:(2)选择结构：if 执行 else (3)循环结构：直到格式 do while 当型格式 while Ahead Institute of Software and Technology2.3.2 用伪代码描述算法例2-6：求s=1+2+3+100问题：求1100之间各个整数的和s算法：算法：sum()y=0,i=1;do y=y+I;i=i+1;while i=100;print y;Ahead Institu

14、te of Software and Technology例2-7:求一个自然数N的阶乘.Factorial()输入N的值;y=1,i=2;While i=Ny=y*i;i=i+1;Print“N!=“,y;Ahead Institute of Software and Technology2.3.3 伪代码应用举例例2-8：求Y=1!+3!+5!+49!问题：求1到50之间奇数的阶乘之和.sumforFactorial()输入N的值;y=1,s=2,i=3;dos=s*i;if INT(i/2)!=i/2;y=y+s;i=i+1;While i=NPrint y;Ahead Institut

15、e of Software and Technology例2-9：分别求1到N之间各奇数之和各偶数之和.Sumforodd&even()输入N的值;Odd=0,even=0;i=1;doif INT(i/2)=i/2;even=even+i;Else odd=odd+i;i=i+1;While i=NPrint odd,even;Ahead Institute of Software and Technology例2-10：将一个数组A1,A2,A3An中的数据按从大到小的顺序进行排序.Sort()i=1;Do j=i+1;Do if A(i)A(j)交换A(i)与 A(j)的值;j=j+1;While j=n i=i+1;While i=n