《2013年高考数学总复习 第1章1.4 算法案例课件 苏教版必修3》由会员分享，可在线阅读，更多相关《2013年高考数学总复习 第1章1.4 算法案例课件 苏教版必修3（30页珍藏版）》请在金锄头文库上搜索。
1、14 算法案例,学习目标,1.体会三个案例的算法思想； 2会用辗转相除法求两个正数的最大公约数,课堂互动讲练,知能优化训练,1.4 算法案例,课前自主学案,课前自主学案,1三种循环语句的一般形式分别是什么？ 当型语句 While P 循环体 End While 直到型语句 Do 循环体 Until P End Do For语句 For I from “初值”To“终值”SteP“步长” 循环体 End For,2当型循环与直到型循环语句的区别 (1)当型循环是先判断(条件)，后执行(循环体)，而直到型循环则是先执行(循环体)，后判断(条件) (2)当型循环是当条件满足时执行循环体，不满足时结束
2、循环，而直到型循环则是条件不满足时执行循环体，条件满足时结束循环 (3)直到型循环至少执行一次循环体，而当型循环可能一次也不执行循环体,1辗转相除法 所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时的较小的数就是原来两个数的_,最大公约数,2更相减损术 所谓更相减损术就是对于给定的两个数，以两数中较大的数减去较小的数，然后将差和较小的数构成一对新数，再用较大的数减去较小的数，反复执行此步骤直到差和较小的数相等，此时相等的两数便为原来两数的_,最大公约数,3中国剩余定理(或孙子剩余定理) 其最
3、早出现在我国算经十书之一的孙子算经中原文是：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二问物几何？答曰：二十三”自从孙子算经中提出这个“物不知数”问题之后，它便引起了人们很大的兴趣 孙子算经中给出了求解的关键步骤，南宋数学家秦九韶对该问题加以推广，又发现了一种新的算法，叫“大衍求一术”人们将这种问题的通用解法称为“_”或“中国剩余定理”,孙子剩余定理,4秦九韶算法,课堂互动讲练,求两个正整数的最大公约数可用辗转相除法或更相减损术二者的主要区别在于辗转相除法进行的是除法运算，即辗转相除；而更相减损术进行的是减法运算，即辗转相减，它们在步骤上虽然略有不同，但在理论上是一致的，都是一个
4、不断的递归过程,用辗转相除法求612与468的最大公约数，并用更相减损术检验所得结果 【思路点拨】 将612作大数，468作小数，执行辗转相除法和更相减损术即可 【解】 用辗转相除法： 6124681144,468144336,144364，即612和468的最大公约数是36. 用更相减损术： 612和468为偶数，两次用2约简得153和117,15311736,1173681,813645,45369,36927,27918,1899， 所以612和468的最大公约数为92236.,【思维总结】 辗转相除法是当大数被小数除尽时，结束除法运算，较小的数就是最大公约数更相减损术是先判断两个数是否
5、均为偶数，若是，用2约简，否则用大数减小数，当大数减小数的差等于小数时减法停止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数,自我挑战1 用辗转相除法、更相减损术求228,1995的最大公约数,解：用辗转相除法： 19958228171 228117157 1713570 所以：57就是228和1995的最大公约数用更相减损术： 19952281767 17672281539,15392281311 13112281083 1083228855 855228627 627228399 399228171 22817157 17157114 1145757 57570 则57就是
6、228,1995的最大公约数,秦九韶算法适用于一般的多项式f(x)anxnan1xn1a1xa0的求值问题，秦九韶算法的特点在于把求一个n次多项式的值转化为求n个一次多项式的值，即把求f(x)anxnan1xn1a1xa0的值转为求递推公式：,通过一次式的反复计算，逐步得出高次多项式的值，对于一个n次多项式，只需做到n次乘法和n次加法运算即可，从而提高了运算效率,用秦九韶算法求多项式f(x)3x58x43x35x212x6，当x2时的值 【思路点拨】 秦九韶算法的关键在于把n次多项式转化为求一次多项式的值，注意体会递推的实现过程,【解】 根据秦九韶算法，把多项式改写成如下形式： f(x)(3x
7、8)x3)x5)x12)x6. 按照从内到外的顺序，依次计算一次多项式当x2时的值v03， v1v02832814， v2v123142325， v3v225252555， v4v321255212122， v5v42612226238， 当x2时，多项式的值为238.,【思维总结】 利用秦九韶算法计算多项式的值，关键是正确地将所给多项式改写，然后由内向外逐次计算，由于后项计算需要用到前项的结果，故应认真、细心，确保中间结果的准确性利用秦九韶算法计算多项式的值，通过列表则能简化书写,自我挑战2 用秦九韶算法求多项式f(x)8x75x63x42x1当x2时的值 解：根据秦九韶算法，把多项式改写成
8、如下形式： f(x)8x75x60x53x40x30x22x1(8x5)x0)x3)x0)x0)x2)x1. 按照从内到外的顺序，依次计算一次多项式当x2时的值： v08；,v182521； v2212042； v3422387； v48720174； v517420348； v634822698； v7698211397. 当x2时，多项式的值为1397.,进位制是人们为了计数和运算方便而约定的记数系统，约定满二进一，就是二进制；满十进一，就是十进制；满十二进一，就是十二进制；满六十进一，就是六十进制，等等也就是说，“满几进一”就是几进制，几进制的基数就是几 把十进制数化为k进制数用“除k取
9、余法”，即把所给十进制数除以k，得到商和余数，再对商除以k，得到商数和余数，直到商数为0，把上面各步所得的余数从下到上排列，即得到k进制数,(本题满分14分)(1)把二进制数11011(2)化为十进制数； (2)把十进制数281化为二进制数 【思路点拨】 按公式或步骤进行,【规范解答】 (1)11011(2)1241230221211682127.6分,(2) 281化为二进制数为100011001(2).14分,【名师点评】 (1)把二进制数化为十进制数的方法： anan1a1a0(2)an2nan12n1a12a0. (2)把十进制数化为二进制数的方法： 把十进制数连续除以2，直到商为0为
10、止同时将各步的余数写出，将各步所得的余数倒序写出，即为所求的二进制数，称为除2取余法,自我挑战3 (1)110010(2)化为十进制数为_ (2)93化为二进制数为_,解析：(1)110010(2)化为十进制数为 125124023022120 32162 50.,(2) 93化为二进制数是1011101(2),答案：(1)50 (2)1011101(2),1用辗转相除法求两数最大公约数时，是当大数恰好被小数整除时停止除法，这时的小数就是两数的最大公约数用更相减损术求两数最大公约数时，是当大数减小数恰好等于小数时停止减法，这时的小数就是两数的最大公约数求三个以上(含三个数)的数的最大公约数时，可依次通过求两个数的最大公约数与第三个数的最大公约数来求得,2利用秦九韶算法计算多项式的值关键是能正确地将所给多项式改写，然后由内向外层逐层计算 3k进制数化为十进制数是把k进制数写成各位上的数字与k的幂的乘积之和的形式，再计算出结果即可 两个非十进制之间的转化，可借助于十进制数过渡转化，先将所给进制数转化为等值十进制数，再将所得的十进制数化为所求的进制数,
