1.1.1算法的概念.ppt

1、1.1.1 算法的概念,普通高中课程标准实验教科书 人教A版数学必修3第一章 算法初步,在中央电视台幸运52节目中,有一个猜商品价格的环节,竟猜者如在规定的时间内大体猜出某种商品的价格,就可获得该件商品.现有一商品,价格在0-8000元之间,采取怎样的策略才能在短的时间内说出正确(大体上)的答案呢?,第一步:报“4000”；,第二步:若主持人说高了(说明答案在04000之间),就报“2000”,否则(答数在40008000之间)报“6000”；,第三步:重复第二步的报数方法取中间数,直至得到正确结果.,先去括号,再乘除,后加减,1、,什么是算法呢？,2 两个男孩和两个女孩一起渡河，渡口只有一条

2、小船每次只能渡1 个男孩或两个女孩，他们四人都会划 船，但都不会游泳试问他们怎样渡过河去？请写出一个渡河方案。,S1 两个女孩同船过河去；,S2 一个女孩划船回来；,S3 一个男孩划船过河去；,S4 对岸的女孩划船回来；,S5 两个女孩同船渡过河去；,S6 一个女孩划船回来；,S7 余下的一个男孩独自划船渡过河去； 对岸的女孩划船回来；,S8 两个女孩再同时划船渡过河去。,智力大比拼,什么是算法呢？,讨论,第一步：,第二步：,第三步：,（消元）,（解一元一次方程）,+2，得 ,解得,（带入求解）,将 代入,得,写一写,写出解第二个方程组的算法：,第一步：,第二步：,第三步：,解，得 ,将带入得

3、,变一变,第一步：,第二步：,第三步：,解，得 ,将带入得,解得,-,一：两腿并拢，挺胸抬头,三：先迈前腿,四：再迈后腿,下面的步骤表述明确吗？,你对以下的“算法”如何理解？,要把大象装冰箱，分几步？,答：分三步：,第一步：打开冰箱门,第二步：把大象装冰箱,第三步：关上冰箱门,问：,显然有个问题：大像可以装进冰箱里吗？这个算法有效吗？,一位商人有9枚银元，其中有1枚略轻的是假银元。你能用天平（不用砝码）将假银元找出来吗？,解: 1.把银元分成3组，每组3枚。,2先将两组分别放在天平的两边。如果天平不平衡，那边假银元就放在轻的那一组；如果天平左右平衡，则假银元就在末称的第3组里。,3取出含假银元

4、的那一组，从中任取两枚放在天平的两边。如果左右不平衡，则轻的那一边就是假银元；如果天平两边平衡，则末称的那一枚就是假银元。,演示,有人对歌德巴赫猜想“任何大于4的偶数都能写成两个奇质数之和”设计了如下操作步骤：,第一步：检验6=3+3,第二步：检验8=3+5,。,利用计算机无穷地进行下去！,请问，利用这种程序能够证明猜想的正确性吗？,第三步：检验10=5+5,这是一种算法吗？,狭义而言,算法是专指用计算机解决某一问题的方法和步骤.著名计算机科学家D.E.Knuth在其计算机程序设计技巧一书中为算法所下的定义是：“一个算法,就是一个有穷规则的集合,其中之规则规定了一个解决某一特定类型问题的运算系

5、列”.,一般地, 按照一定规则解决某一类问题的明确和有限的步骤称为算法(algorithm)。,1. 算法的概念,有限性： 一个算法的步骤序列是有限的，它应在有限步操作之后停止，而不能是无限地执行下去。,确定性： 算法中的每一步应该是确定的并且能有效地执行且得到确定的结果，而不应当是模棱两可的。,不唯一性： 求解某一个问题的算法不一定只有唯一的一个，可以有不同的算法。,2.算法的特征：确定性、有限性、有效性 、不唯一性,有效性：必须能解决一类问题(例如解任意一个二元一次方程组),并且能重复使用。,3.算法的要求,(1)写出的算法,必须能解决一类问题(例如解任意一个二元一次方程组),并且能重复使

6、用;,(2) 算法过程要能一步一步执行,每一步执行的操作,必须确切,不能含混不清,而且在有限步之内完成后能得出结果.,例1 （1）设计一个算法，判断7是否为质数。 第一步，用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是否为质数。 第一步，用2除35，得到余数1.因为余数不为0，

7、所以2不能整除35. 第二步，用3除35，得到余数2.因为余数不为0，所以3不能整除35. 第三步，用4除35，得到余数3.因为余数不为0，所以4不能整除35. 第四步，用5除35，得到余数0.因为余数为0，所以5能整除35.因此，35不是质数.,任意给定一个大于1的整数n，试设计 一个程序或步骤对n是否为质数作出判断。,第一步：给定大于2的整数n,第二步:,第三步:,第四步:,第五步:,例题,例2.用二分法设计一个求方程 x2-2=0 的近似根的算法.,算法分析:回顾二分法解方程的过程,并假设所求近似根与精确解的差的绝对值不超过0.005,则不难设计出以下步骤：,1二分法的概念 对于在区间a

8、，b上连续不断且_的函数yf(x)，通过不断地把函数f(x)的零点所在的区间_，使区间的两个端点_，进而得到零点近似值的方法叫做二分法 由函数的零点与相应方程根的关系，我们可用二分法来求方程的_,f(a)f(b)0,一分为二,逐步逼近零点,近似解,2给定精确度，用二分法求函数f(x)零点近似值的步骤 (1)确定区间a，b，验证_，给定精确度； (2)求区间(a，b)的中点c，c_； (3)计算f(c)： 若f(c)0，则c就是函数的零点；,f(a)f(b)0,若f(a)f(c)0，则令bc(此时零点x0_)； 若f(c)f(b)0，则令ac(此时零点x0_)； (4)判断是否达到精确度：即若_，则得到零点近似值a(或b)；否则重复(2)(4),(a，c),(c，b),|ab|,例2.用二分法设计一个求方程 x2-2=0 的近似根的算法.,算法分析:回顾二分法解方程的过程,并假设所求近似根与精确解的差的绝对值不超过0.005,则不难设计出以下步骤：,解,解,评析:实际上,上述步骤就是在求 的近似值.,任意给定一个正实数a，试设计一个算法求以a为直径的圆的面积.,第一步：输入a