[经济学]第2章 算 法.ppt

第2章 程序的灵魂算法,（2学时）,利用计算机解决问题的过程,问题,确定数据结构,确定算法,程序包括：,数据描述数据结构 操作描述算法 (厨师做菜过程中，配料与菜谱的关系),程序=算法+数据结构+程序设计方法+ 计算机语言,程序=算法+数据结构 沃斯,2.1算法的概念,作任何事情都需要步骤 为解决一个问题而采取的方法和步骤算法。 本书中的算法计算机算法。 “由计算机执行” 分类：数值算法和非数值算法,2.2 简单算法举例,例2.1-I 求1234 5 人工解题(自然语言),通俗易懂，但文字冗长。如果求1231000，要写999个步骤，怎么办？,步骤1：先求12，得到结果2 步骤2：将步骤1得到的乘积2再乘以3，得到6 步骤3：将6再乘以4，得24 步骤4：将24再乘以5，得120,用计算机解题(自然语言) 设两个变量，p代表被乘数，i代表乘数，将每一步的乘积放在被乘数变量中。,S1：1=p S2：2=i S3：pip S4：i1i S5：若i=5，返回S3；否则，输出p值，结束。,求1357911,算法只需要做很少的改动。 (自然语言),思考：当S5改为：若i11，返回S3。这样会有什么问题？会得到什么结果？,S1：1= p S2：3= i S3：pip S4：i2i S5：若i=11，返回S3；否则，输出p值，结束。,例2.2 有50个学生 ，要求将他们之中成绩在80分以上者输出出来。,用n表示学生的学号,n1表示第一个学生的学号,ni表示第i个学生的学号,g表示学生的成绩， gi 代表第i个学生成绩。,(自然语言),S1：1i S2：如果gi 80 ，则输出 ni和gi，否则不输出 S3： i+1 i S4: 如果 i 50, 返回S2， 继续执行； 否则，算法结束。,例2.3判定20002500 年中的每一年是否为闰年,将结果输出.,闰年的条件 能被4整除,但不能被100整除.如:1996,2004 能被100整除, 又能被400整除.如:1600,2000 自然语言描述算法,S1：2000 y S2: 若y不能被4整除，则输出y“不是闰年”。然后转到S6。 S3：若y能被4整除，不能被100整除，则输出y“是闰年”,然后转到S6。 S4：若y能被100整除，又能被400整除，则输出y“是闰年”,然后转到S6。 S5：输出y“不是闰年” S6： y+1y S7: 当y=2500时，转S2继续执行，否则算法停止。,分析：设y为被检测的年份。,例2.4 求1-1/2+1/3-1/4+1/99-1/100,分析:用sign代表符号，sum代表最后结果，demo代表各项分母， term代表各项 自然语言描述算法,S1: sign = 1 S2: sum = 1 S3: demo = 2 S4:sign =(-1) sign S5:term = sign (1/demo) S6:sum = sum+term S7:demo=demo +1 S8:若demo=100,返回S4;否则算法结束。,例2.5 对一个大于或等于3的正整数，判断它是不是一个素数。,素数：除了1和本身之外，不能被其他任何整数整除的数。 判断方法:将n作为被除数,将2到(n-1)各个整数轮流作为除数,如果都不能被整除,则n是素数。 算法描述,S1：输入n的值 S2: i = 2 S3：n被i 除，得余数r S4：如果r=0，可以整除，则输出n“不是素数”，算法结束。否则执行S5 S5：i +1 i S6：如果i = n-1，则返回S3；否则输出n“是素数”，然后结束。,2.3 算法的特性,1.有穷性 有限的操作步骤。 合理范围：如果一种算法的执行时间是1000年，“有穷”，但超过了合理的限度。,2.3 算法的特性,2.确定性 每个步骤确定 步骤的结果确定 算法中的每一个步骤的目的应该是明确的，对问题的解决是有贡献的。,2.3 算法的特性,3.有零个或多个输入 输入指在执行算法时需要从上界取得必要的信息。 程序设计中的算法可以有输入，也可以没有输入。 4.有一个或多个输出 算法的目的是为了求解，“解”就是输出。,2.3 算法的特性,5.有效性 程序算法的每一步都应该能有效地执行，并有确定的结果。 例：若b=0,则a/b是无法执行的,算法：“黑箱子”,2.4.1 自然语言表示法,用自然语言叙述一个问题的求解过程。 汉语、英语等。 优点：通俗易懂。 缺点：冗长，歧义。,2.4 怎样表示一个算法,2.4.2 流程图表示法,用一些图框表示各种操作。 优点： 直观形象、易于理解。,连接点,注释框,例2.6 用流程图表示例2.1（求5！),开始,1=t,t*i=t,i5,结束,N,2=i,i=i+1,Y,输出t,图2.6,图2.7,例2.7 用流程图表示例2.2(有50个学生 ，要求将他们之中成绩在80分以上者输出出来)。,图2.8,Y,例2.8用流程图表示例2.3判定闰年。,Y,Y,Y,N,y不能被400整除,输出y“是闰年”,N,Y,N,N,图2.10,图2.11,例2.9用流程图表示例2.4。,1-1/2+1/3-1/4+1/5+1/99-1/100,图2.12,例2.10用流程图表示例2.5（对一个大于或等于3的正整数，判断它是不是一个素数）。,2.4.3 三种基本结构和改进的流程图,一、传统流程图的弊端 流程线 BS型算法 “a bowl of spaghetti” 可读性和可修改性 可靠性和可维护性 二、改进方法 顺序 规定基本结构，然后由这些基本结构按一定规律组成一个算法结构，整个算法的结构是由上而下地将各个基本结构顺序排列起来的。,图2.13,三、三种基本结构,定义 顺序结构：按照书写顺序依次执行语句。 选择结构：按照条件判断选择执行语句。 循环结构：通过条件控制循环执行语句。,顺序结构,选择/选取/分支结构,循环结构/重复结构,当型(while)循环结构,直到型(until)循环结构,当型循环,图2.18,图2.19,直到型循环,两图的作用相同？,三种基本结构的共同点 只有一个入口 只有一个出口 结构内的每一个框都有机会被执行 结构内没有死循环,2.4.4 N-S流程图表示算法,顺序、选择、循环结构,图2.28,每个结构中的框都可以是一个简单操作，也可以是三个基本结构之一。,N-S结构化流程图是对传统流程图的改进。在N-S结构化流程图中取消了流程线，规定算法只能自上而下执行，算法的全部描述过程封闭在一个方框内，规定算法只允许由顺序结构、选择结构和循环结构3种基本结构构成。,图2.29,例2.11用N-S图表示例2.1的求5！。,例2.12用N-S图表示例2.2。,图2.30,图2.31,图2.32,例2.13用N-S图表示例2.3判定2000-2005间的闰年。,例2.14用N-S图表示例2.4：,图2.33,1-1/2+1/3-1/4+1/5+ +1/99-1/100,例2.15:用N-S图表示例2.5判别素数。,图2.35,2.4.5 伪代码表示算法,用介于自然语言和计算机语言之间的文字和符号表示算法。 优点:易懂,较普遍. 汉字、英语、混合 建议：计算机语言中具有关键字的用英文表示，其它用汉字。,用伪代码表示算法“输出x的绝对值”,if x is positive then print x else print -x,若x为正 输出x 否则 输出-x,例 2.16:求5！,2.4.5 伪代码表示算法,开始 置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.17:输出出50个学生中成绩在80分以上者的学号和成绩。,BEGIN（算法开始） 1=i while ii 1=i while i=80 print ni and gi i+1 =i END （算法结束）,例 2.18:输出2000-2500年中每一年是否闰年。,BEGIN（算法开始） 2000=y while yy END （算法结束）,例 2.19:求1-1/2+1/3-1/4 + +1/99-1/100,BEGIN（算法开始） 1=sum 2=deno 1=sign while denosign sign*1/deno=term sum+term=sum deno+1=deno print sum END （算法结束）,2.4.6 计算机语言表示算法,严格遵守所用语言的语法规则 例2.20： 用C语言表示5！,#include void main() int i,t; t=1; i=2; while(i=5) t=t*i; i=i+1; printf(“%d”,t); ,例2.21 用C语言表示例2.19,#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)