1、11.3 算法案例算法案例 典例精析 题型一 求最大公约数 【例 1】(1)用辗转相除法求 840 与 1 764 的最大公约数； (2)用更相减损术求 440 与 556 的最大公约数. 【解析】(1)用辗转相除法求 840 与 1764 的最大公约数： 1764840 284， 84084 100. 所以 840 与 1 764 的最大公约数是 84. (2)用更相减损术求 440 与 556 的最大公约数： 556440116， 440116324， 324116208， 20811692， 1169224， 922468， 682444， 442420， 24204， 20416， 1
2、6412， 1248， 844. 所以 440 与 556 的最大公约数是 4. 【点拨】(1)辗转相除法与更相减损术是求两个正整数的最大公约数的方法，辗转相除法用较大的数除以较小的数，直到大数被小数除尽结束运算，较小的数就是最大公约数；更相减损术是用两数中较大的数减去较小的数，直到所得的差和较小数相等为止，这个较小数就是这两个数的最大公约数.一般情况下，辗转相除法步骤较少，而更相减损术步骤较多，但运算简易，解题时要灵活运用. (2)两个以上的数求最大公约数，先求其中两个数的最大公约数，再用所得的公约数与其他各数求最大公约数即可. 【变式训练 1】求 147,343,133 的最大公约数. 【
3、解析】先求 147 与 343 的最大公约数. 343147196， 19614749， 1474998， 984949， 所以 147 与 343 的最大公约数为 49. 再求 49 与 133 的最大公约数. 1334984， 844935， 493514， 351421， 21147， 1477. 所以 147,343,133 的最大公约数为 7. 题型二 秦九韶算法的应用 【例 2】用秦九韶算法写出求多项式f(x)1x0.5x20.016 67x30.041 67x40.008 33x5在x0.2 时的值的过程. 【解析】先把函数整理成f(x)(0.008 33x0.041 67)x0
4、.166 67)x0.5)x1)x1，按照从内向外的顺序依次进行. x0.2， a50.008 33， v0a50.008 33； a40.041 67， v1v0 xa40.04； a30.016 67， v2v1xa30.008 67； a20.5， v3v2xa20.498 27； a11， v4v3xa10.900 35； a01， v5v4xa00.819 93； 所以f(0.2)0.819 93. 【点拨】秦九韶算法是多项式求值的最优算法，特点是： (1)将高次多项式的求值化为一次多项式求值； (2)减少运算次数，提高效率； (3)步骤重复实施，能用计算机操作. 【变式训练 2】用
5、秦九韶算法求多项式f(x)8x75x63x42x1 当x2 时的值为 . 【解析】1 397. 题型三 进位制之间的转换 【例 3】(1)将 101 111 011(2)转化为十进制的数； (2)将 53(8)转化为二进制的数. 【解析】(1)101 111 011(2)1 280 271 261 251 241 230 221 211379. (2)53(8)5 81343. 所以 53(8)101 011(2). 【点拨】将k进制数转换为十进制数，关键是先写成幂的积的形式再求和，将十进制数转换为k进制数，用“除k取余法”，余数的书写是由下往上，顺序不能颠倒，k进制化为m进制(k，m10)，
6、可以用十进制过渡. 【变式训练 3】把十进制数 89 化为三进制数. 【解析】具体的计算方法如下： 893 292， 293 92， 93 30， 33 10， 13 01， 所以 89(10)10 022(3). 总结提高 1.辗转相除法和更相减损术都是用来求两个数的最大公约数的方法.其算法不同，但二者的原理却是相似的，主要区别是一个是除法运算，一个是减法运算，实质都是一个递推的过程.用秦九韶算法计算多项式的值，关键是正确的将多项式改写，然后由内向外，依次计算求解. 2.将k进制数转化为十进制数的算法和将十进制数转化为k进制数的算法操作性很强， 要掌握算法步骤，并熟练转化；要熟练应用“除基数，倒取余，一直除到商为 0”.