算法的基本方法.ppt

算法初步,淮海工学院,教学目的,了解算法与程序的基本概念掌握自然语言、流程图、伪代码等算法的表示方法掌握枚举、迭代、排序和查找等算法设计的基本方法,2,教学内容,算法与程序算法的基本概念算法的概念算法的表示算法设计的基本方法枚举法迭代法排序查找,3,一算法与程序,什么是程序？程序和算法的关系是怎样的？引例:从存放教职工档案的“d:zgxx.txt”文件中，显示出教龄满30年的女教工的姓名和所在部门,按一定的顺序安排的工作即操作序列描述完成某项功能所涉及的对象和动作规则,计算机学科中,程序描述了计算机处理数据、解决问题的过程,4,5,程序=数据结构+算法,程序包括两方面的内容：（1）对数据的描述:指定欲处理的数据类型和数据的组织形式，也就是数据结构。例如教职工的姓名,部门,教龄等都具有相应的数据类型文件d:zgxx.txt指定了数据的组织形式。（2）对操作的描述:指定操作步骤，例如“fopen”打开文件、“fscanf”读入数据、“If”判断是否满足条件等。这些操作的先后顺序以及它们所作用的数据，要遵守一定的规则，即求解问题的的算法。,二算法的概念,1什么是算法?计算机来解决的某一类问题的方法或步骤算法是程序的核心例:小球称重9个编号小球中有一个的质量偏小，其余的质量标准。用一天平,无需砝码，检出质量偏小的小球。,6,解法三：先将小球分成（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相等,则称量第三堆中,否则对偏轻的一堆继续称量。,7,哪种方法称量次数最少?,例:圆周率的计算(1)割圆法,8,S正12边形=12S=4,圆周率=S正12边形/R/R=3,公元3世纪，刘徽利用“割圆术”，也就是利用圆内接正六边形算起，依次将边数加倍，一直算到内接正3072边形的面积，从而得到圆周率的近似值为=3.1416，祖冲之把圆周率精确到小数点后15位,算法步骤：量出圆的半径R做圆的内接正n边形求小三角形的面积S求圆的内接正n边形面积S=Sn求圆周率=S/R/R结束,9,(2)利用求圆周率公式,同一个问题，可用不同的算法来求解算法不同，求解的效率不同选择效率高、容易理解和编程实现的算法,2算法的两个要素,算法是由操作与控制结构两个要素组成（1）操作算术运算：加、减、乘、除等。关系运算：大于、大于等于、小于、小于等于、等于、不等于等。逻辑运算：与、或、非等。数据传送：输入、输出、赋值等。,10,(a)顺序结构,(b)选择结构,（2）控制结构各操作之间的执行顺序顺序结构、选择结构、循环结构，称为算法的三种基本结构,11,(c)当型循环结构(d)直到型循环结构,12,从整体上看是顺序结构,13,打开文件,教龄30且性别为女？,从文件中读入一行,true,false,当型循环,3算法的特点,有穷性任意一个算法在执行有穷个计算步骤后必须终止。,每一个计算步骤，必须是精确地定义、无二义性,可行性有限多个步骤应该在一个合理的范围内进行,输入一般有0个或多个输入，它们取自某一特定的集合。,输出一般有若干个输出信息，是反映对输入数据加工后的结果。,14,4算法的分类（1）数值计算算法用于科学计算特点是少量的输入、输出，复杂的运算。例如：计算圆周率，积分（2）非数值计算算法对数据的管理特点是大量的输入、输出，简单的算术运算和大量的逻辑运算。例如：排序查找替换,随着计算机技术的发展和应用面的普及，非数值计算算法涉及面更广，研究的任务更重。,15,5算法的表示,自然语言传统流程图N-S流程图伪代码计算机语言,16,利用求圆周率公式计算圆周率,分析:对通项式：ti=，i=1，2，进行累加，直到某项ti绝对值小于精度即|t|=0.00000001)/当当前项还没有到达精度，继续求和pi=pi+t;/求和s=-1*s;/为下一项作准备，符号变化/i+;/t=s*1.0/(2*i-1);/下一项值coutsetprecision(8)pi*4endl;,只有用计算机语言编写的程序才能被计算机执行,必须严格遵循所选择的编程语言的语法规则,24,三常用算法,枚举法迭代法排序选择法冒泡法查找顺序查找二分查找,25,枚举法,亦称穷举法或试凑法。例：计算机破案张三在家中遇害，侦查中发现A、B、C、D四人到过现场。A说：“我没有杀人。”B说：“C是凶手。”C说：“杀人者是D”D说：“C在冤枉好人。”侦查员经过判断四人中有三人说的是真话，四人中有且只有一人是凶手，凶手到底是谁？,26,分析,用0表示不是凶手，1表示凶手，则每个人的取值范围就是0，1,27,算法,在每个人的取值范围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的为凶手，,要同时满足,28,例:安排考试,3门课程为A、B、C，考试安排在周一到周六，先考A，后考B，最后考C课程；一天只能安排一门课程考试；最后课程只能安排在周5或周6，请列出安排考试的所有方案。分析：解决该问题关键是根据安排日期的规定，每门课程搜索的日期范围不同；,ForA=1To4ForB=A+1To5/B课程总比A晚考ForC=5To6/C最早周5考If(Baj+1/若相邻两个次序不对aj与aj+1元素交换/则交换位置，小数上浮，大数下沉noswapfalse/一旦交换过，noswap设置为flaseIfnoswap数据已经有序提前结束/一轮比较结束，根据noswap值判断数据有序否,数据已经有序后,后续的比较可省略,查找,39,已知姓名,怎么查找某个学生?已知学号,怎么查找某个学生?,(1)顺序查找适用于无序序列，按顺序逐一比对。例：输入一个数key，查找它是否在数列中，如在，输出是第几个数。,40,(2)二分查找二分法查找只适合于在已排好序的数组中进行。待查区间的下界low为1，上界high为N。求待查区间中间元素的下标mid=(low+high)/2，x和amid比较。若x=amid，则查找完毕，结束程序；若xamid，low=mid+1；若xhigh无查找区域，找不到,41,42,思考题,利用二分法查找方法，设计人与计算机做猜数游戏。由计算机随机产生一个1，100的任意整数key，让用户猜这个数。利用二分法的思想,该怎样解决?请画出流程图,43,小结,什么叫算法？算法和程序的关系?算法的要素，算法的特征常见的算法表示形式，它们的优缺点。常用算法：枚举、迭代、排序、查找,44,思考题,1.根据下面的算法画出流程图，实现输入两个数并显示出其中的较大数。1）输入A，B两个数2）比较这两个数，判断哪个数大，将较大数放入BIG变量中3）显示较大数2.用伪代码和流程图编写一个算法，要求实现重复输入10数，显示每个数及其平方数。3.用伪代码和流程图编写一个算法，实现重复输入若干个学生的大学计算机课程考试成绩，并显