苏教版高中数学必修3-1.4《算法案例》参考课件3

1、1.4算法案例算法案例学习目标学习目标1.体会三个案例的算法思想；体会三个案例的算法思想；2会用辗转相除法求两个正数的最大公约数会用辗转相除法求两个正数的最大公约数课堂互动讲练课堂互动讲练知能优化训练知能优化训练1.1.4 4算算法法案案例例课前自主学案课前自主学案课前自主学案课前自主学案温故夯基温故夯基1三种循环语句的一般形式分别是什么？三种循环语句的一般形式分别是什么？当型语句当型语句While P 循环体循环体 End While直到型语句直到型语句 Do 循环体循环体 UntilP End DoFor语句语句 For I from “初值初值”To“终值终值”SteP“步长步长” 循环

2、体循环体 End For2当型循环与直到型循环语句的区别当型循环与直到型循环语句的区别(1)当型循环是先判断当型循环是先判断(条件条件)，后执行，后执行(循环体循环体)，而，而直到型循环则是先执行直到型循环则是先执行(循环体循环体)，后判断，后判断(条件条件)(2)当型循环是当条件满足时执行循环体，不满足当型循环是当条件满足时执行循环体，不满足时结束循环，而直到型循环则是条件不满足时执时结束循环，而直到型循环则是条件不满足时执行循环体，条件满足时结束循环行循环体，条件满足时结束循环(3)直到型循环至少执行一次循环体，而当型循环直到型循环至少执行一次循环体，而当型循环可能一次也不执行循环体可能一

3、次也不执行循环体知新益能知新益能1辗转相除法辗转相除法所谓辗转相除法，就是对于给定的两个数，用较所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数，若余数不为零，则将余数大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时的较小的数就是原直到大数被小数除尽，则这时的较小的数就是原来两个数的来两个数的_最大公约数最大公约数2更相减损术更相减损术所谓更相减损术就是对于给定的两个数，以两数所谓更相减损术就是对于给定的两个数，以两数中较大的数减去较小的数，然后将差和较小的数中较大的数减去较小的

4、数，然后将差和较小的数构成一对新数，再用较大的数减去较小的数，反构成一对新数，再用较大的数减去较小的数，反复执行此步骤直到差和较小的数相等，此时相等复执行此步骤直到差和较小的数相等，此时相等的两数便为原来两数的的两数便为原来两数的_最大公约数最大公约数3中国剩余定理中国剩余定理(或孙子剩余定理或孙子剩余定理)其最早出现在我国其最早出现在我国算经十书算经十书之一的之一的孙子算孙子算经经中原文是：中原文是：“今有物不知其数，三三数之今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二问物几何？剩二，五五数之剩三，七七数之剩二问物几何？答曰：二十三答曰：二十三”自从自从孙子算经孙子算经中提出这个

5、中提出这个“物不知数物不知数”问题之后，它便引起了人们很大的兴问题之后，它便引起了人们很大的兴趣趣孙子算经孙子算经中给出了求解的关键步骤，南宋数中给出了求解的关键步骤，南宋数学家秦九韶对该问题加以推广，又发现了一种新学家秦九韶对该问题加以推广，又发现了一种新的算法，叫的算法，叫“大衍求一术大衍求一术”人们将这种问题的通人们将这种问题的通用解法称为用解法称为“_”或或“中国剩余定中国剩余定理理”孙子剩余定理孙子剩余定理4秦九韶算法秦九韶算法课堂互动讲练课堂互动讲练考点突破考点突破求两个数的最大公约数求两个数的最大公约数求两个正整数的最大公约数可用辗转相除法或更求两个正整数的最大公约数可用辗转相除

6、法或更相减损术二者的主要区别在于辗转相除法进行相减损术二者的主要区别在于辗转相除法进行的是除法运算，即辗转相除；而更相减损术进行的是除法运算，即辗转相除；而更相减损术进行的是减法运算，即辗转相减，它们在步骤上虽然的是减法运算，即辗转相减，它们在步骤上虽然略有不同，但在理论上是一致的，都是一个不断略有不同，但在理论上是一致的，都是一个不断的递归过程的递归过程 用辗转相除法求用辗转相除法求612与与468的最大公约数，的最大公约数，并用更相减损术检验所得结果并用更相减损术检验所得结果【思路点拨思路点拨】将将612作大数，作大数，468作小数，执行作小数，执行辗转相除法和更相减损术即可辗转相除法和更

7、相减损术即可【解解】用辗转相除法：用辗转相除法：6124681144,468144336,144364，即即612和和468的最大公约数是的最大公约数是36.用更相减损术：用更相减损术：612和和468为偶数，为偶数，两次用两次用2约简得约简得153和和117,15311736,1173681,813645,45369,36927,27918,1899，所以所以612和和468的最大公约数为的最大公约数为92236.【思维总结思维总结】辗转相除法是当大数被小数除尽辗转相除法是当大数被小数除尽时，结束除法运算，较小的数就是最大公约时，结束除法运算，较小的数就是最大公约数更相减损术是先判断两个数是

8、否均为偶数，数更相减损术是先判断两个数是否均为偶数，若是，用若是，用2约简，否则用大数减小数，当大数减约简，否则用大数减小数，当大数减小数的差等于小数时减法停止，则这个数小数的差等于小数时减法停止，则这个数(等数等数)或这个数与约简的数的乘积就是所求的最大公约或这个数与约简的数的乘积就是所求的最大公约数数自我挑战自我挑战1用辗转相除法、更相减损术求用辗转相除法、更相减损术求228,1995的最大公约数的最大公约数解：用辗转相除法：解：用辗转相除法：199582281712281171571713570所以：所以：57就是就是228和和1995的最大公约的最大公约数用更相减损术：数用更相减损术：

9、1995228176717672281539153922813111311228108310832288558552286276272283993992281712281715717157114114575757570则则57就是就是228,1995的最大公约数的最大公约数秦九韶算法秦九韶算法秦九韶算法适用于一般的多项式秦九韶算法适用于一般的多项式f(x)anxnan1xn1a1xa0的求值问题，秦九韶算法的特的求值问题，秦九韶算法的特点在于把求一个点在于把求一个n次多项式的值转化为求次多项式的值转化为求n个一次个一次多项式的值，即把求多项式的值，即把求f(x)anxnan1xn1a1xa0的

10、值转为求递推公式：的值转为求递推公式：通过一次式的反复计算，逐步得出高次多项式通过一次式的反复计算，逐步得出高次多项式的值，对于一个的值，对于一个n次多项式，只需做到次多项式，只需做到n次乘法次乘法和和n次加法运算即可，从而提高了运算效率次加法运算即可，从而提高了运算效率 用秦九韶算法求多项式用秦九韶算法求多项式f(x)3x58x43x35x212x6，当，当x2时的值时的值【思路点拨思路点拨】秦九韶算法的关键在于把秦九韶算法的关键在于把n次多项次多项式转化为求一次多项式的值，注意体会递推的实现式转化为求一次多项式的值，注意体会递推的实现过程过程【解解】根据秦九韶算法，把多项式改写成如下根据秦

11、九韶算法，把多项式改写成如下形式：形式：f(x)(3x8)x3)x5)x12)x6.按照从内到外的顺序，依次计算一次多项式当按照从内到外的顺序，依次计算一次多项式当x2时的值时的值v03，v1v02832814，v2v123142325，v3v225252555，v4v321255212122，v5v42612226238，当当x2时，多项式的值为时，多项式的值为238.【思维总结思维总结】利用秦九韶算法计算多项式的值，利用秦九韶算法计算多项式的值，关键是正确地将所给多项式改写，然后由内向外关键是正确地将所给多项式改写，然后由内向外逐次计算，由于后项计算需要用到前项的结果，逐次计算，由于后项计

12、算需要用到前项的结果，故应认真、细心，确保中间结果的准确性利用故应认真、细心，确保中间结果的准确性利用秦九韶算法计算多项式的值，通过列表则能简化秦九韶算法计算多项式的值，通过列表则能简化书写书写自我挑战自我挑战2用秦九韶算法求多项式用秦九韶算法求多项式f(x)8x75x63x42x1当当x2时的值时的值解：根据秦九韶算法，把多项式改写成如下形式：解：根据秦九韶算法，把多项式改写成如下形式：f(x)8x75x60 x53x40 x30 x22x1(8x5)x0)x3)x0)x0)x2)x1.按照从内到外的顺序，依次计算一次多项式当按照从内到外的顺序，依次计算一次多项式当x2时的值：时的值：v08

13、；v182521；v2212042；v3422387；v48720174；v517420348；v634822698；v7698211397.当当x2时，多项式的值为时，多项式的值为1397.进位制进位制进位制是人们为了计数和运算方便而约定的记数进位制是人们为了计数和运算方便而约定的记数系统，约定满二进一，就是二进制；满十进一，系统，约定满二进一，就是二进制；满十进一，就是十进制；满十二进一，就是十二进制；满六就是十进制；满十二进一，就是十二进制；满六十进一，就是六十进制，等等也就是说，十进一，就是六十进制，等等也就是说，“满满几进一几进一”就是几进制，几进制的基数就是几就是几进制，几进制的基

14、数就是几把十进制数化为把十进制数化为k进制数用进制数用“除除k取余法取余法”，即把所，即把所给十进制数除以给十进制数除以k，得到商和余数，再对商除以，得到商和余数，再对商除以k，得到商数和余数，直到商数为得到商数和余数，直到商数为0，把上面各步所，把上面各步所得的余数从下到上排列，即得到得的余数从下到上排列，即得到k进制数进制数 (本题满分本题满分14分分)(1)把二进制数把二进制数11011(2)化为化为十进制数；十进制数；(2)把十进制数把十进制数281化为二进制数化为二进制数【思路点拨思路点拨】按公式或步骤进行按公式或步骤进行【规范解答规范解答】(1)11011(2)1241230221

15、211682127.6分分(2) 281化为二进制数为化为二进制数为100011001(2).14分分【名师点评名师点评】(1)把二进制数化为十进制数的方把二进制数化为十进制数的方法：法：anan1a1a0(2)an2nan12n1a12a0.(2)把十进制数化为二进制数的方法：把十进制数化为二进制数的方法：把十进制数连续除以把十进制数连续除以2，直到商为，直到商为0为止同时将为止同时将各步的余数写出，将各步所得的余数倒序写出，各步的余数写出，将各步所得的余数倒序写出，即为所求的二进制数，称为除即为所求的二进制数，称为除2取余法取余法自我挑战自我挑战3(1)110010(2)化为十进制数为化为

16、十进制数为_(2)93化为二进制数为化为二进制数为_解析：解析：(1)110010(2)化为十进制数为化为十进制数为1251240230221203216250.(2) 93化为二进制数是化为二进制数是1011101(2)答案：答案：(1)50(2)1011101(2)1用辗转相除法求两数最大公约数时，是当大用辗转相除法求两数最大公约数时，是当大数恰好被小数整除时停止除法，这时的小数就是数恰好被小数整除时停止除法，这时的小数就是两数的最大公约数用更相减损术求两数最大公两数的最大公约数用更相减损术求两数最大公约数时，是当大数减小数恰好等于小数时停止减约数时，是当大数减小数恰好等于小数时停止减法，这时的小数就是两数的最大公约数求三个法，这时的小数就是两数的最大公约数求三个以上以上(含三个数含三个数)的数的最大公约数时，可依次通的数的最大公约数时，可依次通过求两个数的最大公约数与第三个数的最大公约过求两个数的最大公约数与第三个数的最大公约数来求得数来求得方法感悟方法感悟2利用秦九韶算法计算多项式的值关键是能正利用秦九韶算法计