重庆警院《计算机基础》课件第8章 算法和程序设计语言

第8章算法和程序设计语言教学目的了解算法与程序的基本概念掌握自然语言、流程图、伪代码等算法的表示方法掌握枚举、迭代、排序和查找等算法设计的基本方法学习内容算法与程序算法的基本概念算法的概念算法的表示算法设计的基本方法枚举法迭代法排序查找一算法与程序什么是程序？按一定的顺序安排的工作即操作序列描述完成某项功能所涉及的对象和动作规则计算机学科中,程序描述了计算机处理数据、解决问题的过程程序和算法的关系是怎样的？引例:从存放教职工档案的“d:\zgxx.txt”文件中，显示出教龄满30年的女教工的姓名和所在部门程序=数据结构+算法程序包括两方面的内容：（1）对数据的描述:指定欲处理的数据类型和数据的组织形式，也就是数据结构。例如教职工的姓名,部门,教龄等都具有相应的数据类型（2）对操作的描述:指定操作步骤，例如“fopen”打开文件、“fscanf”读入数据、“If”判断是否满足条件等。这些操作的先后顺序以及它们所作用的数据，要遵守一定的规则，即求解问题的的算法。二算法的概念1什么是算法?广义的说：计算机来解决的某一类问题的方法或步骤。在数学中：按照一定规则解决某一类问题的明确和有限的步骤，称为算法。算法是程序的核心计算机解决任何问题都要依赖于算法。只有将解决问题的过程分解为若干个明确的步骤,即算法,并用计算机能够接受的“语言”准确地描述出来，计算机才能够解决问题。•广播操图解是广播操的算法；•菜谱是做菜的算法；•歌谱是一首歌曲的算法；•空调说明书是空调使用的算法。我们身边的算法算法趣味案例1：有一个农夫带一条狼、一只羊和一筐白菜过河。如果没有农夫看管，则狼要吃羊，羊要吃白菜。但是船很小，只够农夫带一样东西过河。问农夫该如何解此难题？方法和过程：1、带羊到对岸，返回；2、带菜到对岸，并把羊带回；3、带狼到对岸，返回；4、带羊到对岸。算法趣味案例2:小球称重9个编号小球中有一个的质量偏小，其余的质量标准。用一天平,无需砝码，检出质量偏小的小球。解法三：先将小球分成（1，2，3，4）与（5，6，7，8）两堆，若两堆的质量的相等则偏小的小球是第9个，否则将偏轻的小球分成两堆进行称量。解法一：9个小球分成5堆，（1,2）,（3,4）,（5,6）,（7,8）,（9）解法二：可将9个小球分成3堆进行称量,(1,2,3),(4,5,6),(7,8,9),若1,2相等,则称量第三堆中,否则对偏轻的一堆继续称量。哪种方法称量次数最少?2算法的两个要素算法是由操作与控制结构两个要素组成（1）操作①算术运算：加、减、乘、除等。②关系运算：大于、大于等于、小于、小于等于、等于、不等于等。③逻辑运算：与、或、非等。④数据传送：输入、输出、赋值等。（2）控制结构各操作之间的执行顺序顺序结构、选择结构、循环结构称为算法的三种基本结构1.顺序结构程序按照语句的书写次序顺序执行。BA先执行A操作，再执行B操作，两者是顺序执行关系。2.选择结构通过判断特定条件，选择一个分支执行。当P条件成立时，执行A操作，否则执行B操作APB成立不成立语句不成立P成立当P条件成立时，执行语句操作，否则跳过语句操作逻辑判断3.循环结构在给定条件下，反复执行循环体，直到条件不满足为止.(1)形式a当型循环结构不成立PA成立当P条件成立时，反复执行A,直到P为零为止。逻辑判断逻辑判断(2)形式b直到型循环结构先执行A操作，再判断P是否成立，若P成立，再执行A，直到P不成立为止。AP成立不成立逻辑判断逻辑判断将例2求1+2+3+4+…+10的和用流程图进行描述。n+1=n1=ns+n=s0=sn≤10输出s是否算法举例--流程图描述3算法的特点有穷性任意一个算法在执行有穷个计算步骤后必须终止。每一个计算步骤，必须是精确地定义、无二义性可行性有限多个步骤应该在一个合理的范围内进行输入一般有0个或多个输入，它们取自某一特定的集合。输出一般有若干个输出信息，是反映对输入数据加工后的结果。4算法的分类（1）数值计算算法用于科学计算。特点是少量的输入、输出，复杂的运算。例如：计算圆周率，积分（2）非数值计算算法对数据的管理。特点是大量的输入、输出，简单的算术运算和大量的逻辑运算。例如：排序查找替换5算法的表示自然语言传统流程图N-S流程图伪代码计算机语言算法及其描述方法自然语言描述烧开水的过程o第一步，往壶内注水。o第二步，点火加热。o第三步，观察；如果水开，则停止燃火，否则继续燃火。o第四步，如果水未开，重复过程的第三步，直至水开。自然语言优点：容易理解缺点：冗长、二义性使用方法：粗线条描述算法思想利用求圆周率公式计算圆周率1119171513114π分析:对通项式：ti=，i=1，2，…，进行累加，直到某项ti绝对值小于精度即|t|10-8为止。1i21)1(1i图形符号名称功能终端框(起止框)表示一个算法的起始和结束输入、输出框表示一个算法输入和输出的信息处理框(执行框)判断某一条件是否成立,成立时在出口处标明“是”或“Y”；不”成立时标明“否”或“N”.判断框赋值、计算流程线连接程序框连接点连接程序框图的两部分传统流程图输出pi*4开始pi←0;s←1i←1;t←1|t|≥10-8pi←pi+ts←-1*si←i+1t←s*1/(2*i-1)结束falsetrue计算圆周率的流程图缺陷：制作费时优点:较好的体现程序设计的逻辑N-S流程图美国学者I.Nassi和B.Shneideman提出去掉了传统流程图中带箭头的流向线,全部算法以一个大的矩形框表示，该框内还可以包含一些从属于它的小矩形框适于结构化程序设计。结构化程序设计的三种基本结构具有以下共同的特点：只有一个入口；只有一个出口；结构内的每一部分都有机会被执行到；结构内不存在“死循环”。结构化程序设计的三种基本结构例：求1+2+3+4+…+10的和用N-S图进行描述。0s1n当n≤10时n+ssn+1n输出sn+1=n1=ns+n=s0=sn≤10输出s是否伪代码——介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。优点：表达能力强，抽象性强，容易理解。1.输入n;2.f=1;3.i=1;4.循环直到in结束4.1f=i*f;4.2i=i+1;5.输出f;BEGINpi←0//变量赋初值s←1i←1t←1While(|t|≥10-8){pi←pi+t//计算累加和s←-1*si←i+1t←s*1/(2*i-1)//计算通项}Printpi*4//输出圆周率值End有如下简单约定：用Begin开始、End结束；每一条指令占一行“//”标志表示注释输入/输出以Input/Print表示；用“”表示赋值；用缩进表示代码块结构，块中多句语句用一对{}括起；数组形式：数组名[下界‥上界]；数组元素：数组名[序号]；一些函数调用或者处理简单任务可以用一句自然语言代替。计算机语言#includeiostream.h//文件包含，作用为输入和输出#includeiomanip.h//文件包含，作用为输入和输出#includemath.h//包含数学函数voidmain(){ints,i;//s为控制正负号变化，i为第i项doublepi,t;//pi存放累加和项，t当前某项pi=0;s=i=1=t;;while(abs(t)=0.00000001)//当当前项还没有到达精度，继续求和{pi=pi+t;//求和s=-1*s;//为下一项作准备，符号变化/i++;//t=s*1.0/(2*i-1);//下一项值}coutsetprecision(8)pi*4endl;}只有用计算机语言编写的程序才能被计算机执行必须严格遵循所选择的编程语言的语法规则三常用算法枚举法迭代法排序选择法冒泡法查找顺序查找二分查找枚举法亦称穷举法或试凑法。例：计算机破案张三在家中遇害，侦查中发现A、B、C、D四人到过现场。A说：“我没有杀人。”B说：“C是凶手。”C说：“杀人者是D”D说：“C在冤枉好人。”侦查员经过判断四人中有三人说的是真话，四人中有且只有一人是凶手，凶手到底是谁？分析用0表示不是凶手，1表示凶手，则每个人的取值范围就是[0，1]算法在每个人的取值范围[0，1]的所有可能中进行搜索，如果表格的组合条件同时满足，即为凶手。相应的伪代码为：ForA=0to1ForB=0to1ForC=0to1ForD=0to1If((A=0)+(C=1)+(D=1)+(D=0))=3And(A+B+C+D=1)PrintA,B,C,D//输出的值是1的为凶手，要同时满足例:安排考试3门课程为A、B、C，考试安排在周一到周六，先考A，后考B，最后考C课程；一天只能安排一门课程考试；最后课程只能安排在周5或周6，请列出安排考试的所有方案。分析：解决该问题关键是根据安排日期的规定，每门课程搜索的日期范围不同；ForA=1To4ForB=A+1To5//B课程总比A晚考ForC=5To6//C最早周5考If(BC)//排除B=C的情况，不能在同一天考PrintA,B,C//输出的值是A、B、C分别安排的考试周的星期几综合案例：4位同学中有一位做了好事不留名，表扬信来了之后，校长问这4位是谁做的好事。A说：不是我。B说：是C。C说：是D。D说：他胡说。已知三个人说的是真话，一个人说的是假话。现在要根据这些信息，找出做了好事的人。问题分析：分别假设这个做好事的人为这四人中的一个，然后到每句话中去测试，看有几句话是真话，若有三句真话（第3、4条为互补规则，无法同时满足），则该人是要找的人。已知规则（转化为相应的表达式）：A说：不是我。对应（thisman!=‘A’）B说：是C。对应（thisman==‘C’）C说：是D。对应（thisman==‘D’）D说：他胡说。对应（thisman!=‘D’）o数据处理：判定每条规则的真假值（0或1），求取4条规则值之和。o循环部分：thisman=‘A’时，‘A’!=‘A’;假，值为0；‘A’==‘C’;假，值为0；‘A’==‘D’;假，值为0；‘A’!=‘D’;真，值为1；o判断部分：判断是否有三句真话，即求和值等于3时满足条件，终止循环。thisman换成下一个人开始结束this=‘D’thisman=‘A’4个表达式加求和sum是否打印thismansum==3是否枚举法基本思想:采用搜索的方法，根据题目的部分条件确定答案的大致搜索范围在此范围内对所有可能的情况逐一验证若某个情况符合题目的条件，则为本题的一个答案；若全部情况验证完后均不符合题目的条件，则问题无解。枚举法是一种比较熬时的算法。为提高效率，根据解决问题的情况，尽量减少内循环层数或每层循环次数。思考题:百元买百鸡问题。假定小鸡每只0.5元,公鸡每只2元，母鸡每只3元。现在有100元钱要求买100只鸡，列出所有可能的购鸡方案。搜索的范围?要满足的条件是什么？请尝试画出算法流程图枚举法问题分析与算法设计设：要买x只公鸡，y只母鸡，z只小鸡，可得到方程:x+y+z=100①5x+3y+z/3=100②取值范围：x：1～20y：1～33z:3～99迭代法又称递推法，利用问题本身所具有的某种递推关系求解问题。例：猴子吃桃问题小猴有桃若干，当天吃掉一半多一个；第二天接着吃了剩下的桃子的一半多一个；以后每天都吃尚存桃子的一半零一个，到第7天早上只剩下1个了，问小猴原有多少个桃子？设第n天的桃子为xn，它是前一天的桃子数的一半少1个，即xn-1=(xn+1)×2（递推公式）总结迭代法的基本思想:从初值出发，归纳出新值与旧值间直到最后值为止存在的关系，从而把一个复杂的计算过程转化为简单过程的多次重复，每次重复都从旧值的基础上递推出新值，并由新值代替旧值。思考题：高次方程求根求高次方程根：的近似解，精度ε为10-5