算法与流程图完整版课件.ppt

《算法与流程图完整版课件.ppt》由会员分享，可在线阅读，更多相关《算法与流程图完整版课件.ppt（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章第二章 算法与流程图算法与流程图1、程序数据结构算法、程序数据结构算法2、简单算法举例、简单算法举例3、算法特性、算法特性4、算法的自然语言表示、算法的自然语言表示5、算法的流程图表示、算法的流程图表示6、算法的伪代码表示、算法的伪代码表示1、程序数据结构算法、程序数据结构算法Niklaus Wirth,Niklaus Wirth,designer of Pascaldesigner of PascalWirth,Niklaus(1976)(in English).Algorithms+Data Structures=Wirth,Niklaus(1976)(in English).Alg

2、orithms+Data Structures=Program.Prentice Hall.0130224189.ISBN 87Program.Prentice Hall.0130224189.ISBN 87程序：为计算机解题编制的程序：为计算机解题编制的程序：为计算机解题编制的程序：为计算机解题编制的一组指令集一组指令集一组指令集一组指令集算法：处理问题的策略算法：处理问题的策略算法：处理问题的策略算法：处理问题的策略数据结构：处理信息的表示数据结构：处理信息的表示数据结构：处理信息的表示数据结构：处理信息的表示Turing AwardTuring Award,1984,19842、简单算法

3、举例、简单算法举例求和：求和：1+1/2+1/3+1/4+1/5+1/100蛮力法：蛮力法：S1:S1:先计算先计算先计算先计算1/2=0.51/2=0.5，再与，再与，再与，再与1 1相加得相加得相加得相加得1.51.5S2:S2:计算计算计算计算1/3=0.333331/3=0.33333，与，与，与，与1.51.5相加得相加得相加得相加得1.833331.83333S3:S3:计算计算计算计算1/4=0.251/4=0.25，与，与，与，与1.833331.83333相加得相加得相加得相加得2.083332.08333S99:S99:计算计算计算计算1/100=0.011/100=0.0

4、1，与，与，与，与5.1773785.177378相加得相加得相加得相加得5.1873785.187378。2、简单算法举例、简单算法举例求和：求和：1+1/2+1/3+1/4+1/5+1/100改进的算法：改进的算法：S1:S1:初始化初始化初始化初始化sum=0,i=1sum=0,i=1S2:S2:如果如果如果如果i i 100100，执行，执行，执行，执行S3S3；否则执行；否则执行；否则执行；否则执行S5S5S3:sum=sum+1/iS3:sum=sum+1/iS4:i=i+1S4:i=i+1，跳转到，跳转到，跳转到，跳转到S2S2S5:S5:输出输出输出输出sumsum，算法结束，

5、算法结束，算法结束，算法结束2、简单算法举例、简单算法举例从从3个数个数A、B、C中找出最大的数。中找出最大的数。算法算法1：S1:S1:如果如果如果如果ABAB，执行，执行，执行，执行S2S2；否则执行；否则执行；否则执行；否则执行S3S3S2:S2:如果如果如果如果ACAC，执行，执行，执行，执行S4S4；否则执行；否则执行；否则执行；否则执行S6S6S3:S3:如果如果如果如果BCBC，执行，执行，执行，执行S5S5；否则执行；否则执行；否则执行；否则执行S6S6S4:S4:输出输出输出输出A AS5:S5:输出输出输出输出B BS6:S6:输出输出输出输出C C2、简单算法举例、简单算

6、法举例从从3个数个数A、B、C中找出最大的数。中找出最大的数。算法算法2：S1:S1:初始化初始化初始化初始化max=Amax=AS2:S2:如果如果如果如果ABAB，执行，执行，执行，执行S3S3；否则；否则；否则；否则max=Bmax=B，执行，执行，执行，执行S3S3S3:S3:如果如果如果如果maxCmaxC，执行，执行，执行，执行S4S4；否则；否则；否则；否则max=Cmax=C，执行，执行，执行，执行S4S4S4:S4:输出输出输出输出maxmax算法的五个特点：算法的五个特点：有输入有输入有输入有输入 (Input)(Input)：零个零个零个零个或多个输入。或多个输入。或多个

7、输入。或多个输入。有输出有输出有输出有输出 (Output)(Output)：一个一个一个一个或多个输出。或多个输出。或多个输出。或多个输出。有穷性有穷性有穷性有穷性 (Finiteness)(Finiteness)：对于任意一组合法的输入：对于任意一组合法的输入：对于任意一组合法的输入：对于任意一组合法的输入值，在执行有穷步骤之后一定能结束。值，在执行有穷步骤之后一定能结束。值，在执行有穷步骤之后一定能结束。值，在执行有穷步骤之后一定能结束。可行性可行性可行性可行性 (EffectivenessEffectiveness)：所有操作都可通过已：所有操作都可通过已：所有操作都可通过已：所有操作

8、都可通过已经实现的经实现的经实现的经实现的基本操作基本操作基本操作基本操作运算有限次来实现。运算有限次来实现。运算有限次来实现。运算有限次来实现。确定性确定性确定性确定性 (DefinitenessDefiniteness)：算法中每一步的描述都：算法中每一步的描述都：算法中每一步的描述都：算法中每一步的描述都无二义性无二义性无二义性无二义性，只要输入相同，初始状态相同，无，只要输入相同，初始状态相同，无，只要输入相同，初始状态相同，无，只要输入相同，初始状态相同，无论执行多少遍，结果都应该相同。论执行多少遍，结果都应该相同。论执行多少遍，结果都应该相同。论执行多少遍，结果都应该相同。Turi

9、ngAward,19743、算法的特性、算法的特性“好好”算法的特点：算法的特点：正确性正确性正确性正确性 (Correctness)(Correctness)：满足问题的需求。：满足问题的需求。：满足问题的需求。：满足问题的需求。易读性易读性易读性易读性(Readability)(Readability)：便于理解、测试和修改。：便于理解、测试和修改。：便于理解、测试和修改。：便于理解、测试和修改。健壮性健壮性健壮性健壮性(Robustness)(Robustness)：输入非法数据时，算法能：输入非法数据时，算法能：输入非法数据时，算法能：输入非法数据时，算法能做出适当处理，不会产生难以预

10、料的结果。做出适当处理，不会产生难以预料的结果。做出适当处理，不会产生难以预料的结果。做出适当处理，不会产生难以预料的结果。时空效率时空效率时空效率时空效率 (Efficiency)(Efficiency)：执行时间短，低存储。：执行时间短，低存储。：执行时间短，低存储。：执行时间短，低存储。3、算法的特性、算法的特性4、算法的自然语言表示、算法的自然语言表示 优点优点 通俗易懂通俗易懂通俗易懂通俗易懂 缺点缺点 文字冗长、不直文字冗长、不直文字冗长、不直文字冗长、不直观观观观 不适合描述分支不适合描述分支不适合描述分支不适合描述分支循环结构循环结构循环结构循环结构从从3个数个数A、B、C中找

11、出最大的数。中找出最大的数。S1:如果AB，执行S2；否则执行S3S2:如果AC，执行S4；否则执行S6S3:如果BC，执行S5；否则执行S6S4:输出AS5:输出BS6:输出C5、算法的流程图表示算法的流程图表示 从从3个数个数A、B、C中找出最大中找出最大的数。的数。开始开始结束结束输入输入A,B,CABACCB输出输出B输出输出C输出输出A是是是是是是否否否否否否5.1 流程图基本单元流程图基本单元起止框起止框输入输入/输出框输出框处理框处理框判断框判断框流程线流程线5.2 流程图绘制例流程图绘制例输入50个学生的姓名和成绩，输出不及格学生的名单。开始开始结束结束i=1输入输入ni,si

12、i50是是i=1si50是是i=i+1否否是是否否否否5.2 流程图绘制例流程图绘制例输入50个学生的姓名和成绩，输出不及格学生的名单。开始开始结束结束i=1输入输入ni,sii50是是i=1si50是是i=i+1否否是是否否否否5.3 三种基本结构对应流程图三种基本结构对应流程图（1）顺序结构）顺序结构AB5.3 三种基本结构对应流程图三种基本结构对应流程图（2）选择结构）选择结构ABp是是否否5.3 三种基本结构对应流程图三种基本结构对应流程图（3）循环结构：当型）循环结构：当型 while(p)B;Bp是是否否5.3 三种基本结构对应流程图三种基本结构对应流程图（3）循环结构：直到型）循

13、环结构：直到型 do B;while(p);Bp是是否否5.4 作业作业（1）用流程图表示判断闰年的算法。）用流程图表示判断闰年的算法。（2）用流程图表示判断一个正整数是否是素）用流程图表示判断一个正整数是否是素数的算法。数的算法。5.5 用伪代码表示算法用伪代码表示算法 用介于自然语言和计算机语言之间的文字和用介于自然语言和计算机语言之间的文字和符号表示算法符号表示算法 无固定严格的语法规则无固定严格的语法规则 beginendbeginend ifelseifelse dowhiledowhile whilewhile=，=input,printinput,print例如：求和算法的伪代码

14、例如：求和算法的伪代码1+1/2+1/3+1/4+1/5+1/100beginsum=0i=1while(i 100)beginsum=sum+1/ii=i+1endprint sumend本章小结本章小结“好好”算法的特点算法的特点 算法的流程图表示算法的流程图表示如图所示是一算法的伪代码，执行此算法时，输出的结果是在音乐唱片超市里，每张唱片售价25元，顾客购买5张(含5张)以上但不足10张唱片，则按九折收费，顾客购买10张以上(含10张)唱片，则按八五折收费，编写程序，输入顾客购买唱片的数量a，输出顾客要缴纳的金额C.并画出程序框图【解析】试题分析：根据题意写出分段函数，根据分段函数写出程

15、序框图，注意分段函数需要条件分支结构实现，根据框图再写出程序.试题解析：由题意得C程序如下：以下是某次考试中某班15名同学的数学成绩：72,91,58,63,84,88,90,55,61,73,64,77,82,94,60.要求将80分以上的同学的平均分求出来画出程序框图解析】试题分析：根据算法的三种结构的特点，结合本题的要求，我们可以用条件结构来判断成绩是否高于80分，用循环结构控制输入的次数，同时引进两个累加变量，分别计算高于80分的成绩的总和和人数试题解析：用条件结构来判断成绩是否高于80分，用循环结构控制输入的次数，同时引进两个累加变量S、m，分别计算高于80分的成绩的总和S和人数m.程序框图如图所示：