第02章C语言算法

1、1介绍有关算法的概念、特征及表示方法，要求掌握各种算法的描述介绍有关算法的概念、特征及表示方法，要求掌握各种算法的描述方法。方法。教学目的：教学目的：本章重点：本章重点： 程序流程程序流程 算法描述方法算法描述方法 教学内容：教学内容： 算法的基本概念算法的基本概念 算法的特征算法的特征 算法的表示方法（流程图）算法的表示方法（流程图） 简单算法举例简单算法举例第二章第二章 程序的灵魂程序的灵魂-算法算法2做任何事情都有一定的步骤：做任何事情都有一定的步骤：3实际实际 问题问题 求解求解 编制编制 问题问题问题问题 模型模型 算法算法 程序程序 实现实现分析分析抽象抽象模型模型求解求解命令命令

2、编程编程调试调试程序程序计算机求解问题步骤计算机求解问题步骤4程序程序 （ Program） 是为解决某个问题用计算机语言或命令设计、是为解决某个问题用计算机语言或命令设计、 编写的一系列指令的有序集合。编写的一系列指令的有序集合。 是人的思维活动的代码化描述。是人的思维活动的代码化描述。程序的顺序执行程序的顺序执行 一个程序通常分为若干个具有一定独立性的程序一个程序通常分为若干个具有一定独立性的程序段，这些程序段是按逻辑步骤编排执行的，只有段，这些程序段是按逻辑步骤编排执行的，只有当当前程序段执行完成后，才将控制权转交到下当当前程序段执行完成后，才将控制权转交到下一个程序段并执行下一个程序段

3、。一个程序段并执行下一个程序段。5一个程序应包括以下几方面内容：一个程序应包括以下几方面内容：（1）对数据的描述。指定数据的类型和组织形式，）对数据的描述。指定数据的类型和组织形式，即数据结构。即数据结构。（2）对操作的描述。即操作步骤（算法）。）对操作的描述。即操作步骤（算法）。（3）采用某种程序设计方法进行设计。）采用某种程序设计方法进行设计。（4）采用某一种计算机语言来表示。）采用某一种计算机语言来表示。6程序程序 = 算法算法+数据结构数据结构+程序设计方法程序设计方法+语言工具和环境语言工具和环境l 在这四个方面中，算法是灵魂，数据结构是加工对象，在这四个方面中，算法是灵魂，数据结构

4、是加工对象，语言是工具，编程需采用合适的方法。语言是工具，编程需采用合适的方法。l 算法是解决算法是解决“做什么做什么”和和“怎么做怎么做”的问题的问题7程序设计的过程：程序设计的过程： 问题的分析问题的分析 算法的设计算法的设计 流程的描述流程的描述 调试与运行调试与运行8买电视机的步骤：选好货物开票付款拿发票取货回家考大学上大学的步骤填报名单交报名费拿准考证参加考试得到录取通知书报到注册9算法的定义算法的定义:l 广义上说：广义上说：为解决一个问题而采取的方法和步骤。为解决一个问题而采取的方法和步骤。l 侠义上说：侠义上说：是指在有限步内解决一个具体问题而规定是指在有限步内解决一个具体问题

5、而规定的意义明确的解题步骤的有限集合。的意义明确的解题步骤的有限集合。l 概括地说：概括地说：算法是指解题方案的准确而完整的描述。算法是指解题方案的准确而完整的描述。从程序来说，也可以说算法是一个有限条指令的集合，从程序来说，也可以说算法是一个有限条指令的集合，这些指令确定了解决某一特定类型问题的运算序列。这些指令确定了解决某一特定类型问题的运算序列。 10例例2.1 求求12345。可先写出这样的算法：可先写出这样的算法：（1）先求）先求12，得到结果，得到结果2；（2）将步骤）将步骤1得到的结果再乘以得到的结果再乘以3，得到结果，得到结果6；（3）将）将6再乘以再乘以4，得到，得到24；（

6、4）将）将24再乘以再乘以5，得到，得到120。11求求12345上述算法太繁琐，我们找一种通用的表示方法。上述算法太繁琐，我们找一种通用的表示方法。S1S1：设变量：设变量p p，代表被乘数，代表被乘数，p=1p=1S2S2：设变量：设变量i i，代表乘数，代表乘数，i=2i=2S3S3：使：使p pi i，乘积放在被乘数变量，乘积放在被乘数变量p p中，可表示为中，可表示为 p pi i p pS4S4：使：使i i的值加的值加1 1，即，即i+1 i+1 i iS5S5：如果如果i i不大于不大于5 5，返回重新执行步骤，返回重新执行步骤s3s3以及其后的以及其后的s4s4、s5s5；否

7、则，算法结束否则，算法结束。最后得到的。最后得到的p p就是就是5! 5! 的值。的值。12求求13579 11如果题目改为求如果题目改为求1 13 35 57 79 9 1111。上述算法稍作改动：上述算法稍作改动：S1S1：1 1 p pS2S2：3 3 i iS3S3：p p i i p pS4S4：i+2 i+2 i iS5S5：若：若i i 1111，返回，返回s3s3；否则，结束。；否则，结束。 可以看出，用这种方法表示的算可以看出，用这种方法表示的算法具有通用性、灵活性。法具有通用性、灵活性。S3到到s5 组组成一个循环，在实现算法时，要反复成一个循环，在实现算法时，要反复多次执

8、行多次执行s3、s4、s5等步骤，直到等步骤，直到某一时刻，执行某一时刻，执行s5步骤时经过判断，步骤时经过判断，乘数乘数i已超过规定的数值而不返回已超过规定的数值而不返回s3步骤为止。步骤为止。 计算机实现循环是轻而易举的。计算机实现循环是轻而易举的。13例例2.2例例2.22.2：有有5050个学生，要求将他们之中成绩在个学生，要求将他们之中成绩在8080分以上者打印出来。分以上者打印出来。解：解：用用n n表示学生学号，表示学生学号，n n1 1代表第一个学生学号，代表第一个学生学号，n ni i 代表第代表第i i 个学生学号。用个学生学号。用g g代表学生成绩，代表学生成绩，g gi

9、 i代表第代表第i i个学生成绩，算法表示如下：个学生成绩，算法表示如下：14例例2.2S1: 1 S1: 1 i;i;S2: S2: 如果如果g gi i 80,80,则打印则打印n ni i和和g gi i, ,否则不打印。否则不打印。S3: i+1 S3: i+1 i;i;S4: S4: 如果如果i i 50,50,返回返回s2,s2,继续执行，否则算法结束。继续执行，否则算法结束。本例中，变量本例中，变量i i作为下标，用它来控制序号（第几个作为下标，用它来控制序号（第几个学生，第几个成绩）。当学生，第几个成绩）。当 i i超过超过5050时，表示已对时，表示已对5050个学生的成绩处

10、理完毕，算法结束。个学生的成绩处理完毕，算法结束。15例例 2.3 例例 2.32.3：判断判断20002000年年-2500-2500年中的每一年是否闰年中的每一年是否闰年，将结果输出。年，将结果输出。 解：解：闰年的条件是：闰年的条件是：(1)(1)能被能被4 4整除，但不能被整除，但不能被100100整除的年份是闰年。如整除的年份是闰年。如19961996，20042004年；年；(2)(2)能被能被100100整除，又能被整除，又能被400400整除的年份是闰年。如整除的年份是闰年。如16001600，20002000年。不符合这两个条件的年份不是闰年。年。不符合这两个条件的年份不是闰

11、年。16算法如下：设算法如下：设y y为被检测的年份，可采取以下步骤：为被检测的年份，可采取以下步骤：s1: s1: 2000 2000 y;y;s2s2: : 若若y y不能被不能被4 4整除，则输出整除，则输出y “y “不是闰年不是闰年”。然后转到。然后转到s6.s6.s3s3: : 若若y y能被能被4 4整除，不能被整除，不能被100100整除，输出整除，输出y “y “是闰年是闰年”，然，然后转到后转到s6s6。s4s4: : 若若y y 能被能被100100整除，又能被整除，又能被400400整除，输出整除，输出y “y “是闰年是闰年”; ;否则输出否则输出“不是闰年不是闰年”

12、，然后转到，然后转到s6s6。s5s5: : 其他，输出其他，输出 y “y “不是闰年不是闰年”。s6s6: y+1 : y+1 y;y;s7s7: : 当当y y 25002500时，转时，转s2s2继续执行，如继续执行，如y2500,y2500,算法停止。算法停止。例例 2.317例例2.4 判断一个数判断一个数n(n=3)是不是素数是不是素数素数：素数：指除了指除了1 1和该数本身之外，不能被其他任何整数整除的数。如：和该数本身之外，不能被其他任何整数整除的数。如：1313是素是素数数判断一个数判断一个数n n是否为素数的方法：是否为素数的方法：将将n n作为被除数，将作为被除数，将2

13、 2到到(n-1)(n-1)各整数轮流作各整数轮流作为除数，如果都不能被整除，则为除数，如果都不能被整除，则n n为素数。为素数。算法如下：算法如下：s1: s1: 输入输入n n的值的值; ;s2s2: 2 : 2 i i（i i作为除数）作为除数）s3s3: n: n被被i i除，得余数除，得余数r rs4s4: : 若若r r0 0，表示，表示n n能被能被i i整除，则打印整除，则打印n”n”不是素数不是素数”，算法结束；否则执，算法结束；否则执行行s5s5s5s5: i: i1 1 i is6s6: : 如果如果i=ni=n1 1，返回，返回s3s3；否则打印；否则打印n”n”是素数

14、是素数”，算法结束。，算法结束。n实际上只需被实际上只需被2 2到到 之间的整数除即可之间的整数除即可18小练习小练习题目：商店结帐，要求将当天题目：商店结帐，要求将当天100笔收入累加，打印笔收入累加，打印出总和。写出算法：出总和。写出算法：（200）打印出100笔收入的总和。解（1）将第一笔收入输入给计算机；（2）将第二笔收入输入给计算机；（3）将以上两笔收入相加；（4）将第三笔收入输入给计算机；（5）将它和前二笔收入的和相加；(198) 将第100笔收入输入给计算机；（199）将它和前99笔收入之和相加；19 以上算法计算机重复执行了一些操作，引入计算机以上算法计算机重复执行了一些操作，

15、引入计算机“ 循循环环” 的概念，算法可改写为：的概念，算法可改写为：（1） 设设“ 计数变量计数变量” N，使，使N的初值为零，即的初值为零，即N=0；（2） 设设“ 累加变量累加变量” T，初值为零（，初值为零（T=0）；）；（3） 输入一个数给输入一个数给“ 收入变量收入变量” A；（4） 将将A和和T的值相加，和放在变量的值相加，和放在变量T中，即中，即A+TT；（5）使）使N的值加的值加1，即，即N+1 N（N的值表示已累加的数据的值表示已累加的数据的个数）；的个数）；（6）若）若N100，则返回，则返回(3)继续执行，否则执行继续执行，否则执行(7)；（7）打印出总和）打印出总和T

16、的值。的值。算法说明算法说明20l 这个算法比上一个简单明确。如果收入不是这个算法比上一个简单明确。如果收入不是100笔而是笔而是1000笔，只需将（笔，只需将（6）中的）中的N100改为改为Nmax？Max = a；成立成立不成立不成立max = b；ab32循环结构程序设计循环结构程序设计l 举例，求举例，求1100的累加和。的累加和。 int i，sum=0； i=1; while（i =100) sum=sum+i; i=i+1; i50g gi i 80是是否否打印打印n ni,i,g gi i37循环结构程序设计循环结构程序设计循环又分循环又分“当型循环当型循环”和和“直到型循环直

17、到型循环”当条件当条件P成立成立执行循环中指令执行循环中指令直到条件直到条件P成立为止成立为止执行循环中的指令执行循环中的指令例：求例：求5!的算法的算法用用N-S图表示图表示1 t2 i T*i t i+1 i直到直到i5打印打印t38 比文字描述直观、形象、易于理解比文字描述直观、形象、易于理解 比传统流程图紧凑易画，废除了流程线，整个算法比传统流程图紧凑易画，废除了流程线，整个算法由基本结构按序组成。由基本结构按序组成。 N-S流程图中的顺序就是程序执行时的顺序。流程图中的顺序就是程序执行时的顺序。 用用N-S图表示的算法都是结构化的算法。图表示的算法都是结构化的算法。39例：求级数的值

18、，用例：求级数的值，用N-S图表示图表示0s1 n n s+1/ns s n+1n当当nt2i当当iti+1 i输出输出t结束结束41注意：注意：伪代码所描述的流程，一般不能直接作为程序来使用，最后还需转换成用某种程序设计语言所描述的程序。与程序设计语言的区别：与程序设计语言的区别： 前者比较自由，不象后者那样受语法的约束，只要描述得人们能理解就行，而不必考虑计算机处理时所要遵循的规定或其它一些细节。42 要实现某个任务，不仅要设计算法，而且要实现算法。用要实现某个任务，不仅要设计算法，而且要实现算法。用计算机程序设计语言（如计算机程序设计语言（如C语言）可实现算法。语言）可实现算法。 用某种

19、程序设计语言编写的程序本质上也是问题处理方案用某种程序设计语言编写的程序本质上也是问题处理方案的描述，并且是最终的描述。的描述，并且是最终的描述。 在一般的程序设计过程中，不提倡一开始就编写程序，特在一般的程序设计过程中，不提倡一开始就编写程序，特别是对于大型的程序。别是对于大型的程序。 程序是程序设计的最终产品，需要经过每一步的细致加工程序是程序设计的最终产品，需要经过每一步的细致加工才能得到，如果企图一开始就编写出程序，往往会适得其才能得到，如果企图一开始就编写出程序，往往会适得其反，达不到预想的结果。反，达不到预想的结果。43例题例题例例2.20 求求5！，用！，用C语言表示语言表示 #

20、include void Main ( ) int i,t;t=1;i=2; while(i=5) t=t*i; i=i+1; printf(“%d”,t); 44例例2.21 求级数的值求级数的值#include void Main( )float deno=2.0,sun=1.0,term;while (deno101) term=1/deno; sum=sum+term; deno=deno+1; printf(“%f”,sum);45最后编写的程序还需要进行测试和调试，只有最后编写的程序还需要进行测试和调试，只有经过调试后的程序才能正式运行。经过调试后的程序才能正式运行。测试：是指通过

21、一些典型例子，尽可能多发现测试：是指通过一些典型例子，尽可能多发现程序中的错误。程序中的错误。调试：是指找出程序中错误的具体位置，并改调试：是指找出程序中错误的具体位置，并改正错误。正错误。结论：测试与调试往往是交替进行的，通过测结论：测试与调试往往是交替进行的，通过测试发现程序中的错误，通过调试进一步找出错试发现程序中的错误，通过调试进一步找出错误的位置并改正错误。误的位置并改正错误。调试与运行调试与运行46结构化程序设计方法的基本思路是：把一个复杂问题的求结构化程序设计方法的基本思路是：把一个复杂问题的求解过程分阶段进行，每个阶段处理的问题都控制在人们容解过程分阶段进行，每个阶段处理的问题

22、都控制在人们容易理解和处理的范围内。易理解和处理的范围内。采用以下方法可得到结构化的程序采用以下方法可得到结构化的程序:(1)自顶向下(2)逐步细化(3)模块化设计(4)结构化编码47模块化设计模块化设计 把一个大程序按人们能理解的大小规模进把一个大程序按人们能理解的大小规模进行分解。（经过分解后的模块比较小，易实行分解。（经过分解后的模块比较小，易实现，易调试。现，易调试。 考虑的问题考虑的问题：按功能划分模块 划分模块的基本原则是使每个模块易于理解，要求各模块的功能尽量单一，各模块之间的联系尽量减少。这样要修改某一功能时只涉及一个模块；其它应用程序可以充分利用已有的一些模块。48按层次组织

23、模块时，一般上层模块只指出按层次组织模块时，一般上层模块只指出“做什做什么么”, , 在最底层的模块才精确地描述在最底层的模块才精确地描述“怎么怎么做做”。例：下图层次结构中，主模块只需要指出总任务例：下图层次结构中，主模块只需要指出总任务就可以了，下层模块才精确描述就可以了，下层模块才精确描述“ “ 怎么做怎么做”。HIS前台系统前台系统预定登记预定登记后台系统后台系统餐饮管理餐饮管理决策支持决策支持各种算法各种算法按层次组织模块按层次组织模块49l 包括以下两个方面：包括以下两个方面： 将一个复杂问题的求解过程分解和细化将一个复杂问题的求解过程分解和细化 成若干模块组成的层次结构；成若干模

24、块组成的层次结构； 将一个模块的功能逐步分解、细化为一将一个模块的功能逐步分解、细化为一 系列的处理步骤，直到分解为某种程序系列的处理步骤，直到分解为某种程序 设计语言的语句或某种机器指令。设计语言的语句或某种机器指令。l 优点：优点： 可提高程序的效率；用先全局后局部、先整体后细可提高程序的效率；用先全局后局部、先整体后细节、先抽象后具体的方法设计出的程序具有清晰的节、先抽象后具体的方法设计出的程序具有清晰的层次结构，容易阅读和理解。层次结构，容易阅读和理解。自顶向下、逐步细化的设计过程自顶向下、逐步细化的设计过程50 计算并打印平均分计算并打印平均分计算平均分计算平均分SUM0(累加器清零

25、累加器清零)N=0逐个读入分数逐个读入分数X，且，且SUMSUMX(累加累加)NN1(计数计数)计算平均分计算平均分SSUMN打印平均分打印平均分举例：计算并打印输出某门课程平均分举例：计算并打印输出某门课程平均分51例：打印出例：打印出2000-2500年中是闰年的年份年中是闰年的年份如果如果y是闰年，是闰年，则打印则打印y当当y=2500Y=2000By是闰年是闰年是是不是不是打印打印yyy1BCMod(y,4)=0 且且 Mod(y,100)0 是是不是不是打印打印yCMod(y,100)=0 且且 Mod(y,400)=0 是是不是不是打印打印y52例例 将将1到到1000之间的素数打印出来之间的素数打印出来“筛法”采用的方法：在一张纸上写上1到1000全部整数，然后逐个判断他们是否是素数，找出一个非素数就把它挖掉最后剩下的就是素数用筛法求素数表输入1-n各数把所有非素数去掉打印全部素数53(1)先将先将1挖掉挖掉(2)用用2去除它后面的各个数，把能被去除它后面的各个数，把能被2整除的数挖掉，整除