中国科技大学语言讲义.ppt

第2章 程序的灵魂-------算法 2.1 算法的概念（2.1） 2.2 算法的特性(2.3) 2.3 算法的表示(2.2 2.4) 2.4 结构化程序设计方法(2.5) 2.1 算法的概念 一个程序应包括对数据的描述和对数据处理的描述 对数据的描述，即数据结构(data structure)。 对数据处理的描述，即计算机算法(algorithm)。 算法是为解决一个问题而采取的方法和步骤，是程序的灵魂。 Nikiklaus Wirth公式： 数据结构 + 算法 = 程序数据结构 + 算法+计算机语言+程序设计方法= 程序 算法:为解决一个问题所采取的方法和步骤分类: 数值算法  非数值算法评估: 时间复杂度 空间复杂度 2.2 算法的特点 确定性 算法的每一种运算必须要有确切的定义，即每一种运算应该执行何种动作必须是相当清楚的、无二义性的。 数据输入 一个算法有零个或多个数据输入，它们是在算法开始之前对算法最初赋予的量，这些输入取自特定的对象集合。 数据输出 一个算法产生一个或多个输出，它们是同输入有某种特定关系的量。 有穷性 一个算法总是在执行了有穷步之后终止。 有效性 有效执行 2.3算法的表示 自然语言—易出现”歧义” 流程图—直观形象、易理解 N-S流程图—改进的流程图 伪代码 计算机语言表示 求5! 例2.1 设p为被乘数，i为乘数。用循环算法来求结果。 S1：使p=l S2：使i=2 S3：使pXi，乘积仍放在变量p中，可表示为 pXi=p S4：使i的值加1，即i+1=i s5：如果i不大于5，返回重新执行步骤s3以及其后的步骤S4和s5；否则，输出p,算法结束。最后得到p的值就是5!的值。 顺序结构 选择结构 循环结构 一个入口 一个出口 结构内每一部分都会被执行 结构内无”死循环” 2.3算法的表示 自然语言—易出现”歧义” 流程图—直观形象、易理解 N-S流程图—改进的流程图 伪代码 计算机语言表示 判定2000-2500年中的每一年是否闰年，将结果输出．闰年的条件是：①能被4整除，但不能被100整除的年份都是闰年，如1996年，2004年是闰年；②能被100整除，又能被400整除的年份是闰年．如1600年、2000年是闰年．不符合这两个条件的年份不是闰年。（2.3） 设y为被检测的年份。采取以下步骤； S1：2000=y S2：若y不能被4整除，则输出y“不是闰年”。转S5 S3：若y能被4整除，不能被100整除，则输出y“是闰年”。转S5 S4：若y能被100整除，又能被400整除，输出y”是闰年”；否则 输出“不是闰年”。转S5 S5：y+1=y S6：当y≤2500时，转S2继续执行，如y2500，算法停止。 对一个大于或等于3的正整数，判断它是不是一个素数。 判素数的方法:将n作为被除数，将2到(n一1)各个整数轮流作为除数，如果都不能被整除，则n为素数。（2.5） S1：输入n的值 S2：i=2(i作为除数) S3：n被i除，得余数r S4：如果r=O，表示n能被i整除，则打印n“不是素数”，算法结束；否则执行S5 S5：i+1=i S6：如果i=n-1，返回S3；否则打印n“是素数”，然 后结束。 S6：如果i=n1/2，返回S3；否则打印n“是素数”,然 后结束。 2.4结构化程序设计方法 为何提出: 基本思路: 把一个复杂的问题分解成若干个简单的小问题. 自顶向下 逐步细化 模块化设计 结构化编码 例 将1到1000之间的素数打印出来。 “埃拉托色尼(Eratosthenes)筛法”:在一张纸上写上1到1000全部整数，然后逐个判断它们是否素数，找出一个非素数，就把它挖掉，最后剩下的就是素数. (1)先将1挖掉(因为1不是素数)。 (2)用2去除它后面的各个数，把能被2整除的数挖 掉，即把2的倍数挖掉。 (3)用3去除它后面各数，把3的倍数挖掉。 (4)分别用4、5…作为除数去除这些数以后的各数。这个过程一直进行到在除数后面的数已全被挖掉为止。 如果需要找1～n范围内素数表，只需进行到除数为n1/2(取其整数)即可。 (1)挖去1； (2)用刚才被挖去的数的下一个数p去除p后面各 数，把p的倍数挖掉； (3)检查P是否小于n1/2 的整敷部分(如果n--1000， 则检查p31)，如果是，则返回(2)继续执行， 否则就结束， (4)纸上