资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,主讲老师 潘学国,算法初步,算筹,算盘,计算器,计算机,中国古代数学中蕴涵了丰富的算法思想，算筹、算盘都是盛行一时的计算工具。如今，算法已经成为计算机科学的重要基础，同时计算机又是强大的实现各种算法的工具。,1.1,算法与程序框图,算法的概念,新课引入,请你说出登录腾讯,QQ,的步骤。,（电脑已经打开）,第一步：打开,QQ,程序。,第二步：输入,QQ,号码。,第三步：输入密码。,第四步：点击登录。,一人带着一只狼、一只羊和一箱蔬菜要过河，但只有一条小船。乘船时，每次只能带狼、羊和蔬菜中的一种。当有人在场时，狼、羊、蔬菜都相安无事。一旦人不在，狼会吃羊，羊会吃菜。请设计一个方案，安全地将狼、羊和蔬菜带过河。,趣味益智游戏,方法和过程：,1,、,带羊到对岸，返回；,2,、,带菜到对岸，并把羊带回；,3,、,带狼到对岸，返回；,4,、,带羊到对岸。,一般地，对于一类问题的机械式地、统一地、按部就班地求解过程称为,算法,(algorithm),。它是解决某一问题的程序或步骤。,所谓,“,算法,”,就是解题方法的精确描述。从更广义的角度来看，并不是只有,“,计算,”,的问题才有算法，日常生活中处处都有。如乐谱是乐队演奏的算法，菜谱是做菜肴的算法，珠算口诀是使用算盘的算法。,按照这样的理解,我们可以设计出很多具体数学问题的算法,.,下面看几个例子：,思考,：,回顾二元一次方程组有哪些解法？,导入新课,思考,请你写出解下面二元一次方程组的详细过程,.,分析：,解二元一次方程组的主要思想是消元的思想，有代入消元和加减消元两种消元的方法。下面分别用两种方法写出它的求解过程。,第一步，由,x2,，得,第二步，解得,第三步，,-x2,得,第四步，解得,第五步，得到方程组的解为,第一步，由，得,第二步，把代入得,第三步，由,得,第四步，把代入得,第五步，得到方程组的解为,加,减,消,元,代,入,消,元,第二步，由得，,第四步，由得，,第三步，,第一步，,，得,，,得,第五步，得到方程组的解为,能写出代入消元法解方程组的步骤吗？比较两种解法的步骤复杂程度。,思考：,你能写出解一般的二元一次方程组的步骤吗,？,思考：,根据上述分析，你能归纳出算法的概念吗？,在数学中，按照一定规则解决,某一类,问题的,明确,和,有限,的步骤称为算法。,现在，算法通常可以编成计算机程序，让计算机执行并解决问题。,讲授新课,思考：,有人对哥德巴赫猜想,“,任何大于,4,的偶数都能写成两个质数之和,”,设计了如下操作步骤：,第一步，检验,6=3+3,，,第二步，检验,8=3+5,，,第三步，检验,10=5+5,，,利用计算机无穷地进行下去！,请问：这是一个算法吗？,思考：,请你根据前面两个问题总结一下算法有哪些特点和要求？,1,、有限性：,一个算法应包括有限的操作步骤，能在执行有穷的操作步骤之后结束。,2,、确定性：,算法对每一个步骤都有确切的，能有效执行且得到确定结果的，不能模棱两可。,3,、顺序与可行性：,算法中的每下一个步骤都是在上一个步骤完成才能执行，并且每一步都是可以完成的。,4,、不唯一性：,求解某一个问题的算法不一定是唯一的，对于同一个问题可以有不同的算法。,5,、普遍性：,一个算法通常设计成能解决一类问题，不仅仅是解决一个问题。,1,、下列对算法描述正确的一项是（）,A.,某一个具体问题的一系列解决步骤,B.,数学问题的解题过程,C.,某一类问题的一系列解决步骤,D.,计算机程序,C,巩固练习,2,、算法具有精确性，指的是（）,A.,算法的步骤是有限的,B.,算法一定包含输出,C.,算法的每个步骤是具体的、可操作,D.,以上说法都不正确,C,3,、算法具有有穷性，指的是（）,A.,算法的每个步骤都是可执行的,B.,算法的步骤是有限的,C.,算法一定包含输出,D.,以上说法都不正确,B,4,、下列对算法描述正确的一项是（）,A.,算法只能用自然语言来描述,B.,算法只能用图形方式来表示,C.,同一问题可以有不同的算法,D.,同一问题的算法不同，结果必然不同,C,5,、下面关于算法的说法，正确的个数是,_.,(1),求解某一类问题的算法是唯一的,(2),算法必须在有限步操作之后停止,(3),算法的每一步操作必须是明确的，不能有歧义或模糊,(4),算法执行后一定产生确定的结果,3,例,1,：,(1),设计一个算法判断,7,是否为质数,.,(2),设计一个算法判断,35,是否为质数,.,典例剖析,算法分析：,根据质数的定义，依次用,26,除,7,，如果它们中的一个能整除,7,，则,7,不是质数，否则,7,是质数，类似地，也可以写出“,35,是否是质数”的算法。,例,1,：,(1),设计一个算法判断,7,是否为质数,.,(2),设计一个算法判断,35,是否为质数,.,第一步，用,2,除,7,，得到余数,1.,因为余数不为,0,，,所以,2,不能整除,7.,第二步，用,3,除,7,，得到余数,1.,因为余数不为,0,，,所以,3,不能整除,7.,第三步,用,4,除,7,，得到余数,3.,因为余数不为,0,，,所以,4,不能整除,7.,第四步,用,5,除,7,，得到余数,2.,因为余数不为,0,，,所以,5,不能整除,7.,第五步,用,6,除,7,，得到余数,1.,因为余数不为,0,，,所以,6,不能整除,7.,因此，,7,是质数,.,典例剖析,第一步,用,2,除,35,，得到余数,1.,因为余数不为,0,，,所以,2,不能整除,35.,第二步,用,3,除,35,，得到余数,2.,因为余数不为,0,，,所以,3,不能整除,35.,第三步,用,4,除,35,，得到余数,3.,因为余数不为,0,，,所以,4,不能整除,35.,第四步,用,5,除,35,，得到余数,0.,因为余数为,0,，,所以,5,能整除,35.,因此，,35,不是质数,.,例,1,：,(1),设计一个算法判断,7,是否为质数,.,(2),设计一个算法判断,35,是否为质数,.,思考,:,“,判断,1997,是否质数,”,的算法如下：,第,1,步,用,2,除,1997,得余数为,1,余数不为,0,所以,2,不能整除,1997;,第,2,步,用,3,除,1997,得余数为,2,余数不为,0,所以,3,不能整除,1997;,第,1995,步,用,1996,除,1997,得余数为,1,余数不为,0,故,1996,不能整除,1997;,所以,1997,是质数,.,上述算法正确吗？请说明理由,.,不正确。,算法分析：,对于整数,1997,，若用,i,表示,2,1996,中的任意整数，则判断整数,1997,是否为质数的算法包含下面的重复操作。,用,i,除,1997,，得到余数,r,，判断余数,r,是否为,0,，若是，则,1997,不是质数；否则，将,i,的值增加,1.,再执行同样的操作,.,这个操作一直要进行到,i,的值等于,1996,为止。,第一步：令,i=2,；,第二步：用,i,除,1997,得余数,r,；,第三步：判断“,r=0”,是否成立，若是，则,1997,不是质数，结束算法，否则，将,i,的值增加,1,，仍用,i,表示；,第四步：判断“,i1996”,是否成立，若是则,1997,是质数，结束算法，否则，返回第二步。,算法设计：,你能写出,“,判断整数,n(n,2),是否为质数,”,的算法吗？,思考？,算法分析：,对于任意的整数,n(n2),，若用,i,表示,2,（,n-1,）中的任意整数，则判断整数,n(n2),是否为质数的算法包含下面的重复操作。,用,i,除,n,，得到余数,r,，判断余数,r,是否为,0,，若是，则,n,不是质数；否则，将,i,的值增加,1.,再执行同样的操作,.,这个操作一直要进行到,i,的值等于（,n-1,）为止。,你能写出,“,判断整数,n(n,2),是否为质数,”,的算法吗？,第一步，给定大于,2,的整数,n;,第二步，令,i=2;,第三步，用,i,除,n,，得到余数,r;,第四步，判断余数,r,是否为,0,若是则,n,不是质数，结束算法；否则，将,i,的值增加,1,，仍用,i,表示,;,第五步，判断,i,是否大于,(n-1),，若是，则,n,是 质数；否则，返回第三步。,算法设计：,思考？,（,1,）请你,设计出求,1+2+3+4+5+6+7,的算法,.,巩固练习,第一步,:,计算,1+2,得,3;,第二步,:,将第一步结果,3+3,，得,6;,第三步,:,将第二步结果,6+4,，得,10;,第四步,:,将第三步结果,10+5,，得,15;,第五步,:,将第四步结果,15+6,，得,21,；,第六步,:,将第五步结果,21+7,，得,28.,第一步,取,n,=,7,;,第二步,计算,第三步,计算结果,28.,解法,2.,1+2+3+n=n(n+1)/2,解法,1.,按照逐一相加的程序进行,.,-,用公式运算,练习,2,：,有蓝和黑两个墨水，但现在却错把蓝墨水装在了黑墨水瓶中，黑墨水装在了蓝墨水瓶中，要求将其互换，请你设计算法解决这一问题,.,分析：,由于两个墨水瓶中的墨水不能直接交换，故可以考虑通过引入第三个空墨水瓶的办法进行交换。,第二步：将黑墨水瓶中的蓝墨水倒入白瓶中；,第三步：将,蓝墨水瓶中的黑墨水倒入黑瓶中；,第五步：交换结束。,第一步：取一只空墨水瓶，设其为白色；,第四步：将白,瓶中的蓝墨水倒入蓝瓶中；,练习,3,：,任意给定一个正实数，试设计一个,算法求以这个数为半径的圆的面积。,算法设计：,第一步，给定一个正实数,r,；,第二步，计算以,r,为半径的圆的面积 ；,第三步，得到圆的面积,s,。,练习,4,：,任意给定一个大于,1,的正整数,n,，试设计一个算法求出,n,的所有因数。,第一步，给定一个大于,1,的正整数,n,；,第二步，令,i=1,；,第三步，用,i,除,n,得余数,r,；,第四步，判断,“,r=0,”,是否成立：若是，则,i,是,n,的因数；否则，,i,不是,n,的因数；,第五步，使,i,的值增加,1,，仍用,i,表示,第六步，判断,“,in,”,是否成立，若是，则结束算法；,否则，返回第三步。,例,2,：,用二分法设计一个求方程,的近似根的算法,.,典例剖析,算法分析,：令,f(x)=x,2,-2=0(x0),则方程,x,2,-2=0,的解就是函数,f(x),的零点,.,二分法的基本思想,：把函数,f(x),的零点所在区间,a,b,（满足,f(a)f(b)0,）一分为二，得到,a,m,和,m,b.,根据,f(a)f(m)0,是否成立，取出零点所在的区间,a,m,或,m,b,仍记为,a,b.,对所得的区间,a,b,重复上述步骤，直到包含零点的区间,a,b,足够小，则,a,b,内的数可以作为方程的近似解,.,a,b,|a-b|,1,2,1,1,1.5,0.5,1.25,1.5,0.25,1.375,1.5,0.125,1.375,1.437 5,0.062 5,1.406 25,1.437 5,0.031 25,1.406 25,1.421 875,0.015 625,1.4140 625,1.421 875,0.007 812 5,1.414 062 5,1.417 968 75,0.003 906 25,当,d,=0.005,时，按照以上算法，可得下面表和图,.,第四步,若,f,(,a,),f,(,m,),0,则含零点的区间为,a,m,；,第二步，给定区间,a,，,b,，,满足,f,(,a,),f,(,b,),0,第三步,取中间点,第五步,判断,f,(,m,),是否等于,0,或者,a,b,的长度是否小于,d,，,若是，则,m,是方程的近似解,；,否则，返回第三步,将新得到的含零点的仍然记为,a,b,.,否则，含零点的区间为,m,b,.,算法设计：,第一步，令 ，给定精确度,d,.,y,=,x,2,-2,1,2,1.5,1.375,1.25,于是，开区
展开阅读全文