第二章 程序的灵魂-算法 V2.pptVIP

第二章 程序的灵魂－算法 2.1 算法的概念 程序 = 算法 + 数据结构 + 程序设计方法 + 语言工具和环境 数据结构：程序所处理的对象 数据的类型和组织形式 算法：解决一个问题采取的方法和步骤 例：攒电脑 正确、简单 例：整理箱、自行车、测楼高、考试 分类： 数值算法－求数值解 非数值算法－排序、检索、档案管理 2.2 算法的特性 有穷性：算法要能够结束 确定性：对于确定的输入要有确定的结果 有效性：每一步都能有效的执行 输入不限：有、没有、很多 至少一个输出：一定要至少有一个结果 2.3 简单算法举例 将A瓶中的醋和B瓶中的酱油掉换 （不是脑筋急转弯） 求 1*2*3*4*5 S1：1*2=2 S2：2*3=6 S3：6*4=24 S4：24*5=120 求12+22+ …+n2 S1：12＝1 S2：22＝4 S3：1+4＝5 S4：32＝9 S5：5+9＝14 有50个学生,将成绩在80分以上者打印出来.ni代表第i个学生的学号,gi代表成绩 S1: i=1 S2: 如果gi =80,则打印 ni gi S3: i=i+1 S4: 如果i=50返回S2；否则，算法结束 判定2000-2500年中的每一年是否闰年，将结果输出 闰年条件： (1)能被4整除,不能被100整除的年份 (2)能被100整除,又能被400整除的年份 求1-1/2+1/3-1/4+…+1/99-1/100 S1:sign=1 S2:sum=1 S3:deno=2 S4:sign=(-1)*sign S5:term=sign*(1/deno) S6:sum=sum+term S7:deno=deno+1 S8:若deno=100 返回 S4;否则,结束 求1-1/2+1/3-1/4+…+1/99-1/100 S1:sum=0 S2:n=1 S3:sum=sum+1/n-1/(n+1) S4:n=n+2 S5:若n=100返回S3，否则，结束 给定一个大于或等于3的正整数,判断它是不是一个素数. S1: 输入n的值 S2: i=2 S3: n被i除,得余数r S4: 如果r=0,表示n能被i整除 打印n不是素数跳到S7算法结束 S5: i=i+1 S6: 如果i=n-1, 返回S3;否则打印n是素数 S7: 结束 穷举法 对问题的所有可能状态一一测试，直到找到解或将全部可能状态都测试过为止。 36块砖，36人一次搬完，男士一次搬4块，女士一次搬3块，两个小孩一次搬1块，求男士、女士、小孩各多少人？ 迭代法 不断用新值取代变量旧值，或由旧值递推出变量的新值的过程。 人口年增长率2％，现有12亿人口，10年后将有多少人？ for(i=1,s=12;i=10;i++)s=s*(1+2%); 起泡法 输入10个数，用“起泡法”对10个数排序（由小到大）。 “起泡法”算法：相邻数进行比较，将较大的放到后面，较小的往前放。 先进行第一、二个数比较，然后比较二三，然后是三四? ? ? ? ?以此类推。第一轮全部比较后，可以挑出最大的数并且放到了最后。 第二轮比较后，就将第二大的数放到了倒数第二位。 第三轮? ? ? ? ? 选择法 选择法对10个整数排序 选择法：（类似冒泡法）抓住一个元素a[0]不放，分别进行a[0]与a[1]~a[9]各个元素进行比较。 若a[0]小，则不做变动；若大则用最小的替换位置。在第一轮比较后a[0]就为最小的数。 进行第二轮比较，抓住a[1]，挑出第二小的。 第三轮 有局限性（单数项相加时？） 专用与通用的关系： “专”的效率高，但是没法适应其他情况 “通”的适应性好，可是效率不高 是一对矛盾，在遇到具体问题时应根据具体情况考虑 例如手机 2.4 算法的表示方法 用自然语言 用流程图 三种基本结构 用N-S流程图 用伪代码 用计算机语言 流程图表示 用一些框图表示各种操作 图例： 三种基本结构 顺序 选择 循环 一个入口 一个出口 每一部分都有可能被执行到 结构内不存在死循环 N－S流程图表示 经证明三种基本算法可以解决任何复杂算法结构，因此去除了流程线从而形成了N－S流程图。 优点：直观、形象、易于理解、易画 伪代码表示 例　求5!　伪代码表示如下： 开始 　置t的初值为1 　置i的初值为2 　当i=5，执行下面操作： 　　使t=t*I 　　使i=i+1(循环体到此结束) 　打印t的值 结束 例　打印2000-2500年中的每一年是否闰年 BEGIN(算法开始) 2000=y while y=2500 {if