《随堂优化训练2014年数学人教a版必修3配套课件：13算法案例数学备课大师网为您整理》由会员分享，可在线阅读，更多相关《随堂优化训练2014年数学人教a版必修3配套课件：13算法案例数学备课大师网为您整理（23页珍藏版）》请在金锄头文库上搜索。
1、1.3 算法案例,【学习目标】,1.理解辗转相除法与更相减损术求最大公约数的方法. 2.理解秦九韶算法中求多项式的值的步骤原理. 3.能利用除 k 取余法把十进制数化为 k 进制数.,1.辗转相除法的算法步骤 第一步，给定两个正整数 m，n(mn). 第二步，计算_除以_所得的_数 r. 第三步，mn，nr. 第四步，若 r0，则 m，n 的最大公约数等于_；否,则，返回第二步.,m,n,余,n,2.更相减损术的算法步骤 第一步，任意给定两个正整数，判断它们是否都是偶数.若 是用 2 约简；若不是，执行第二步. 第二步，以较大的数减去较小的数，接着把所得的差与 _比较，并以大数减小数.继续这个
2、操作，直到所得的数 _为止，则这个数(等数)或这个数与约简的数的乘积就 是所求的最大公约数.,较小的数,相等,3.秦九韶算法 把一个n次多项式f(x)anxnan1xn1a1xa0改写,成如下形式：,(anxn1an1xn2a1)xa0,f(x)anxnan1xn1a1xa0 _ (anxn2an1xn3a2)xa1)xa0 _.,(anxan1)xan2)xa1)xa0,求多项式的值时，首先计算最内层括号内的一次多项式的 值，即v1anxan1，然后由内向外逐层计算一次多项式的值，,即：,n,这样，求 n 次多项式 f(x)的值就转化为求_个一次多项 式的值.,v1anxan1， v2_，
3、v3v2xan3， vn_，,v1xan2,vn1xa0,4.进位制,(1)k进制数anan1a1a0(k)转化为十进制数为 _. (2)把十进制数化为 k 进制数用“_”，即把所给 的十进制数除以_，得到商数和余数，再用商数除以 k， 得到商数和余数，直到商数为_ ，把上面各步所得的 _从右到左排列，即得到 k 进制数.,除 k 取余法,k,0,余数,anknan1kn1a1ka0,【问题探究】,用秦九韶算法求多项式的值有什么优点？,答案：减少了做乘法运算的次数，优化了求多项式的值的,算法.,题型 1 最大公约数的求法 【例 1】 用辗转相除法求下面两数的最大公约数，并用更 相减损术检验你的
4、结果：,(1)80,36；,(2)294,84.,思维突破：辗转相除法的结束条件是余数为 0，更相减损 术的结束条件是差与减数相等.,解：(1)803628， 36844， 8420，,即 80 与 36 的最大公约数是 4. 验证：803644，,44368,36828,28820， 20812,1284,844， 80 与 36 的最大公约数是 4.,(2)29484342,84422， 即 294 与 84 的最大公约数是 42.,验证：294 与 84 都是偶数可同时除以2，即取147 与42,的最大公约数后再乘 2.,14742105,1054263， 634221,422121，,
5、294 与 84 的最大公约数为 21242.,辗转相除法求最大公约数的步骤较少，而更相减,损术运算简易，因此解题时要灵活运用.,【变式与拓展】,1.试用算法程序表示用辗转相除法求 144 与 60 的最大公约,数的算法.,解：程序如下：,m144 n60,DO,rm MOD n mn nr,LOOP UNTIL r0,PRINT m END,题型 2 秦九韶算法的应用,【例 2】 当 x3 时，求多项式 f(x)x5x3x2x1 的,值.,解：根据秦九韶算法，把多项式改写成如下形式：,f(x)x50x4x3x2x1 (x0)x1)x1)x1)x1.,按照从内到外的顺序，依次计算一次多项式当
6、x3 时的,值：v01，,v11303， v233110， v3103131， v4313194， v59431283.,所以当 x3 时，多项式的值为 283.,当多项式函数的中间出现空项时，应先补上系 数为 0 的相应项.解题时关键是能正确地改写多项式，然后由内 向外逐项计算.由于后项计算用到前项的结果，故要认真确保每 一项计算的准确性.,【变式与拓展】 2.利用秦九韶算法计算多项式 f(x)115x3x27x3 在,x 23 的值时，不会用到下列哪个值(,),D,A.161,B.3772,C.86 641,D.85 169,解析：f(x)115x3x27x3(7x3)x5x11. 所以当
7、x23时，v07； v172331613164； v2164235377253767； v33767231186 6411186 652.,题型 3 进制数之间的转化,【例 3】 (1)将 101 111 011(2)转化为十进制数； (2)将 1231(5)转化为七进制数.,思维突破：k进制数anan1a2a1a0(k)(0aik)转化为十进制数：anan1a2a1a0(k)anknan1kn1a2k2a1ka01.要将k进制数转化为n进制数(n，k10)，可先将 k 进制数转化为十进制数，然后再转化为所求的n进制数.,解：(1)101 111 011(2)12802712612512412
8、3022121120379(10). (2)1231(5)153252351191(10)， 1231(5)362(7).,【变式与拓展】,3.填空：,248,130,(1)11 111 000(2)_(10)； (2)154(6)_(7).,【例4】 已知f(x)x52x43x34x25x6，用秦九韶 算法求这个多项式当 x2 时的值时，做了几次乘法运算？几次 加法运算？,解：共做了 5 次乘法运算，5 次加法运算.,易错分析：用秦九韶算法计算多项式f(x)anxnan1xn1a1xa0.当xx0时，首先将多项式改写成f(x)(anx an1)xan2)xa1)xa0形式，然后再计算v1an
9、xan1，v2v1xan2，vnvn1xa0.因此，尽管an是1，但仍进行了5次乘法.,方法规律小结,1.辗转相除法与更相减损术求最大公约数的区别与联系.,2.秦九韶算法的优点.,(1)减少乘法运算的次数.,(2)规律性强，便于利用循环语句实现.,(3)不用对 x 做幂的运算，每次都是计算一个一次多项式的,值，提高了计算精度.,3.进位制的理解.,进位制是一种记数方式，用有限的数字在不同的位置表示 不同的数值.使用数字符号的个数称为基数，基数为 n，即称为 n 进位制，简称 n 进制.现在最常用的是十进制，通常使用 10 个 阿拉伯数字 09 进行记数.,对于任何一个数，我们可以用不同的进位制来表示.比如： 十进数 57，可以用二进制表示为 111 001，也可以用八进制表 示为 71，用十六进制表示为 39，它们所代表的数值都是一样的. 表示各种进制数时，一般要在数字右下角加注来表示.如 111 001(2)表示二进制数，34(5)表示五进制数.电子计算机一般都 使用二进制.,
