[工学]第二章 算法.pptVIP

2 、判定2000-2500年中的每一年是否闰年 判定闰年的条件是: (1)能被4整除,但不能被100整除的年份都是闰年 (2)能被100整除,又能被400整除的年份是闰年 不符合上述两条件的年份不是闰年 用有含义的单词作变量名,使算法更易于理解: sum 表示累加和 deno是”分母”英文缩写 sign 代表数值符号 term代表某一项 4 、对于一个大于或等于3的正整数,判断它是不是一个素数 判定方法: 将n作为被除数,将2到n-1(或者2到n/2之间整数,甚至2到n的平方根之间整数)各个整数先后做为除数,如果都不能被整除,则n为素数 本章小结 掌握程序的三种基本结构 掌握流程图 掌握N-S图 伪代码 了解结构化程序设计方法 第二章 算法 一、算法 算法就是为解决一个具体问题而采取的有限的操作步骤，算法通过语句来实现 计算机算法分两类： 数值运算算法:求数值解，例如求方程的根、 求函数的定积分等。 非数值运算算法:常用于事务管理领域，例如图 书检索、人事管理、行车调度管理等。 著名计算机科学家沃思提出一个公式: 程序=数据结构(data structure) +算法(algorithm) (数据) ( 操作) 算法的正确性衡量标准： 有穷性：算法包含有限步操作 确定性：每一步都应确定无歧义 有效性：每一步都应能有效执行且能得到确定的结果 0或多个输入: 程序允许无输入 1或多个输出：任何程序都必须有输出，哪怕是提示信息 二、算法的描述 常用的算法描述方法有：自然语言、传统流程图、NS流程图、伪代码、PAD图等 1.自然语言 2.流程图: 美国国家标准化协会ANSI(American National Standard Institute)规定了一些常用的流程图符号： 例：求n!的算法思想： n!=1*2*3*…*n 计算机执行乘法时通常每次求两个数相乘，因此上面公式在程序中需要通过反复相乘来实现。 需要设定一个变量n，表明求多少的阶乘； 第二个变量，存当前累乘的结果； 第三个变量存当前将要与累乘器相乘的因子，并且该因子的变化是从1到n每次增加1 流程图如下页所示 no 开始 n0? 输入n 计算n! 的传统流程图 fac=1,i=1 fac=fac*i i= i+1 i=n? yes 输出fac值 no 结束 输出错提示 yes 求5! 流程图是表示算法的较好的工具。一个流程图包括以下几部分 ： (1)表示相应操作的框； (2)带箭头的流程线； (3)框内外必要的文字说明。 传统流程图弊端: BS型算法(a bowl of spaghetti) 太长 3.程序的三种基本结构 ⑴ 顺序结构 A B ⑵ 选择结构 又称分支结构。根据是否满足给定条件而从两组操作中选择执行一种操作。虚线框内是一个选择结构。 P A B 成立 不成立 ·无论P条件是否成立，只能执行A操作或B操作中的一个; ·无论执行完哪一个分支后，就结束了。 ·两个操作可以有一个是空操作，即不执行任何操作，形如下图: P A 成立 不成立 P B 成立 不成立 入口 出口 ⑶ 循环结构 又称重复结构，即在一定条件下，反复执行某一部分的操作。 有两种类型： 执行过程： 当给定条件P成立时，执行S操作，然后再判断P条件是否成立，如果仍成立，再执行S操作，然后再判断…，如此反复，直到某一次P条件不成立为止，此时不再执行S，结束循环。 特点： 先判断，后执行，S有可能一次也不执行。 P S F T 当型循环 入口 出口 ⑶ 循环结构 执行过程： 执行S操作，然后判断条件P是否成立，如果不成立，再执行S操作，然后再判断，…...，如此反复，直到某一次P条件成立不再执行S，结束循环。 特点： 先执行，后判断，S最少要执行一次。 S P F T 直到型循环 入口 出口 三种基本结构共同特点 （1）只有一个入口 （2）只有一个出口 （3）结构内每部分都有机会被执行。 （4）结构内不存在死循环 自定义基本结构 4. N-S流程图表示算法 完全去掉了带箭头的流程线。 全部算法写在一个矩形框内，在该框内还可以包含其它的从属于它的框。 N-S流程图用以下的流程图符号： (1)顺序结构 (2)选择结构 (3)循环结构 N-S图表示算法的优点 比文字描述直观、形