第二章 程序灵魂—算法(1)

1、第二章第二章 程序的灵魂程序的灵魂算法算法算法的概念算法的概念简单算法举例简单算法举例算法的特性算法的特性怎样表示一个算法怎样表示一个算法结构化程序设计方法结构化程序设计方法2.1 2.1 算法的概念算法的概念算法的定义算法的定义 广义地说，为解决一个问题而采取的方法和广义地说，为解决一个问题而采取的方法和步骤，就称为步骤，就称为“算法算法”。计算机算法的分类计算机算法的分类数值运算算法：求方程的根，求函数的积分等数值运算算法：求方程的根，求函数的积分等非数值运算算法：图书管理，人事管理，行车非数值运算算法：图书管理，人事管理，行车调度等调度等1.2 1.2 简单算法举例简单算法举例步骤步骤1

2、 1：先求：先求1 x 21 x 2，得结果，得结果2 2。步骤步骤2 2：将步骤：将步骤1 1得到的乘积得到的乘积2 2再乘以再乘以3 3，得到结果，得到结果6 6。步骤步骤3 3：将：将6 6再乘以再乘以4 4，得，得2424。步骤步骤4 4：将：将2424再乘以再乘以5 5，得，得120120，这就是最后的结果。，这就是最后的结果。最原始的方法：最原始的方法：54321例例2.1 2.1 求求p1S1:S1:pipS3:S3:i2S2:S2:i1iS4:S4:5i S5:S5:若若 ，返回，返回S3S3；否则，结束。；否则，结束。100321 5 4321 改成把9 7531 5 432

3、1 改成把p : p : 被乘数和每一步骤的乘积被乘数和每一步骤的乘积i: i: 乘数乘数改进的算法：改进的算法：例例2.32.3（1 1） 判定某一给定年份判定某一给定年份y y是否为闰年，是否为闰年，将结果输出将结果输出S1S1： 输入输入y yS2S2： 若若y y不能被不能被4 4整除，则输出整除，则输出y“y“不是闰年不是闰年” ” ，转，转S6S6S3S3： 若若y y能被能被4 4整除，但不能被整除，但不能被100100整除，则输出整除，则输出y y “是闰年是闰年” ” ，转，转S6S6S4S4： 若若y y能被能被100100整除，但又能被整除，但又能被400400整除，则输

4、出整除，则输出y y “是闰年是闰年” ” ，转，转S6S6S5S5：输出：输出y“y“不是闰年不是闰年”S6S6：算法结束：算法结束闰年：闰年：能被能被4 4整除，但不能整除，但不能被被100100整除的年份整除的年份能能100100整除，同时有能被整除，同时有能被400400整除的年份整除的年份非闰年：非闰年：不能被不能被4 4整除的年份整除的年份能能100100整除，但不能被整除，但不能被400400整整除的年份除的年份例例2.3 2.3 判定判定2000-25002000-2500年中的每一年是否为闰年，年中的每一年是否为闰年，将结果输出将结果输出S1S1：S2S2： 若若y y不能被

5、不能被4 4整除，则输出整除，则输出y“y“不是闰年不是闰年”，然后转到，然后转到S6S6S3S3： 若若y y能被能被4 4整除，但不能被整除，但不能被100100整除，则输出整除，则输出y “y “是是 闰年闰年” ” ，然后转到，然后转到S6S6S4S4： 若若y y能被能被100100整除，但又能被整除，但又能被400400整除，则输出整除，则输出y “y “是是 闰年闰年” ” ，然后转到，然后转到S6S6S5S5：输出：输出y“y“不是闰年不是闰年”S6S6：S7S7：当：当 时，转时，转S2S2继续执行，否则，算法停止。继续执行，否则，算法停止。y2000y1y5002yy :

6、y : 被检测的年份被检测的年份例例2.4 2.4 求求1001991.4131211sign 1 :S1sum 1 :S2deno 2 :S3sum termsum :S6deno 1 deno :S7signsign1)( :S4 term (1/deno)sign :S5001 deno S8: S8: 若若 返回返回S4S4，否则算法结束，否则算法结束sum : sum : 累加和累加和deno: deno: 分母分母sign: sign: 符号符号 term: term: 某一项某一项例例2.5 2.5 对于一个大于对于一个大于3 3的正整数，判断它是不是的正整数，判断它是不是 一个

7、素数一个素数素数：除了素数：除了1 1和该数本身之外，不能被其它任何和该数本身之外，不能被其它任何整数整除的数整数整除的数ni i1i1nii2 0r S1S1：输入：输入 n n 的值的值S2S2： （i i 作为除数）作为除数）S3S3：n n 被除被除 i i，得余数得余数 r rS4S4：如果如果 ，则打印则打印 n “n “不是素数不是素数”，算，算法结束；否则执行法结束；否则执行S5S5S5S5：S6S6：如果如果 ，则返回，则返回S3S3；否则打印否则打印 n n “是素数是素数”，然后结束。，然后结束。n : n : 被判断的数被判断的数i: i: 除数除数r: r: 被除数被

8、除数2.3 2.3 算法的特性算法的特性n有穷性有穷性n确定性确定性n有零个或多个输入有零个或多个输入n有一个或多个输出有一个或多个输出n有效性有效性2.4 2.4 怎样表示一个算法怎样表示一个算法用自然语言表示算法用自然语言表示算法用传统流程图表示算法用传统流程图表示算法用用N-SN-S流程图表示算法流程图表示算法用伪代码表示算法用伪代码表示算法用计算机语言表示算法用计算机语言表示算法用流程图表示算法用流程图表示算法流程图是用一些图框表示各种操作流程图是用一些图框表示各种操作起止框起止框输入输出框输入输出框判断框判断框流程线流程线连接点连接点注释框注释框处理框处理框0?x 打印x打印-xYN

9、例例 2.6 2.6 求求5!5!的算法用流程图表示的算法用流程图表示pipi5i1i结束结束开始开始N NY Yi2p1p1S1:S1:pipS3:S3:i2S2:S2:i1iS4:S4:5i S5:S5:若若 ，返回，返回S3S3；否则，结束；否则，结束。例例 2.10 2.10 将判断素数的算法用流程将判断素数的算法用流程图表示图表示输入输入n ni2r的余数inr=0?ni i1i打印n是素数结束结束开始开始打印打印n n不不是素数是素数YNNYi1i1nii2 0rS1S1：输入：输入 n n 的值的值S2S2： （i i 作为除数）作为除数）S3S3：n n 被除被除 i i，得余

10、数得余数 r rS4S4：如果如果 ，则打印则打印 n “n “不是素不是素数数”，算法结束；否则执行，算法结束；否则执行S5S5S5S5：S6S6：如果如果 ，则返回，则返回S3S3；否则打否则打印印 n “n “是素数是素数”，然后结束。，然后结束。 改进的流程图改进的流程图ABabpABba成立成立不成立不成立只有一个入口只有一个入口只有一个出口只有一个出口结构内的每一部分都有机会被执行到结构内的每一部分都有机会被执行到结构内不存在结构内不存在“死循环死循环” 循环结构循环结构 选择结构选择结构 顺序结构顺序结构A1pab成立成立当型循环当型循环2pAab不成立不成立直到型循环直到型循环

11、循环结构举例循环结构举例x1x结束结束开始开始Y YN Nx05x 打印xx1x结束结束开始开始N NY Yx05x 打印x用用N-SN-S流程图表示算法流程图表示算法ABP成立成立不成立不成立AB当当 成立成立1pA直到直到 成立成立2pA 选择结构选择结构 循环结构循环结构 顺序结构顺序结构r=0.08r=0.08r=0.06r=0.06成立成立不成立不成立当当10n 100p pr)(1pAB例例2.11 2.11 求求5!5!的算法用的算法用N-SN-S流程图表示流程图表示打印pp1i2pipi1i直到 i 5i 5pipi5i1i结束结束开始开始N NY Yi2p1打印p例2.15输

12、入输入n ni2r的余数inr=0?r=0?ni i1i打印打印n n是素数是素数结束结束开始开始打印打印n n不不是素数是素数Y YN NN NY Y输入输入n nrin的余数r=0?r=0?i1i打印打印n n是素数是素数开始开始Y YN NN NY Yi2w0ni 1w w=0?w=0?打印打印n n非素数非素数结束结束Y YN Nw1或输入n输出输出n n是素数是素数输出输出n n不是素数不是素数是是否否w=0直到 i 或w 0nw1i1i是是否否r=0n / i 的余数 rw0i2 用伪代码表示算法用伪代码表示算法 伪代码是用介于自然语言和计算机语言之间伪代码是用介于自然语言和计算机

13、语言之间的文字符号来描述算法。的文字符号来描述算法。若若 x x 为正为正 打印打印 x x否则否则 打印打印 - -x xif x if x 为正为正 print xprint xelseelse print -x print -x打印打印 x x 的绝对值的绝对值例例2.16 2.16 将求将求5!5!的算法用伪代码表示的算法用伪代码表示BEIGN(BEIGN(算法开始算法开始) ) while i = 5 while i = 5 print t print tEND(END(算法结束算法结束) )t1i2titi1i用计算机语言表示算法用计算机语言表示算法例例2.20 2.20 将求将求

14、5!5!的算法用的算法用C C语言表示语言表示2.5 2.5 结构化程序设计方法结构化程序设计方法结构化程序设计方法的特点：结构化程序设计方法的特点：n自顶向下自顶向下n逐步细化逐步细化n模块化设计模块化设计n结构化编码结构化编码例例2.22 2.22 将将1-10001-1000之间的素数打印出来之间的素数打印出来把所有非素数去掉把所有非素数去掉打印全部素数打印全部素数输入输入1-n1-nA AB BC C输入输入n ni1ixii1ini 当当A：例例2.102.10将将 去掉去掉当当i i 的整数部分的整数部分i2ixni1i如如 未去掉未去掉，则则 将将 到到 间间全部是全部是 倍数倍数的数去掉的数去掉ix1ixnxix1B2B3BB：D将将 到到 范围内范围内是是 倍数的数去掉倍数的数去掉是是否否1ixnxix0 xiD：E将能将能 被整除的被整除的 去掉去掉j1i当