《算法的概念 公开课课件》由会员分享,可在线阅读,更多相关《算法的概念 公开课课件(25页珍藏版)》请在金锄头文库上搜索。
1、算法的概念,在中央电视台幸运52节目中,有一个猜商品价格的环节,竟猜者如在规定的时间内大体猜出某种商品的价格,就可获得该件商品.现有一商品,价格在0-8000元之间,采取怎样的策略才能在短的时间内说出正确(大体上)的答案呢?,第一步:报“4000”;,第二步:若主持人说高了(说明答案在04000之间),就报“2000”,否则(答数在40008000之间)报“6000”;,第三步:重复第二步的报数方法取中间数,直至得到正确结果.,先去括号,再乘除,后加减,1、,什么是算法呢?,简单地说,算法就是解决问题的程序或步骤。,什么是算法呢?,一般地, 按照一定规则解决某一类问题的明确和有限的步骤称为算法
2、(algorithm)。,按照这样的理解,我们可以设计出很多具体数学问题的算法.下面看几个例子:,所谓 “算法”就是解题方法的精确描述.从更广义的角度来看,并不是只有“计算”的问题才有算法,日常生活中处处都有.如乐谱是乐队演奏的算法,菜谱是做菜肴的算法,珠算口诀是使用算盘的算法.,它是解决某一类问题的程序或步骤.,第一步:,第二步:,第三步:,(消元),(解一元一次方程),+2,得 ,解得,(带入求解),将 代入,得,写一写,写出解第二个方程组的算法:,第一步:,第二步:,第三步:,解,得 ,将带入得,变一变,第一步:,第二步:,第三步:,解,得 ,将带入得,解得,-,一:两腿并拢,挺胸抬头,
3、三:先迈前腿,四:再迈后腿,下面的步骤表述明确吗?,你对以下的“算法”如何理解?,要把大象装冰箱,分几步?,答:分三步:,第一步:打开冰箱门,第二步:把大象装冰箱,第三步:关上冰箱门,问:,一位商人有9枚金币,其中有一枚略轻的假币,你能用天平(无砝码)将假币找出来吗?写出解决这一问题的算法。,第一步:把9枚金币平均分成三组,每组三枚。,先将其中的两组放在天平的两边,如果天平不平衡,那么假金币就在轻的那一组;如果天平左右平衡,则假金币就在未称量的那一组里。,取出含假币的那一组,从中任取两枚金币放在天平两边进行称量,如果天平不平衡,则假金币在轻的那一边;若平衡,则未称的那一枚就是假币。,第二步:,
4、第三步:,有人对歌德巴赫猜想“任何大于4的偶数都能写成两个奇质数之和”设计了如下操作步骤:,第一步:检验6=3+3,第二步:检验8=3+5,。,利用计算机无穷地进行下去!,请问,利用这种程序能够证明猜想的正确性吗?,第三步:检验10=5+5,这是一种算法吗?,在数学中,现代意义上的 “算法”通常是指可以用计算机来解决的某一类问题的程序或步骤,这些程序或步骤必须是明确和有效的,而且能够在有限步之内完成.,2.算法的要求,(1)写出的算法,必须能解决一类问题(例如解任意一个二元一次方程组),并且能重复使用;,(2) 算法过程要能一步一步执行,每一步执行的操作,必须确切,不能含混不清,而且在有限步之
5、内完成后能得出结果.,1.算法定义的理解,3.算法的基本特征:,明确性:算法对每一个步骤都有确切的,能有效执行且得到确定结果的,不能模棱两可。,有效性:算法从初始步骤开始,分为若干明确的步骤,每一步都只能有一个确定的继任者,只有执行完前一步才能进入到后一步,并且每一步都确定无误后,才能解决问题。,有限性:算法应由有限步组成,至少对某些输入,算法应在有限多步内结束,并给出计算结果,不唯一性:求解某一个问题的解法不一定是唯一的,对于同一个问题可以有不同的解法,例1.任意给定一个大于1的整数n,试设计一个程序或步骤对n是否为质数做出判定.,第一步:判断n是否等于2.若n=2,则n是质数;若n2,则执
6、行第二步.,第二步:依次从2(n1)检验是不是n的因数,即整除n的数,若有这样的数,则n不是质数;若没有这样的数,则n是质数.,评析:这是判断一个大于1的整数n是否为质数的最基本算法.,例题讲解,例2.用二分法设计一个求方程 x2-2=0 的近似根的算法.,第一步:令f(x)=x2-2,因为f(1)0,所以设a=1,b=2.,第二步:令m= , 判断f(m)是否为0.若是,则m为所求;若否,则继续判断f(a)f(m)大于0还是小于0.,算法分析:回顾二分法解方程的过程,并假设所求近似根与精确解的差的绝对值不超过0.005,则不难设计出以下步骤:,第三步:若f(a)f(m) 0,则令a=m;否则
7、,令b=m.,第四步:判断 |a-b|0.005是否成立?若是,则a或b(或任意值)为满足条件的近似根;若否,则返回第二步.,评析:实际上,上述步骤就是在求 的近似值.,于是开区间中的实数都是满足假设条件的原方程的近似根.,1.任意给定一个正实数,设计一个算法求以这个数为半径的圆的面积.,第一步:输入任意一个正实数r;,第二步:计算圆的面积: S=r2;,第三步:输出圆的面积S.,课堂练习,2.你要乘火车去外地办一件急事,请你写出从自己房间出发到坐在车厢内的三步主要算法.,第一步:去车站;,第二步:买车票;,第三步:凭票上车对号入座.,3.任意给定一个大于1 的正整数n,设计一个算法求出n的所
8、有因数.,第一步:依次以2(n-1)为除数去除n,检查余数是否为0,若是,则是n的因数;若不是,则不是n的因数.,第二步:在n的因数中加入1和n.,第三步:输出n的所有因数.,(P4 练习2),1.知识结构,算法的概念,算法的步骤,算法的特点,算法,课堂小结,2.算法的特点:思路简单清晰,叙述复杂,步骤繁琐,计算量大,完全依靠人力难以完成.而这些恰恰就是计算机的特长,它能不厌其烦地完成枯燥的、重复的繁琐的工作. 正因为这些,现代算法的作用之一就是使计算机代替人完成某些工作,这也是我们学习算法的重要原因之一.,课堂小结,3.设计算法的注意事项: (1)认真分析问题,联系解决此问题的一般数学方法;
9、 (2)综合考虑此类问题中可能涉及的各种情况; (3)借助有关的变量或参数对算法加以表达; (4)将解决问题的过程划分为若干个步骤; (5)然后用简练的语言将各个步骤表示出来.,现有有限个实数,怎样从中找出最大值?,先假定这些实数中的第一个数为“最大值”。,将这些实数中的下一个数与“最大值”比较,如果它大于此“最大值”,这时就假定“最大值”是这个实数。,如果还有其他实数,重复第二步。,一直到没有可比的数为止,这时假定的“最大值”就是这有限个实数的最大值。,第一步:,第二步:,第三步:,第四步:,思 考,算法1:,第二步:计算10150;,第三步:写出运算结果,算法2:,第一步:取n=100;,第二步:计算,第三步:写出运算结果,写出求1+2+3+ +100的一个算法,(1+100)+(2+99)+ +(50+51);,第一步:将原式变形为,你会了吗?,