[工学]【程序设计基础】第2章_程序的灵魂--算法 2.ppt

2.1 算法的概念 2.2 简单算法举例 例2: 某班有30名学生，求该班学生A课程的平均成绩。 S1：total=0。 S2：counter=1。 S3：读入第counter个学生的成绩赋给grade S4：total=total+grade S5：使counter的值加1，即counter=counter+1 S6：如果counter不大于30，返回重新执行步骤S3以及其后的步骤S4、S5和S6 S7：average=total / 30 2.3 算法的特性 2.4 算法的表示 2.4.1 用流程图表示算法 将例2求平均成绩的算法用流程图表示 S1：total=0。 S2：counter=1。 S3：读入第counter个学生的成绩赋给grade S4：total=total+grade S5：使counter的值加1，即counter=counter+1 S6：如果counter不大于30，返回重新执行步骤S3以及其后的步骤S4、S5和S6 S7：average=total / 30 2.4.2 三种基本结构和改进的流程图 2.4.3 N-S流程图 去掉流程线,使图紧凑易画,更好地表示结构化算法 N-S图表示算法的优点 直观、形象、 易于理解。 紧凑易画。N--S流程图中的上下顺序就是执行时的顺序。 用N--S图表示的算法都是结构化的算法，因为它不可能出现流程无规律的跳转，而只能自上而下地顺序执行。 2.5 结构化程序设计方法 作业： 2.4 2.5 用流程线指出各框的执行顺序，对流程线的使用没有严格限制； 难以阅读、修改，使算法的可靠性和可维护性难以保证 限制箭头的滥用，即不允许无规律地使流程随意转向，只能顺序地进行下去 * * 第二章 主要内容 2.1 算法的概念 2.2 简单算法举例 2.3 算法的特性 2.4 怎样表示一个算法 2.5 结构化程序设计方法 一个程序应包括两个方面的内容: 对数据的描述：数据结构(data structure) 对操作的描述：算法(algorithm) 著名计算机科学家沃思提出一个公式: 数据结构 + 算法 = 程序 数据结构＋算法＋程序设计方法＋语言工具 完整的程序设计应该是: 程序设计：让计算机按自己的意愿进行某项计算或数据处理任务。 “做什么”、“怎么做” ax2+bx+c=0 算法：计算机具体操作的步骤 例如： 让计算机从任意两个数中挑选出大者并打印出来。 算法如下： 1.输入两个数a和b; 2.判断a和b数值谁大，若ab，则 a?max；否则（ab）b?max; 3.将max的值打印出来。 例1: 求1×2×3×4×5 步骤1：先求1×2，得到结果2 步骤2：将步骤1得到的乘积2再乘以3，得到结果6 步骤3：将6再乘以4，得24 步骤4：将24再乘以5，得120 如果要求1×2×…×1000，则要写999个步骤 S1：使t=1。 S2：使i=2。 S3：使t×i，乘积仍放在变量t中，可表示为：t×i→t S4：使i的值加1，即i+1 → i。 S5：如果i不大于5，返回重新执行步骤S3以及其后的步骤S4和S5；否则，算法结束。最后得到t的值就是5!的值。 可以设两个变量： 被乘数、乘数 每一步骤的乘积放在被乘数变量中。 设t为被乘数，i为乘数。用循环算法来求结果, 算法可改写： S1：1→t S2：3 → i S3：t×i → t S4：i+2 → i S5：若i≤11，返回S3。否则，结束。 如果题目改为：求1×3×5×……×11 算法只需作很少的改动： 累乘算法！ 总成绩：total 计数器：counter 每次读入的成绩：grade 平均成绩：average 例3 对一个大于或等于3的正整数，判断它是不是一个素数。 概念：所谓素数，是指除了1和该数本身之外，不能被其它任何整数整除的数。例如，13是素数。因为它不能被2，3，4，…，12整除。 分析：判断一个数n(n≥3)是否素数的方法： 将n作为被除数，将2到(n-1)各个整数轮流作为除数，如果都不能被整除，则n为素数。 算法如下 ： S1：输入n的值 S2：i=2 （i作为除数） S3：n被i除，得余数r S4：如果r=0，表示n能被i整除，则打印n“不是素数”，算法结束。否则执行S5 S5：i+1→i S6：如果i≤n-1，返回S3。否则打印 n “是素数”。然后结束。 实际上，n不必被2到(n-1)的整数除，只需被2到n/2间整数除，甚至只需被2到 之间的