2算法程序灵魂.ppt

开始 输入一个数 该数0 累加 输入完100个数 输出累加和 结束 起止框 处理框 判断框 流向线 Y Y N N 例 算法描述 (流程图) 例 算法描述(N-S流程图) 处理 判断 重复 输入一个数 该数 〉 0 满足 不满足 加到累加和中 输入完 100 个数 否 输出累加和 不累加 * 例2.15 将例2.5判别素数的算法用N--S流程图表示。 传统流程图分析： 出口1 出口2 此图不符合基本结构特点！由于不能分解为三种基本结构，就无法直接用N--S流程图的三种基本结构的符号来表示。 因此，应当先作必要的变换。 所谓素数，是指除了1和该数本身之外，不能被其他任何整数整除的数。例如，13是素数，因为它不能被2，3，4，…，12整除。 判断一个数n(n≥3)是否素数的方法是很简单的：将n作为被除数，将2到(n-1)各个整数轮流作为除数，如果都不能被整除，则n为素数。 例2.15 将例2.5判别素数 传统流程图变换为： 一个出口 图2-34 所谓素数，是指除了1和该数本身之外，不能被其他任何整数整除的数。例如，13是素数，因为它不能被2，3，4，…，12整除。 判断一个数n(n≥3)是否素数的方法是很简单的：将n作为被除数，将2到(n-1)各个整数轮流作为除数，如果都不能被整除，则n为素数。 要将第一个判断框（r=0）的两个出口回合在一点，以解决两个出口问题。 当r=0时不直接输出n“不是素数”，而只设一个标志值（变量w），它的初始状态为w=0。当r=0时（n表示非素数）使w变成1. 如果r≠0则保持w=0。w=1表示n为非素数。 如果最终w=0，则表示n为素数。然后将“1=w”框的出口线改为指向第二个菱形框，同时将第二个菱形框中的条件改为 “i≤n和w=0”，即只有当“i≤n”和“w=0”两个条件都满足时才继续执行循环。 如果出现i＞n或w≠0之一，都不会继续执行循环(见图2.34)。如果在某一次r=0，则应执行1=w，然后，由第二个菱形框判断为“条件不成立”，接着执行图下部的选择结构。 此时，w≠0，表示n不是素数，应打印出n不是素数的信息。 如果w=0，则表示在上面的每次循环中，n都不能被每一个i整除，所以n是素数，故输出n是素数的信息。 图2-35 N--S流程图 注意： 直到型循环的判断条件为： “直到i＞n或w≠0”，即只要“i＞n或w≠0”之一成立，就不再继续执行循环。 通过以上例子，可以看出用N-S图表示算法的优点： 它比文字描述直观、形象、 易于理解；比传统流程图紧凑易画，尤其是它废除了流程线，整个算法结构是由各个基本结构按顺序组成的。 N-S流程图中的上下顺序就是执行时的顺序，即图中位置在上面的先执行，位置在下面的后执行。 写算法和看算法只需从上到下进行就可以了，十分方便。 用N-S图表示的算法都是结构化的算法。 一个结构化的算法是由一些基本结构顺序组成的。在基本结构之间不存在向前或向后的跳转，流程的转移只存在于一个基本结构范围之内(如循环中流程的跳转)；一 个非结构化的算法可以用一个等价的结构化算法代替，其功能不变 。如果一个算法不能分解为若干个基本结构，则它必然不是一个结构化的算法。 小结： §2.4.5 用位代码表示算法 概念：伪代码是用介于自然语言和计算机语 言之间的文字和符号来描述算法。 特点：它如同一篇文章一样 ，自上而下地写 下来。每一行表示一个基本操作。 它不用图形符号，因此书写方便 、也 比较好懂，也便于向计算机语言算法 (即程序)过渡。 用处：适用于设计过程中需要反复修改时的 流程描述。 IF x is positive THEN print x ELSE print -x 例： “打印x的绝对值”的算法可以用伪代码表示为： 也可以用汉字伪代码表示： 若 x 为正 打印 x 否则 打印 -x 也可以中英文混用，如： IF x 为 正 print x ELSE print -x 例2.16 求5!。 用伪代码表示算法： BEGIN / *算法开始 */ 1?t 2 ? i while i≤5 { t *i ?t i + 1 ? i } print t END /* 算法结束 */ BEGIN (算法开始)