1、1.3 算法案例登高揽胜 拓界展怀课前自主学习学 习 目 标1理解辗转相除法与更相减损术的含义，了解其执行过程2体会秦九韶算法的计算过程，并了解它提高计算效率的实质3理解进位制的概念，能进行不同进位制间的转化4了解进位制的程序框图和程序自主导学知识点一辗转相除法与更相减损术 阅读教材 P34P36 的内容，完成下列问题辗转相除法与更相减损术(1)辗转相除法：又叫欧几里得算法，是一种求两个正整数的 1 _的古老而有效的算法最大公约数(2)更相减损术：我国古代数学专著九章算术中介绍的一种求两个正整数的 2 _的算法最大公约数思考探究|辨别正误|1任意给定两个正整数，是否辗转相除法和更相减损术都可以
2、求它们的最大公约数？提示：是辗转相除法和更相减损术都能在有限步内结束，故均可以用来求两个正整数的最大公约数2求最大公约数时，如何选择辗转相除法和更相减损术？提示：当两个数大小差别不大时，两种方法的计算次数区别不大，只是辗转相除法以除法为主，更相减损术以减法为主；当两个数大小差别较大时，辗转相除法的计算次数明显较少，可选择辗转相除法功能一元 n 次多项式改写的形式计算方法用于计算 3_的值f(x)anxnan1xn1a1xa0 4 _(anxn2an1xn3a2)xa1xa0 5 _ _从括号最内层开始，由内向外逐层计算v1anxan1，v2v1xan2，v3 6 _，vnvn1xa0，这样，求
3、 n 次多项式 f(x)的值就转化为求 7 _的值知识点二|秦九韶算法 阅读教材 P37P39 的内容，完成下列问题秦九韶算法一元 n 次(anxn1an1xn2a1)xa0v2xan3n 个一次多项式(anxan1)xan2)xa1)xa0多项式思考探究|辨别正误|利用秦九韶算法求多项式 f(x)anxnan1xn1a1xa0 的值时，如何改写多项式，用这种方法，最多可进行多少次乘法，多少次加法？提示：可将多项式改写为 f(x)(anxan1)xan2)xan3)xa1)xa0，这样最多只需 n 次乘法和 n 次加法即可求出多项式的值知识点三|进位制与进位制之间的互化 阅读教材 P40P45
4、 的内容，完成下列问题1进位制进位制是人们为了 8 _和 9 _方便而约定的记数系统，“满几进一”就是 10 _制，11_制的基数就是 12 _计数运算几进几进几2其他进位制与十进制间的转化(1)其他进位制化成十进制其他进位制的数化成十进制时，表示成 13 _的形式(2)十进制化成 k 进制的方法“14 _”不同位上数字除k取余法与基数的幂的乘积之和思考探究|辨别正误|1如何将一个非十进制数转化为另一个非十进制数？提示：先把该数转化为十进制数，再用除 k 取余法转化为另一个非十进制数2不同进位制的数能比较大小吗？提示：进位制是人们为了计数和运算方便而约定的记数系统，不同进位制的数可以比较大小，
5、一般转化成十进制数比较大小更方便小试身手1用更相减损术求 294 和 84 的最大公约数时，需做减法运算的次数是()A2 B3C4 D5解析：选 C 29484210,21084126,1268442,844242，共做了 4 次减法运算2把十进制的 23 化成二进制数是()A00110(2)B10111(2)C10101(2)D11101(2)解析：选 B 232111，11251，5221，2210，1201，故 2310111(2)3把二进制数 110(2)化成十进制数为()A4 B5C6 D7解析：选 C 110(2)012122246.4将 389 化成四进制数的末位是()A1 B2
6、C3 D0解析：选 A 389 化成四进制数的运算过程如图，所得的四进制数是 12011(4)，其末位是 1.5用“辗转相除法”求得 459 和 357 的最大公约数是_解析：用辗转相除法：4593571102,357102351,102512，459 与 357 的最大公约数为 51.答案：516用秦九韶算法计算多项式 f(x)125x8x27x36x45x53x6 当 x4 时，v3 的值为_解析：v13(4)57，v2(7)(4)634，v334(4)7129.答案：1297已知函数 f(x)x32x25x8，利用秦九韶算法求 f(9)的值为_解析：f(x)x32x25x8(x2)x5)
7、x8，f(9)(92)95)98530.答案：530剖析题型 总结归纳课堂互动探究题型一 求最大公约数【例 1】用辗转相除法求 612 与 468 的最大公约数，并用更相减损术检验所得结果解 用辗转相除法：6124681144,468144336,144364，即 612 和 468 的最大公约数是 36.用更相减损术检验：612 和 468 为偶数，两次用 2 约简得 153 和 117，15311736,1173681,813645，45369,36927,27918,1899，所以 612 和 468 的最大公约数为 92236.方 法 总 结求最大公约数常用的两种方法(1)利用辗转相除
8、法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数(2)利用更相减损术求两个正整数的最大公约数的一般步骤是：首先判断两个正整数是否都是偶数若是，用 2 约简，也可以不除以 2，直接求最大公约数，这样不影响最后结果.11 624 与 899 的最大公约数为_解析：(1)1 6248991725,8997251174，725174429,174296，故 1 624 与 899 的最大公约数是 29，故填 29.答案：292用辗转相除法求 80 和 3
9、6 的最大公约数，并用更相减损术检验所得结果解：辗转相除法：803628,36844,842.故 80 和 36 的最大公约数是 4.用更相减损术检验：803644，44368，36828，28820，20812，1284，844，所以 80 和 36 的最大公约数是 4.题型二 秦九韶算法的应用【例 2】利用秦九韶算法分别计算 f(x)8x75x63x42x1 在 x2 与 x1 时的值，并判断多项式 f(x)在区间1,2有没有零点解 f(x)8x75x63x42x1(8x5)x0)x3)x0)x0)x2)x1，且 x2 时，v182521，v2212042，v3422387，v487201
10、74，v517420348，v634822698，v7698211 397.当 x2 时，f(x)1 397.同理可求当 x1 时，f(x)1.又f(1)f(2)1 3970，则多项式 f(x)在区间1,2上有零点.方 法 总 结秦九韶算法的算法步骤第一步，输入多项式次数 n、最高次项的系数 an 和 x 的值第二步，将 v 的值初始化为 an，将 i 的值初始化为 n1.第三步，输入 i 次项的系数 ai.第四步，vvxai，ii1.第五步，判断 i 是否大于或等于 0.若是，则返回第三步；否则，输出多项式的值 v.3用秦九韶算法求多项式 f(x)20.35x1.8x23x36x45x5x6
11、 在 x1 时的值时，令 v0a6，v1v0 xa5，v6v5xa0，则 v3 的值是_解析：f(x)(x5)x6)x3)x1.8)x0.35)x2，v01，v1v0 x56，v2v1x66(1)612，v3v2x315.答案：154利用秦九韶算法求多项式 f(x)x65x56x4x23x2当 x2 时的值解：将多项式变式为 f(x)(x5)x6)x0)x1)x3)x2，v01，v12(5)7，v27(2)620，v320(2)040，v440(2)181，v581(2)3159，v6159(2)2320.所以当 x2 时，多项式的值等于 320.题型三 进位制 多维探究 角度 1 k 进制数
12、化为十进制数【例 3】将下列各数化成十进制数(1)11001000(2)；(2)310(8)解(1)11001000(2)127126025024123022021020200.(2)310(8)382181080200.方 法 总 结k 进制数化为十进制数：先把 k 进制数写成不同位上的数字与 k 的幂的乘积之和的形式，再按十进制数的运算规则计算出结果角度 2 十进制数化 k 进制数【例 4】(1)试把十进制数 136 转化为二进制数；(2)试把十进制数 1234 转化为七进制数解(1)由于 1362680，682340，342170，17281，8240，4220，2210，1201.所以
13、 13610001000(2)(2)123471762，1767251，25734，3703.所以 1234 化为七进制数为 3412(7).方 法 总 结(1)应注意搞清每一次除法中的被除数、除数，当商为零时停止除法，把每步所得的余数倒着排成一个数，就是相应的二进制数(2)十进制化七进制数与化二进制数方法类似，要认真体会其原理角度 3 不同进制数之间的转化角度 3 不同进制数之间的转化【例 5】(1)下列各数 85(9)，301(5)，1000(4)中最小的数是_解析 85(9)8959072577.301(5)35205115075176.1000(4)14304204104064.所以
14、1000(4)最小答案 1000(4)(2)把四进制数 13022 化为六进制数解 先把四进制数 13 022 化为十进制数.13022(4)144343042241240256192082458.再把十进制数 458 化为六进制数所以 4582042(6)故 13022(4)2042(6).方 法 总 结非十进制数直接利用公式 anan1a1a0(k)anknan1kn1a1ka0 就可以转化为十进制数；k 进制数和 m 进制数之间需要用十进制数来转化，即先把 k 进制数转化为十进制数，再利用除 m 取余法转化为 m 进制数.5二进制数算式 1010(2)10(2)的值是()A1011(2)
15、B1100(2)C1101(2)D1000(2)解析：选 B 二进制数的加法是逢二进一，故选 B.6(1)把二进制数 101101(2)化为十进制数；(2)把十进制数 458 转化为四进制数解：(1)101101(2)1250241231220211203284145.所以二进制数 101101(2)转化为十进制数为 45.(2)所以 45813022(4)知识归纳 自我测评堂内归纳提升1理解 1 组区别和联系辗转相除法与更相减损术的联系和区别联系：(1)都是求最大公约数的方法(2)二者的实质都是递归的过程(3)二者都要用循环结构来实现区别：(1)计算上辗转相除法以除法为主，更相减损术以减法为
16、主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显(2)从结果体现形式来看，辗转相除法体现结果是以相除余数为 0 则得到，而更相减损术则以减数与差相等而得到2掌握 1 组特点秦九韶算法的特点秦九韶算法的特点在于把求一个n次多项式的值转化为求n个一次多项式的值，即把求 f(x)anxnan1xn1a1xa0的值转化为求递推公式：v0an，vkvk1xankk1，2，n.这样可以最多计算 n 次乘法和 n 次加法即可得多项式的值，和直接代入多项式相比减少了乘法的运算次数，提高了运算效率3掌握 3 个转化十进制与其他进制的转化(1)将 k 进制转化为十进制的方
17、法：先把 k 进制数写成各位上的数字与 k 的幂的乘积的形式，再按十进制的运算规则计算(2)将十进制化成 k 进制的方法：用除 k 取余法，用 k 连续去除十进制数所得的商，直到商为零为止，然后将各步所得的余数倒序写出，即为相应的 k 进制数(3)两个非十进制的数之间的转化，可以先化成十进制数，再化成另一进制的数，即将十进制作为“桥梁”自测检评1下列关于利用更相减损术求 156 和 72 的最大公约数的说法中正确的是()A都是偶数必须约简B可以约简，也可以不约简C第一步作差为 1567284；第二步作差为 728412D以上都不对解析：选 B 约简是为了使运算更加简捷，故不一定要约简，A 错；
18、C 中第二步应为 847212，故选 B.2用秦九韶算法计算多项式 f(x)6x65x54x43x32x2x7 在 x0.4 时的值时，需做加法和乘法的次数的和为()A10 B9C12 D8解析：选 C f(x)(6x5)x4)x3)x2)x1)x7，所以加法 6 次，乘法 6 次，所以 6612(次)，故选 C.3二进制数 1 101 111(2)化成十进制数是_解析：1101111(2)126125024123122121120111.答案：1114若 k 进制数 123(k)化成十进制数为 38，则 k_.解析：由 k 进制数 123 可知，k4.下面可用验证法：若 k4，则 38(10)212(4)，不合题意；若 k5，则 38(10)123(5)成立，所以 k5.答案：55分别用辗转相除法、更相减损术求 204 与 85 的最大公约数解：(1)用辗转相除法求 204 与 85 的最大公约数20485234，8534217，34172，因此，204 与 85 的最大公约数是 17.(2)用更相减损术求 204 与 85 的最大公约数由于 204 和 85 不都是偶数，所以 20485119，1198534，853451，513417，341717，因此，204 与 85 的最大公约数是 17.word部分：请做：课时分层训练水平达标 提升能力点此进入该word板块
