中国科技大学C语言讲义2

《中国科技大学C语言讲义2》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章程序的灵魂-------算法2.1算法的概念（2.1）2.2算法的特性(2.3)2.3算法的表示(2.22.4)2.4结构化程序设计方法(2.5)2.1算法的概念一个程序应包括对数据的描述和对数据处理的描述对数据的描述，即数据结构(datastructure)。对数据处理的描述，即计算机算法(algorithm)。算法是为解决一个问题而采取的方法和步骤，是程序的灵魂。NikiklausWirth公式：数据结构+算法=程序数据结构+算法+计算机语言+程序设计方法=程序算法:为解决一个问题所采取的方法和步骤分类:数值算法非数值算法评估:时间复杂度空间复杂度2.2算法的特点确定性算法的每一

2、种运算必须要有确切的定义，即每一种运算应该执行何种动作必须是相当清楚的、无二义性的。数据输入一个算法有零个或多个数据输入，它们是在算法开始之前对算法最初赋予的量，这些输入取自特定的对象集合。数据输出一个算法产生一个或多个输出，它们是同输入有某种特定关系的量。有穷性一个算法总是在执行了有穷步之后终止。有效性有效执行2.3算法的表示自然语言—易出现”歧义”流程图—直观形象、易理解N-S流程图—改进的流程图伪代码计算机语言表示求5!例2.1设p为被乘数，i为乘数。用循环算法来求结果。S1：使p=lS2：使i=2S3：使pXi，乘积仍放在变量p中，可表示为pXi=>pS4：使i的值加1，即i+1=>i

3、s5：如果i不大于5，返回重新执行步骤s3以及其后的步骤S4和s5；否则，输出p,算法结束。最后得到p的值就是5!的值。起止框输入/出框判断框处理框流程线注释框连接点开始1=>p2=>ipxi=>pi+1=>ii>5打印p结束NY顺序结构选择结构循环结构当型循环直到型循环直到条件成立a块一个入口一个出口结构内每一部分都会被执行结构内无”死循环”开始1=>p2=>ipxi=>pi+1=>ii>5打印p结束NY1=>p2=>ipxi=>pi+1=>i直到i>5打印p2.3算法的表示自然语言—易出现”歧义”流程图—直观形象、易理解N-S流程图—改进的流程图伪代码计算机语言表示判定2000-2500年

4、中的每一年是否闰年，将结果输出．闰年的条件是：①能被4整除，但不能被100整除的年份都是闰年，如1996年，2004年是闰年；②能被100整除，又能被400整除的年份是闰年．如1600年、2000年是闰年．不符合这两个条件的年份不是闰年。（2.3）设y为被检测的年份。采取以下步骤；S1：2000=>yS2：若y不能被4整除，则输出y“不是闰年”。转S5S3：若y能被4整除，不能被100整除，则输出y“是闰年”。转S5S4：若y能被100整除，又能被400整除，输出y”是闰年”；否则输出“不是闰年”。转S5S5：y+1=>yS6：当y≤2500时，转S2继续执行，如y>2500，算法停止。20

5、00=>y是Y/4的余数为0否是Y/100余数不为0否打印y”非闰年”打印y”是闰年”是Y/400余数为0否打印y”是闰年”打印y”非闰年”y+1=>y直到y>2500对一个大于或等于3的正整数，判断它是不是一个素数。判素数的方法:将n作为被除数，将2到(n一1)各个整数轮流作为除数，如果都不能被整除，则n为素数。（2.5）S1：输入n的值S2：i=2(i作为除数)S3：n被i除，得余数rS4：如果r=O，表示n能被i整除，则打印n“不是素数”，算法结束；否则执行S5S5：i+1=>iS6：如果i<=n-1，返回S3；否则打印n“是素数”，然后结束。S6：如果i<=n1/2，返回S3；否则

6、打印n“是素数”,然后结束。开始输入n2=>in/i的余数=>rr=0?i+1=>ii>n1/2打印“n是素数”结束打印“n不是素数”YNYN开始输入n2=>i0=>wn/i的余数=>rr=0?i+1=>ii<=n1/2和w=01=>wYN1结束打印“n不是素数”打印“n是素数”W=0?YN1YN输入n0=>w2=>in/i的余数=>r是r=0否1=>wi+1=>i直到r>n1/2或w!=0是w=0否输出n”是素数“输出n”不是素数“2.4结构化程序设计方法为何提出:基本思路:把一个复杂的问题分解成若干个简单的小问题.自顶向下逐步细化模块化设计结构化编码例将1到1000之间的素数打印出来。“埃

7、拉托色尼(Eratosthenes)筛法”:在一张纸上写上1到1000全部整数，然后逐个判断它们是否素数，找出一个非素数，就把它挖掉，最后剩下的就是素数.(1)先将1挖掉(因为1不是素数)。(2)用2去除它后面的各个数，把能被2整除的数挖掉，即把2的倍数挖掉。(3)用3去除它后面各数，把3的倍数挖掉。(4)分别用4、5…作为除数去除这些数以后的各数。这个过程一直进行到在除数后面的数已全被挖掉为止。