程序的灵魂——算法.ppt

第二章 程序的灵魂算法 2.1 算法的概念 2.2 简单算法举例（并入2.4讲） 2.3 算法的特性 2.4 怎样表示一个算法 2.5 结构化程序设计方法,C语言程序设计 第二章 程序的灵魂算法,本章要点 算法的概念 算法的表示 结构化程序设计方法,C语言程序设计 第二章 程序的灵魂算法,著名计算机科学家沃思（Nikiklaus Wirth）提出: 数据结构 + 算法 = 程序,一个程序应包括两个方面的内容：,对数据的描述：数据结构(data structure) 对操作的描述：算法(algorithm),描述对数据的操作步骤,描述数据的类型、组织形式,C语言程序设计 第二章 程序的灵魂算法,说明： 一个程序除以上两个主要因素外，还包括程序设计方法和语言工具两个方面。数据是加工的对象，算法是灵魂，语言是工具，编程需采用适当的方法。,2.1 算法的概念 做事方法、步骤（顺序）决定事情成败,C语言程序设计 第二章 程序的灵魂算法,1、算法的概念 例：把大象关冰箱分几步？ 求1+2+3+100=?,算法：计算机求解某一问题而采用的具体方法和 步骤,生活经验,思维逻辑,说明： 针对某一问题可能采取许多不同的方法，因此，为了有效解题，不仅需要保证算法正确，还要考虑算法质量，采用简单、步骤少又能准确完成任务的算法,C语言程序设计 第二章 程序的灵魂算法,2、计算机算法分为两大类： 数值运算算法：求数值解 计算机最初设计的目的，最初级功能 比较成熟，扩展性不强 非数值运算算法：常用于事务管理 日益广泛，远超过数值运算的应用 设计难度相对较大,3、算法的描述方法： 主要为两大类： 文字 图形（符号）,C语言程序设计 第二章 程序的灵魂算法,1、有穷性：一个算法应该包含有限的操作步 骤，不能是无限的，不能有死循环 2、确定性：每一个步骤都应该是确定的，不能 模棱两可，不可以产生“歧义性” 3、有零个或多个输入：在执行时从外界获得必 要的信息，也可以由系统直接获得 4、有一个或多个输出：每一个算法必须有至少 一个结果，但不一定需要打印输出 5、有效性：每一个步骤都应该有意义，能有效 地执行并得到确定的结果 当然还有可靠性、易维护性等特性,2.3 算法的特性,例如：若b=0，则执行a/b是不能有效执行的,例1.2 求两数之和 #include void main( ) int a,b,sum; a=123; b=456; sum=a+b; printf(“sum is %dn“,sum); ,一个算法得到的结果就是算法的输出,scanf(“%d%d“,2、流程图 灵活，自由，形象，直观，可表示任何算法 占用篇幅较长，对于复杂的算法，画流程图费 时、不方便，难于阅读和修改，看起来混乱,2.4 怎样表示一个算法 常用的算法描述方法： 1、带序号的自然语言描述 易懂，但文字冗长，易产生歧义性，描述分支、循环算法不方便,C语言程序设计 第二章 程序的灵魂算法,重点！,算法的描述方法： 主要为两大类： 文字 图形（符号）,除很简单的问题外，不用这种方法,3、N-S图（盒图） 特点：完全去掉了带箭头的流程线，算法的所有处理步骤都写在一个大矩形框里（算法简单，符合结构化思想） 处理框 判断框 循环框 形象、直观、易于理解、结构图紧凑易画、废除了流程线，整个算法结构是由各个基本结构按顺序组成的 当然在大的矩形框中还可以包含其它从属于它的框,C语言程序设计 第二章 程序的灵魂算法,4、伪代码（软件专业人员经常采用的方法） 用介于自然语言和计算机语言之间的文字及符号来描述算法 方便，易懂，书写格式自由，便于修改，易于向计算机语言过渡，不如流程图直观，可能会出现逻辑上的错误 以上四种都是算法设计 5、计算机语言（算法的实现） 必须严格遵循所用语言的语法规则,C语言程序设计 第二章 程序的灵魂算法,C语言程序设计 第二章 程序的灵魂算法,要求： 掌握N-S图、伪代码描述算法的方法，尤其是N-S图，现在结构化程序设计都用N-S图描述算法，传统流程图要求能够读懂、看明白、知道含义，对于简单程序经常用伪代码描述算法。课程目标就是能够用计算机语言实现算法。,自然语言描述,步骤1：先求12， 得到结果2 步骤2：将步骤1得到 的乘积2再乘以 3，得到结果6 步骤3：将6再乘以4， 得24 步骤4：将24再乘以5， 得120,例1 求12345，写出其算法,C语言程序设计 第二章 程序的灵魂算法,太繁琐了！,自然语言描述,例1 求12345，写出其算法,C语言程序设计 第二章 程序的灵魂算法,1*2=p p*3=q q*4=r r*5=t 结果存在t中,分析：,用循环算法求解,注意： S1、S2代表步骤1，步骤2 。S是Step(步)的缩写，这是写 算法的习惯用法,N-S图描述,例1 求12345，写出其算法,C语言程序设计 第二章 程序的灵魂算法,流程图描述,计算机语言描述,#include void main( ) int i,t; t=1; i=2; while(i=5) t=t*i; i=i+1; printf (“% dn“ ,t); ,例1 求12345，写出其算法,C语言程序设计 第二章 程序的灵魂算法,伪代码描述,开始 置t的初值为1 置i的初值为2 当i=5，执行下面操作: 使t=t*i 使i=i+1 循环体到此结束 输出t的值 结束,begin /*算法开始*/ 1=t 2=i while it i+1=i print t end /*算法结束*/,例2 把50个学生中成绩在80分以上学生的学号和成绩输出。,算法分析： 用n表示学生学号，n1代表第1个学生学号，ni代表第i个学生学号。 用g代表学生成绩， g1代表第1个学生成绩 gi代表第i个学生成绩。 用变量i作为下标，用它来控制序号(第几个学生，第几个成绩)。当i超过50时，表示已对50个学生的成绩处理完毕，算法结束。,C语言程序设计 第二章 程序的灵魂算法,自然语言描述,S1：1=i S2：如果gi80，则输出ni和gi，否则不输出 S3：i+1=i S4：如果i50，返回S2，继续执行；否则，算法结束。,例2 把50个学生中成绩在80分以上学生的学号和成绩输出。,C语言程序设计 第二章 程序的灵魂算法,流程图描述,外界输入学生学号、成绩,放到左侧图开始之后,例2 把50个学生中成绩在80分以上学生的学号和成绩输出。,C语言程序设计 第二章 程序的灵魂算法,N-S图描述,外界输入学生学号、成绩,放到左侧图的上面,例2 把50个学生中成绩在80分以上学生的学号和成绩输出。,C语言程序设计 第二章 程序的灵魂算法,计算机语言描述,#include void main( ) int i=1,n51; float g51; while(i=80.0) printf(“%d %fn “,ni,gi); i+; ,伪代码描述,begin /*算法开始*/ 1=i while i 50 if gi80 print ni and gi i+1=i end /*算法结束*/,begin /*算法开始*/ 1=i while i 50 input ni and gi i+1=i 1=i while i 50 if gi80 print ni and gi i+1=i end /*算法结束*/,例2 把50个学生中成绩在80分以上学生的学号和成绩输出。,C语言程序设计 第二章 程序的灵魂算法,例3 求1-1/2+1/3-1/4+1/99-1/100。,C语言程序设计 第二章 程序的灵魂算法,说明： 拿到一道题后，先观察、分析，不要急于入手，以 防走弯路或考虑不周。 本题中，分子都是1，分母递增，符号阶梯变化,例3 求1-1/2+1/3-1/4+1/99-1/100。,C语言程序设计 第二章 程序的灵魂算法,自然语言描述,流程图描述,S1：1=sign S2：1=sum S3：2=deno S4：(-1)*sign=sign S5：sign*(1/deno)=term S6：sum+term=sum S7：deno+1=deno S8：若deno100返回S4；否则算法结束。,用有含义的单词做变量名，使算法更易理解,denominator,C语言程序设计 第二章 程序的灵魂算法,N-S图描述,伪代码描述,例3 求1-1/2+1/3-1/4+1/99-1/100。,begin /*算法开始*/ 1= sum 2= deno 1= sign while deno 100 (-1)*sign=sign sign*1/deno=term sum+term=sum deno+1=deno print sum end /*算法结束*/,C语言程序设计 第二章 程序的灵魂算法,计算机语言描述,#include void main( ) int sign=1; float deno=2.0,sum=1.0,term; while (deno=100) sign=-sign; term=sign/deno; sum=sum+term; deno=deno+1; printf(“%f“,sum); ,例3 求1-1/2+1/3-1/4+1/99-1/100。,将课本例2.3、2.5,2.5 结构化程序设计方法 一、结构化程序设计的三种基本结构 1966年提出三种基本结构，用这三种基本结构作为表示一种良好算法的基本单元：顺序结构、选择结构、循环结构 任何复杂的算法都是由这三种基本结构按一定规律组成,C语言程序设计 第二章 程序的灵魂算法,顺序结构的图示：,操作步骤按书写的顺序执行 a=3; b=4; c=a+b;,顺序结构,C语言程序设计 第二章 程序的灵魂算法,如：例1.2,选择结构的图示：,例： if(n!=0) y=sin(x)/x; else y=1; 功能：求解分段函数,选择结构(分支结构),C语言程序设计 第二章 程序的灵魂算法,循环结构的图示：,C语言程序设计 第二章 程序的灵魂算法,两种循环结构的区别： 当型循环结构中的A可能一次也不执行，而直到型循环结构中的A至少会执行一次，不会出现一次也不执行的情况 例：,sum=0； i=1； while（i=100） sum+=i; i+; ,sum=0; i=1; do sum+=i; i+; while(i=100);,C语言程序设计 第二章 程序的灵魂算法,二、三种基本结构的共同特点 1、只有一个入口。 2、只有一个出口。 3、结构内的每一部分都有机会被执行到。 4、结构内不存在“死循环”(无终止的循环)。,C语言程序设计 第二章 程序的灵魂算法,三、结构化程序设计的方法 结构化程序：用高级语言表示的结构化算法 用三种基本结构组成的程序是结构化程序 优点：易编、易读、易懂、易修改、易维护 强调 程序设计风格 和 程序结构的规范化 基本思路：把一个复杂问题的求解过程分阶 段进行，每个阶段处理的问题都控制在 人们容易理解和处理的范围内 核心思想：自顶向下； 逐步细化；模块化设 计；结构化编码,C语言程序设计 第二章 程序的灵魂算法,比如：学校办公自动化系统,C语言程序设计 第二章 程序的灵魂算法,把每个专业作为一个模块，进行模块化设计,四、结构化程序设计的过程 1、确定算法：分析问题（建立数学模型、选择公式），写出算法描述 2、编写程序：用计算机语言实现算法的程序 3、上机调试：,C语言程序设计 第二章 程序的灵魂算法,例：张丘建算经中提出“百鸡问题”：鸡 翁一值钱五，鸡母一值钱三，鸡雏三值钱 一。百钱买百鸡，问鸡翁、母、雏各几何？ 分析：cocks+hens+chicks=100 5*cocks+3*hens+chicks/3=100 其中，0cocks19，0hens33，0chicks100 思路：依次取cocks值域中的值，然后求其余 两数，看是否符合题意 方法：累试法 枚举法,C语言程序设计 第二章 程序的灵魂算法,算法描述：（伪代码）,C语言程序设计 第二章 程序的灵魂算法,cocks=0 当cocks19时 找满足题意的hens、chicks数 cocks加1 ,细化,算法描述：（伪代码）,C语言程序设计 第二章 程序的灵魂算法,cocks=0 当cocks19时 hens=0 当hens33时 找满足题意的chicks数 hens数加1 cocks加1 ,细化,C语言程序设计 第二章 程序的灵魂算法,cocks=0 当cocks19时 hens=0 当hens33时 chicks=100-cocks-hens if(5*cocks+3*hens+chicks/100=100) 输出cocks、hens、chicks数 hens加1 cocks加1 ,用计算机语言实现算法、写出程序：,C语言程序设计 第二章 程序的灵魂算法,#include void main( ) int cocks=0,hens,chicks; /*变量定义与初始化*/ while(cocks=19) hens=0; while(hens=33) chicks=100-cocks-hens; if(5.0*cocks+3.0*hens+chicks/3.0=100.0) printf(“%d %d %dn“,cocks,hens,chicks); hens+; cocks+; ,附值语句,选择结构,循环结构,复合语句,内循环,编译、连接、运行程序 运行结果：,C语言程序设计 第二章 程序的灵魂算法,0 25 75 3