中国科技大学C语言讲义

1、1第第2 2章章 程序的灵魂程序的灵魂-算法算法2.1 2.1 算法的概念（算法的概念（2.12.1）2.2 2.2 算法的特性算法的特性(2.3)(2.3)2.3 2.3 算法的表示算法的表示(2.2 2.4)(2.2 2.4)2.4 2.4 结构化程序设计方法结构化程序设计方法(2.5)(2.5)22.1 2.1 算法的概念算法的概念一个程序应包括对数据的描述和对数据处理的描述一个程序应包括对数据的描述和对数据处理的描述对数据的描述，即数据结构对数据的描述，即数据结构(data structure)(data structure)。 对数据处理的描述，即计算机算法对数据处理的描述，即计算机

2、算法(algorithm)(algorithm)。 算法是为解决一个问题而采取的方法和步骤，是算法是为解决一个问题而采取的方法和步骤，是程序的灵魂。程序的灵魂。Nikiklaus WirthNikiklaus Wirth公式：公式： 数据结构数据结构 + + 算法算法 = = 程序程序数据结构数据结构 + + 算法算法+ +计算机语言计算机语言+ +程序设计方法程序设计方法= = 程序程序3算法算法:为解决一个问题所采取的方法和步骤为解决一个问题所采取的方法和步骤分类分类: 数值算法数值算法 非数值算法非数值算法评估评估: 时间复杂度时间复杂度 空间复杂度空间复杂度42.2 2.2 算法的特点

3、算法的特点v确定性确定性 算法的每一种运算必须要有确切的定义，算法的每一种运算必须要有确切的定义，即每一种运算应该执行何种动作必须是相当清楚的、即每一种运算应该执行何种动作必须是相当清楚的、无二义性的。无二义性的。v数据输入数据输入 一个算法有零个或多个数据输入，它们一个算法有零个或多个数据输入，它们是在算法开始之前对算法最初赋予的量，这些输入是在算法开始之前对算法最初赋予的量，这些输入取自特定的对象集合。取自特定的对象集合。v数据输出数据输出 一个算法产生一个或多个输出，它们是一个算法产生一个或多个输出，它们是同输入有某种特定关系的量。同输入有某种特定关系的量。v有穷性有穷性 一个算法总是在

4、执行了有穷步之后终止。一个算法总是在执行了有穷步之后终止。v有效性有效性 有效执行有效执行52.32.3算法的表示算法的表示v自然语言自然语言易出现易出现”歧义歧义”v流程图流程图直观形象、易理解直观形象、易理解vN-SN-S流程图流程图改进的流程图改进的流程图v伪代码伪代码v计算机语言表示计算机语言表示6求求5! 5! 例例2.12.1设设p p为被乘数，为被乘数，i i为乘数。用循环算法来求结果。为乘数。用循环算法来求结果。 S1S1：使：使p=lp=l S2 S2：使：使i=2i=2 S3 S3：使：使pXipXi，乘积仍放在变量，乘积仍放在变量p p中，可表示为中，可表示为 pXi=p

5、pXi=p S4 S4：使：使i i的值加的值加1 1，即，即i+1=ii+1=i s5 s5：如果：如果i i不大于不大于5 5，返回重新执行步骤，返回重新执行步骤s3s3以及其后的以及其后的步骤步骤S4S4和和s5s5；否则，输出；否则，输出p,p,算法结束。最后得到算法结束。最后得到p p的的值就是值就是5!5!的值。的值。7起止框起止框输入输入/出框出框判断框判断框处理框处理框流程线流程线注释框注释框连接点连接点8开始开始1=p1=p2=i2=ipxi=ppxi=pi+1=ii+1=ii5i5打印打印p p结束结束N NY Y9顺序结构顺序结构10选择结构选择结构11循环结构循环结构当

6、当型型循循环环直直到到型型循循环环直到条件成立直到条件成立a a块块12一个入口一个入口一个出口一个出口结构内每一部分都会被执行结构内每一部分都会被执行结构内无结构内无”死循环死循环”13开始开始1=p1=p2=i2=ipxi=ppxi=pi+1=ii+1=ii5i5打印打印p p结束结束N NY Y1=p1=p2=i2=ip xi=pp xi=pi+1=ii+1=i直到直到i5i5打印打印p p142.32.3算法的表示算法的表示v自然语言自然语言易出现易出现”歧义歧义”v流程图流程图直观形象、易理解直观形象、易理解vN-SN-S流程图流程图改进的流程图改进的流程图v伪代码伪代码v计算机语言

7、表示计算机语言表示15判定判定2000-25002000-2500年中的每一年是否闰年，将结果输出年中的每一年是否闰年，将结果输出闰年的条件是：闰年的条件是：能被能被4 4整除，但不能被整除，但不能被100100整除的年份都是整除的年份都是闰年，如闰年，如19961996年，年，20042004年是闰年；年是闰年；能被能被100100整除，又能被整除，又能被400400整除的年份是闰年如整除的年份是闰年如16001600年、年、20002000年是闰年不符合年是闰年不符合这两个条件的年份不是闰年。这两个条件的年份不是闰年。（2.32.3） 设设y y为被检测的年份。采取以下步骤；为被检测的年份

8、。采取以下步骤； S1S1：2000=y2000=y S2 S2：若：若y y不能被不能被4 4整除，则输出整除，则输出y“y“不是闰年不是闰年” ”。转。转S5S5 S3 S3：若：若y y能被能被4 4整除，不能被整除，不能被100100整除，则输出整除，则输出y“y“是闰年是闰年” ”。转。转S5S5 S4 S4：若：若y y能被能被100100整除，又能被整除，又能被400400整除，输出整除，输出y”y”是闰年是闰年” ”；否则；否则 输出输出“ “不是闰年不是闰年” ”。转。转S5S5 S5 S5：y+1=yy+1=y S6 S6：当：当y2500y2500时，转时，转S2S2继续

9、执行，如继续执行，如y2500y2500，算法停止。，算法停止。162000= y是是 Y/4Y/4的余数为的余数为0 0 否否是是 Y/100Y/100余数不为余数不为0 0 否否打印打印y”y”非闰年非闰年”打印打印y”是是闰年闰年”是是 Y/400Y/400余数为余数为0 0 否否打印打印y”是是闰年闰年”打印打印y”非闰年非闰年” y+1=y 直到直到y250017对一个大于或等于对一个大于或等于3 3的正整数，判断它是不是一个素数。的正整数，判断它是不是一个素数。 判素数的方法判素数的方法: :将将n n作为被除数，将作为被除数，将2 2到到(n(n一一1)1)各个整数轮流作各个整数

10、轮流作为除数，如果都不能被整除，则为除数，如果都不能被整除，则n n为素数。为素数。（2.52.5）S1S1：输入：输入n n的值的值S2S2：i=2(ii=2(i作为除数作为除数) )S3S3：n n被被i i除，得余数除，得余数r rS4S4：如果：如果r=Or=O，表示，表示n n能被能被i i整除，则打印整除，则打印n“n“不是素数不是素数” ”，算法结束；，算法结束；否则执行否则执行S5S5S5S5：i+1=ii+1=iS6S6：如果：如果i=n-1i=n-1，返回，返回S3S3；否则打印；否则打印n“n“是素数是素数” ”，然，然 后结束。后结束。S6S6：如果：如果i=niin/

11、i 的余数的余数=rr=0?i+1=iin1/2打印打印“n n是素数是素数” 结束结束打印打印“n n不是素数不是素数”YNYN19开始开始输入输入n2=i 0=wn/i 的余数的余数=rr=0?i+1=iiwYN结束结束打印打印“n n不是素数不是素数”打印打印“n n是素数是素数” W=0?YNYN20输入输入n0=w2=in/i的余数的余数=r是是 r=0 否否1= w i+1=i 直到直到rn1/2或或w!=0是是 w=0 否否输出输出n”是素数是素数“ 输出输出n”不是素数不是素数“212.42.4结构化程序设计方法结构化程序设计方法v为何提出为何提出: :v基本思路基本思路: :

12、 把一个复杂的问题分解成若干个简单的小问把一个复杂的问题分解成若干个简单的小问题题. .自顶向下自顶向下 逐步细化逐步细化 模块化设计模块化设计 结构化编码结构化编码22例例 将将1 1到到10001000之间的素数打印出来。之间的素数打印出来。 “ “埃拉托色尼埃拉托色尼(Eratosthenes)(Eratosthenes)筛法筛法” ”: :在一张纸上写上在一张纸上写上1 1到到10001000全部整数，然后逐个判断它们是否素数，找出一个全部整数，然后逐个判断它们是否素数，找出一个非素数，就把它挖掉，最后剩下的就是素数非素数，就把它挖掉，最后剩下的就是素数. (1)(1)先将先将1 1挖

13、掉挖掉( (因为因为1 1不是素数不是素数) )。 (2)(2)用用2 2去除它后面的各个数，把能被去除它后面的各个数，把能被2 2整除的数挖整除的数挖 掉，即把掉，即把2 2的倍数挖掉。的倍数挖掉。 (3)(3)用用3 3去除它后面各数，把去除它后面各数，把3 3的倍数挖掉。的倍数挖掉。 (4)(4)分别用分别用4 4、55作为除数去除这些数以后的各数。作为除数去除这些数以后的各数。这个过程一直进行到在除数后面的数已全被挖掉为这个过程一直进行到在除数后面的数已全被挖掉为止。止。 如果需要找如果需要找1 1n n范围内素数表，只需进行到除数范围内素数表，只需进行到除数为为n n1/21/2(

14、(取其整数取其整数) )即可。即可。23 (1)(1)挖去挖去1 1； (2)(2)用刚才被挖去的数的下一个数用刚才被挖去的数的下一个数p p去除去除p p后面各后面各 数，把数，把p p的倍数挖掉；的倍数挖掉； (3)(3)检查检查P P是否小于是否小于n n1/21/2 的整敷部分的整敷部分( (如果如果n-1000n-1000， 则检查则检查p31)pi当当ixii+1=i26将去将去x1掉掉 (x1=0)2=i当当ii如如xi未去掉未去掉,则将则将xi+1到到xn之之间所有是间所有是xi倍数的数去掉倍数的数去掉27 xi=0 是是 否否则将则将xi+1到到xn之间所有是之间所有是xi倍数的数去掉倍数的数去掉28i+1=j当当jj将能被将能被xi整除的整除的xj去掉去掉29是是 xj =0 否否 xj能被能被xi整除整除