第2章算法及其描述课件

第2章算法及其描述

（程序的灵魂）第2章算法及其描述12.1算法

2.1.1什么是算法？算法是对问题的思维方法和过程体现.1.算法的特征:(1)确定性,确定唯一的意义,不能有二意性.(2)有限行,执行时有限时间内结束,解决问题.(3)可行性,控制操作是可实现的.2.算法的结构:(1)顺序结构：<操作1><操作2><操作3>。(2)选择结构：如果<条件>成立执行<操作1>

否则执行<操作2>。(3)循环结构：重复执行<操作>直到<条件>成立。2.1算法

2.1.1什么是算法？算法是对问题的思维方22.1.2算法的描述算法是解决问题的方法和步骤在计算机上的表示任何问题的求解都有一定的“算法”计算机算法有很大不同算法是人设计出来的计算机算法是严谨的,不能有二意性.算法可分为两类：数值运算算法：主要用于科学运算非数值运算算法：如信息检索、人工智能等2.1.2算法的描述算法是解决问题的方法和步骤在计算机上32.1.3算法的举例:

例：判断任意整数n（n≥3）是不是素数？素数是只能被1和自身整除（余数为零）的整数算法分析：用n做被除数，依次用2到（n–1）之间的各个整数做除数，求所有的余数，如果所有余数都不为零，则n为素数；只要有一个余数为零就可以断定n不是素数算法：1）任意输入n2）令i=2（i做除数，i=2,3,...,n-1）3）计算n/i，得余数r4）若r=0，则打印“n不是素数”，转到7；否则继续5）令i=i+16）若i<n，转到3；否则打印“n是素数”7）算法结束2.1.3算法的举例:

例：判断任意整数n（n≥3）4算法的举例:例2-1：求Y=1!+3!+5!+……+49!问题：求1到50之间奇数的阶乘之和.(1)问题分析:理解奇数阶乘的求和.(2)算法描述:Y表示求和,S表示每一个阶乘,I阶乘的序号.(3)算法的说明:1)意为Y=1!2)意为S=2!3)令I=34)S=S*I=I!5)INT(I/2)!=I/2I!为奇数的阶乘，加入到Y中.6)I加1.7)返回4)进行4),5),6)步;直到I=50,输出结果算法结束.算法的举例:例2-1：求Y=1!+3!+5!+…52.2流程图2.2.1流程图及其分类1.传统流程图起止框处理框输入/出框判断框流程线基本图件2.2流程图起止框处理框输入/出框判断框流程线基本图件6三种基本结构（1966年，Bohra和Jacopini提出）（1）顺序结构（2）选择（分支）结构ABC顺序结构ABCP二路分支结构三种基本结构（1966年，Bohra和Jacopini提出）7（3）循环结构当型循环（先判断后执行，执行次数可能为0）

直到型循环（先执行后判断，至少执行1次）ABCP当型循环否是ABCP直到型循环是否（3）循环结构ABCP当型循环否是ABCP直到型循环是否8三种基本结构的特点：只有一个入口只有一个出口具有结构化的特征应避免流程线的交叉三种基本结构的特点：92.N-S盒图1973年由美国的I.Nassi和B.Shneidermen提出特点：1）不使用流程线（箭头）；2）全部算法写在一个大的矩形框内；3）搭积木方式，真正的结构化。2.N-S盒图1973年由美国的I.Nassi和10三种基本结构A操作B操作顺序结构P是否AB分支结构P条件满足A循环体当型循环PA直到型循环只允许“从上边入，从下边出”三种基本结构A操作B操作顺序结构P是否AB分支结构P条件满足11输入nN>=0？输出-n输出n例2-2：输出一个数的绝对值解题思路：1、判断n>=0; 2、是输出n;否则输出-n.输入nn>=0？是否输出n输出-n输入nN>=0？输出-n输出n例2-2：输出一个数的绝对值解12例算法的举例:例：求s=1+2+3+……+100问题：求100个整数的和s，结果是s

这100个整数是从1到100的所有自然数算法一：设s为累加单元1)将1送到S中；2)把2加到S中（即S中的内容1加2后再送回S中，下同）3)把3加到S中；……100)把100加到S中；101)把S中的结果输出。例算法的举例:算法一：设s为累加单元131=>SS+2=>SS+3=>SS+100=>S输出S例用流程图与盒图描述算法1=>SS+2=>SS+3=>S…………S+100=>S输出S1=>SS+2=>SS+3=>SS+100=>14例：求s=1+2+3+……+100问题：求100个整数的和s，结果是s

这100个整数是从1到100的所有自然数算法二：设n为计数单元，s为累加单元1)将0送到S中，将0送到n中；2)将n+1送到n中，再把n加到s中；3)判断n的值是否大于等于100？4)若n<100，转到2；否则向下进行；5）输出s中的内容。例：求s=1+2+3+……+100算法二150=>n0=>Sn<100输出Sn+1=>nS+n=>S例用流程图与盒图描述算法0=>S,nn+1=>nS+n=>S输出Sn<100是否0=>nn<100输出Sn+1=>n16例2-3输入10个数，求它们的平均值。例2-4输入50个学生成绩，统计出不及格的人数。例2-3输入10个数，求它们的平均值。17例求Fibonacci数列：1，1，2，3，5，8，……的前40个数。

F1=1(n=1)F2=1(n=2)Fn=Fn-1+Fn-2(n≥3)1534233159710946750255142293524578241578171855377258417711121393832040570288739088169213896104181286571964181346269922746563245986321144987676546368317811217830914930352102334155/*c5_12.c*/#include<stdio.h>main(){longintf1,f2;inti;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=1fori=1to20输出f1,f2f1=f1+f2f2=f2+f1例求Fibonacci数列：1，1，2，3，5，8，……的18例判断m是否素数/*c5_13.c*/#include<stdio.h>#include<math.h>main(){intm,i,k;scanf("%d",&m);k=sqrt(m);

for(i=2;i<=k;i++)if(m%i==0)break;if(i>=k+1)printf("%dis",m);elseprintf("%disnot",m);printf("aprimenumber\n");}例6.9求100~200间的全部素数读入mi=2当i≤km被i整除真假用break结束循环i=i+1i≥k+1真假输出:m”是素数”输出:m”不是素数”k=m例判断m是否素数/*c5_13.c*/例6.9求10192.2.3流程图应用举例例2-5求Y=1!+3!+5!+……+49!问题：求1到50之间奇数的阶乘之和.2.2.3流程图应用举例例2-5求Y=1!+3!+202.3伪代码伪代码的使用UsageofPseudocode

伪代码(Pseudocode)是一种算法描述语言。使用为代码的目的是为了使被描述的算法可以容易地以任何一种编程语言(Pascal,C,Java,etc)实现。因此，伪代码必须结构清晰，代码简单，可读性好，并且类似自然语言。

下面介绍一种类伪代码的语法规则。

伪代码的语法规则

在伪代码中，每一条指令占一行(elseif例外，)，指令后不跟任何符号（Pascal和C中语句要以分号结尾）；书写上的“缩进”表示程序中的分支程序结构。这种缩进风格也适用于if-then-else语句。用缩进取代传统Pascal中的begin和end语句来表示程序的块结构可以大大提高代码的清晰性；同一模块的语句有相同的缩进量，次一级模块的语句相对与其父级模块的语句缩进；2.3伪代码伪代码的使用UsageofPseudoco21伪代码表示的算法

用传统的流程图和N-S图表示算法直观易懂，但画起来比较费事，在设计一个算法时，可能要反复修改，而修改流程图是比较麻烦的。因此，流程图适宜于表示一个算法，但在设计算法过程中使用不是很理想的(尤其是当算法比较复杂、需要反复修改时)。为了设计算法时方便，常用一种称为伪代码的工具。伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法。它如同一篇文章一样，自上而下地写下来。每一行(或几行)表示一个基本操作。它不用图形符号，因此书写方便、格式紧凑，易懂也便于向计算机语言算法(即程序)过渡。可以用英文、汉字、中英文混合表示算法，以便于书写和阅读为原则。用伪代码写算法并无固定的、严格的语法规则，只要把意思表达清楚，并且书写的格式要写成清晰易读的形式。伪代码表示的算法

用传统的流程图和N-S图表示算法直观22例如：

x←y

x←20*(y+1)

x←y←30

以上语句用Pascal分别表示为：

x:=y;

x:=20*(y+1);

x:=30;y:=30;

以上语句用C分别表示为：

x=y;

x=20*(y+1);

x=y=30;

例如：

x←y

x←20*(y+1)

x←y←30

232.3.1伪代码及其分类自然语言描述（如上）通俗、冗长、易“歧义”1）类Pascal伪代码 简洁、易实现、不直观常用语：BEGINENDIF…ELSEFORWHILEDO….2.3.1伪代码及其分类24例如：求任意两个数a和b的和算法： 1）输入a和b 2）计算a+b，结果存入sum 3）打印sum用伪代码表示：

BEGIN INPUTa,b a+b=>sum PRINTa,'+',b,'=',sum END例如：求任意两个数a和b的和252)类C伪代码(1)顺序结构:…<操作1><操作2>…(2)选择结构：if<条件>{

执行<操作1>}else {<操作2> }(3)循环结构：直到格式do{<操作>}while<条件>

当型格式while<条件>{<操作>}2)类C伪代码(1)顺序结构:…262.3.2用伪代码描述算法例2-6：求s=1+2+3+……+100问题：求1~100之间各个整数的和s算法：sum(){y=0,i=1;do{y=y+I;i=i+1;}whilei<=100;printy;}2.3.2用伪代码描述算法算法：27例2-7:求一个自然数N的阶乘.Factorial(){输入N的值;y=1,i=2;Whilei<=N{y=y*i;i=i+1;}Print“N!=“,y;}例2-7:求一个自然数N的阶乘.282.3.3伪代码应用举例例2-8：求Y=1!+3!+5!+……+49!问题：求1到50之间奇数的阶乘之和.sumforFactorial(){输入N的值;y=1,s=2,i=3;do{s=s*i;ifINT(i/2)!=i/2;{y=y+s;}i=i+1;}Whilei<=NPrinty;}2.3.3伪代码应用举例例2-8：求Y=1!+3!29例2-9：分别求1到N之间各奇数之和各偶数之和.Sumforodd&even(){输入N的值;Odd=0,even=0;i=1;do{ifINT(i/2)=i/2;{even=even+i;}Else{odd=odd+i;}i=i+1;}Whilei<=NPrintodd,even;}例2-9：分别求1到N之间各奇数之和各偶数之和.30例2-10：将一个数组A1,A2,A3…An中的数据按从大到小的顺序进行排序.Sort(){i=1;Do{j=i+1;Do{ifA(i)<A(j){

交换A(i)与A(j)的值;}j=j+1;}Whilej<=ni=i+1;}Whilei<=n}例2-10：将一个数组A1,A2,A3…An中的数据按从大到31第2章算法及其描述

（程序的灵魂）第2章算法及其描述322.1算法

2.1.1什么是算法？算法是对问题的思维方法和过程体现.1.算法的特征:(1)确定性,确定唯一的意义,不能有二意性.(2)有限行,执行时有限时间内结束,解决问题.(3)可行性,控制操作是可实现的.2.算法的结构:(1)顺序结构：<操作1><操作2><操作3>。(2)选择结构：如果<条件>成立执行<操作1>

否则执行<操作2>。(3)循环结构：重复执行<操作>直到<条件>成立。2.1算法

2.1.1什么是算法？算法是对问题的思维方332.1.2算法的描述算法是解决问题的方法和步骤在计算机上的表示任何问题的求解都有一定的“算法”计算机算法有很大不同算法是人设计出来的计算机算法是严谨的,不能有二意性.算法可分为两类：数值运算算法：主要用于科学运算非数值运算算法：如信息检索、人工智能等2.1.2算法的描述算法是解决问题的方法和步骤在计算机上342.1.3算法的举例:

例：判断任意整数n（n≥3）是不是素数？素数是只能被1和自身整除（余数为零）的整数算法分析：用n做被除数，依次用2到（n–1）之间的各个整数做除数，求所有的余数，如果所有余数都不为零，则n为素数；只要有一个余数为零就可以断定n不是素数算法：1）任意输入n2）令i=2（i做除数，i=2,3,...,n-1）3）计算n/i，得余数r4）若r=0，则打印“n不是素数”，转到7；否则继续5）令i=i+16）若i<n，转到3；否则打印“n是素数”7）算法结束2.1.3算法的举例:

例：判断任意整数n（n≥3）35算法的举例:例2-1：求Y=1!+3!+5!+……+49!问题：求1到50之间奇数的阶乘之和.(1)问题分析:理解奇数阶乘的求和.(2)算法描述:Y表示求和,S表示每一个阶乘,I阶乘的序号.(3)算法的说明:1)意为Y=1!2)意为S=2!3)令I=34)S=S*I=I!5)INT(I/2)!=I/2I!为奇数的阶乘，加入到Y中.6)I加1.7)返回4)进行4),5),6)步;直到I=50,输出结果算法结束.算法的举例:例2-1：求Y=1!+3!+5!+…362.2流程图2.2.1流程图及其分类1.传统流程图起止框处理框输入/出框判断框流程线基本图件2.2流程图起止框处理框输入/出框判断框流程线基本图件37三种基本结构（1966年，Bohra和Jacopini提出）（1）顺序结构（2）选择（分支）结构ABC顺序结构ABCP二路分支结构三种基本结构（1966年，Bohra和Jacopini提出）38（3）循环结构当型循环（先判断后执行，执行次数可能为0）

直到型循环（先执行后判断，至少执行1次）ABCP当型循环否是ABCP直到型循环是否（3）循环结构ABCP当型循环否是ABCP直到型循环是否39三种基本结构的特点：只有一个入口只有一个出口具有结构化的特征应避免流程线的交叉三种基本结构的特点：402.N-S盒图1973年由美国的I.Nassi和B.Shneidermen提出特点：1）不使用流程线（箭头）；2）全部算法写在一个大的矩形框内；3）搭积木方式，真正的结构化。2.N-S盒图1973年由美国的I.Nassi和41三种基本结构A操作B操作顺序结构P是否AB分支结构P条件满足A循环体当型循环PA直到型循环只允许“从上边入，从下边出”三种基本结构A操作B操作顺序结构P是否AB分支结构P条件满足42输入nN>=0？输出-n输出n例2-2：输出一个数的绝对值解题思路：1、判断n>=0; 2、是输出n;否则输出-n.输入nn>=0？是否输出n输出-n输入nN>=0？输出-n输出n例2-2：输出一个数的绝对值解43例算法的举例:例：求s=1+2+3+……+100问题：求100个整数的和s，结果是s

这100个整数是从1到100的所有自然数算法一：设s为累加单元1)将1送到S中；2)把2加到S中（即S中的内容1加2后再送回S中，下同）3)把3加到S中；……100)把100加到S中；101)把S中的结果输出。例算法的举例:算法一：设s为累加单元441=>SS+2=>SS+3=>SS+100=>S输出S例用流程图与盒图描述算法1=>SS+2=>SS+3=>S…………S+100=>S输出S1=>SS+2=>SS+3=>SS+100=>45例：求s=1+2+3+……+100问题：求100个整数的和s，结果是s

这100个整数是从1到100的所有自然数算法二：设n为计数单元，s为累加单元1)将0送到S中，将0送到n中；2)将n+1送到n中，再把n加到s中；3)判断n的值是否大于等于100？4)若n<100，转到2；否则向下进行；5）输出s中的内容。例：求s=1+2+3+……+100算法二460=>n0=>Sn<100输出Sn+1=>nS+n=>S例用流程图与盒图描述算法0=>S,nn+1=>nS+n=>S输出Sn<100是否0=>nn<100输出Sn+1=>n47例2-3输入10个数，求它们的平均值。例2-4输入50个学生成绩，统计出不及格的人数。例2-3输入10个数，求它们的平均值。48例求Fibonacci数列：1，1，2，3，5，8，……的前40个数。

F1=1(n=1)F2=1(n=2)Fn=Fn-1+Fn-2(n≥3)1534233159710946750255142293524578241578171855377258417711121393832040570288739088169213896104181286571964181346269922746563245986321144987676546368317811217830914930352102334155/*c5_12.c*/#include<stdio.h>main(){longintf1,f2;inti;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=1fori=1to20输出f1,f2f1=f1+f2f2=f2+f1例求Fibonacci数列：1，1，2，3，5，8，……的49例判断m是否素数/*c5_13.c*/#include<stdio.h>#include<math.h>main(){intm,i,k;scanf("%d",&m);k=sqrt(m);

for(i=2;i<=k;i++)if(m%i==0)break;if(i>=k+1)printf("%dis",m);elseprintf("%disnot",m);printf("aprimenumber\n");}例6.9求100~200间的全部素数读入mi=2当i≤km被i整除真假用break结束循环i=i+1i≥k+1真假输出:m”是素数”输出:m”不是素数”k=m例判断m是否素数/*c5_13.c*/例6.9求10502.2.3流程图应用举例例2-5求Y=1!+3!+5!+……+49!问题：求1到50之间奇数的阶乘之和.2.2.3流程图应用举例例2-5求Y=1!+3!+512.3伪代码伪代码的使用UsageofPseudocode

伪代码(Pseudocode)是一种算法描述语言。使用为代码的目的是为了使被描述的算法可以容易地以任何一种编程语言(Pascal,C,Java,etc)实现。因此，伪代码必须结构清晰，代码简单，可读性好，并且类似自然语言。

下面介绍一种类伪代码的语法规则。

伪代码的语法规则

在伪代码中，每一条指令占一行(elseif例外，)，指令后不跟任何符号（Pascal和C中语句要以分号结尾）；书写上的“缩进”表示程序中的分支程序结构。这种缩进风格也适用于if-then-else语句。用缩进取代传统Pascal中的begin和end语句来表示程序的块结构可以大大提高代码的清晰性；同一模块的语句有相同的缩进量，次一级模块的语句相对与其父级模块的语句缩进；2.3伪代码伪代码的使用UsageofPseudoco52伪代码表示的算法

用传统的流程图和N-S图表示算法直观易懂，但画起来比较费事，在设计一个算法时，可能要反复修改，而修改流程图是比较麻烦的。因此，流程图适宜于表示一个算法，但在设计算法过程中使用不是很理想的(尤其是当算法比较复杂、需要反复修改时)。为了设计算法时方便，常用一种称为伪代码的工具。伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法。它如同一篇文章一样，自上而下地写下来。每一行(或几行)表示一个基本操作。它不用图形符号，因此书写方便、格式紧凑，易懂也便于向计算机语言算法(即程序)过渡。可以用英文、汉字、中英文混合表示算法，以便于书写和阅读为原则。用伪代码写算法并无固定的、严格的语法规则，只要把意思表达清楚，并且书写的格式要写成清晰易读的形式。伪代码表示的算法

用传统的流程图和N-S图表示算法直观53例如：

x←y

x←20*(y+1)

x←y←30

以上语句用Pascal分别表示为：

x:=y;

x:=20*(y+1);

x:=30;y:=30;

以上语句用C分别表示为：

x=y;

x=20*(y+1);

x=y=30;

例如：

x←y

x←20*(y+1)

x←y←30

542.3.1伪代码及其分类自然语言描述（如上）通俗、冗长、易“歧义”1）类Pascal伪代码 简洁、易实现、不直观常用语：BEGINENDIF…ELSEFORWHILEDO….2.3.1伪代码及其分类55例如：求任意两个数a和b的和算法： 1）输入a和b 2）计算a+b，结果存入sum 3）打印sum用伪代码表示：

BEGIN INPUTa,b a+b=>sum PRINTa,'+',b,'=',sum END例如：求任意两个数a和b的和562)类C伪代码(1)顺序结构:…<操作1><操作2>…(2)选择