1、第一章 算法初步 1.3 算法案例 学 习 目 标核 心 素 养 1会用辗转相除法与更相减损术求两数的最大公约数(重点、易混点)2会用秦九韶算法求多项式的值(重点)3会在不同进位制间进行相互转化(难点)1通过古代传统算法，培养数学运算素养2借助算法案例，提升逻辑推理素养.自 主 预 习 探 新 知 1辗转相除法与更相减损术(1)辗转相除法辗转相除法是用于求 的一种算法，这种算法是由欧几里得在公元前 300 年左右首先提出的，因而又叫 两个正整数的最大公约数欧几里得算法所谓辗转相除法，就是对于给定的两个数，用 除以 若余数不为零，则将 构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时
2、就是原来两个数的最大公约数较小的数较大的数较小的数余数和较小的数(2)更相减损术更相减损术是我国古代数学专著 中介绍的一种求两数最大公约数的方法其基本过程是：第一步，任意给定两个正整数，判断它们是否都是偶数若是，用 约简；若不是，执行第二步第二步，以较大的数 较小的数，接着把所得的差与较小的数比较，并以大数减小数继续这个操作，直到所得的数 为止，则这个数或这个数与约简的数的 就是所求的最大公约数乘积九章算术2减去相等2秦九韶算法把一个 n 次多项式 f(x)anxnan1xn1a1xa0 改写成如下形式：f(x)(anxan1)xan2)xa1)xa0.求多项式的值时，首先计算 括号内一次多项
3、式的值，即 v1anxan1，然后 逐层计算一次多项式的值，即 v2v1xan2，v3v2xan3，vnvn1xa0，这种求 n 次多项式 f(x)的值的方法叫秦九韶算法由内向外最内层3进位制(1)进位制是人们为了 和 而约定的记数系统“满 k进一”就是 ，k 进制的基数是 .(2)将 k 进制数化为十进制数的方法是：先把 k 进制数写成 的 形 式，再 计数运算方便k进制k各位上的数字与k的幂的乘积之和按照十进制数的运算规则计算出结果(3)将 十 进 制 数 化 为 k 进 制 数 方 法 是：即 ，直 到 商 为 零 为 止，然后 就是相应的 k 进制数把各步得到的余数倒排写出除k取余法用
4、k连续去除十进制数所得的商1在对 16 和 12 求最大公约数时，整个操作如下：16124,1248,844.由此可以看出 12 和 16 的最大公约数是()A4 B12C16D8A 根据更相减损术的方法判断2下列有可能是 4 进制数的是()A5123B6542C3103D4312C 4 进制中逢 4 进 1，每位上的数字一定小于 4.3已知多项式 f(x)4x53x42x3x2x12，用秦九韶算法求f(2)等于()A1972B1972C1832D1832A f(x)(4x3)x2)x1)x1)x12，f(2)1972.4利用辗转相除法求 3 869 与 6 497 的最大公约数时，第二步是_
5、3 8692 62811 241 第一步应为 6 4973 86912 628；第二步应为 3 8692 62811 241.合 作 探 究 释 疑 难 求最大公约数【例 1】求 228 与 1995 的最大公约数思路点拨：求两个正整数的最大公约数可以用辗转相除法，也可以用更相减损术 解 法一：(辗转相除法)1 9958228171,228117157,171357，所以 228 与 1 995 的最大公约数为 57.法二：(更相减损术)1 9952281 767,1 7672281 539，1 5392281 311,1 3112281 083，1 083228855,855228627，6
6、27228399,399228171，22817157,17157114，1145757.所以 228 与 1 995 的最大公约数为 57.求最大公约数的两种方法 1利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数.2利用更相减损术求两个正整数的最大公约数的一般步骤是：第一步判断两个正整数是否都是偶数，若是，用 2 约简，也可以不除以 2，直接求最大公约数，这样不影响最后结果.第二步，以较大的数减去较小的数，接着把所得的差与较小的数
7、比较，并以大数减小数，继续这个操作，直到所得的数相等为止，则这个数等数或这个数与约简的数的乘积就是所求的最大公约数.跟进训练1用辗转相除法和更相减损术求 1 515 与 600 的最大公约数，需要运算的次数分别为()A4,15 B5,14C5,13D4,12B 辗转相除法：1 5156002315；6003151285,315285130,28530915,30152，故最大公约数为 15，且需计算 5 次 用更相减损术：1 515600915,915600315,600315285,31528530,28530255,25530225,22530195,19530165,16530135,1
8、3530105,1053075,753045,453015,301515.故最大公约数为 15，且需计算 14 次秦九韶算法【例 2】已知一个 5 次多项式为 f(x)4x52x43.5x32.6x21.7x0.8，用秦九韶算法求这个多项式当 x5 时的值思路点拨：可根据秦九韶算法的原理，将所给的多项式改写，然后由内到外逐次计算 解 将 f(x)改写为 f(x)(4x2)x3.5)x2.6)x1.7)x0.8，由内向外依次计算一次多项式，当 x5 时的值：v04；v145222；v22253.5113.5；v3113.552.6564.9；v4564.951.72 826.2；v52 826.
9、250.814 130.2.所以当 x5 时，多项式的值等于 14 130.2.利用秦九韶算法求多项式的值的步骤跟进训练2用秦九韶算法计算多项式 f(x)1235x8x26x45x53x6在 x4 时，v3 的值为()A144B136C57D34B 根据秦九韶算法多项式可化为 f(x)(3x5)x6)x0)x8)x35)x12.由内向外计算 v03；v13(4)57；v27(4)634；v334(4)0136.进位制及其转化 探究问题1数学上通常使用什么进位制？它的原理是什么？提示 十进制 十进制的原理是满十进一一个十进制正整数 N 可以写成 an10nan110n1a1101a0100 的形
10、式，其中 an，an1，a1，a0都是 0 至 9 中的数字，且 an0.例如 36531026105.2你还知道哪些进位制？它们与目前我们使用的进位制数之间能否转化？提示(1)二进制使用 0 和 1 这两个数字，基数为 2.(2)八进制使用 0,1,2,3,4,5,6,7 这八个数字，基数为 8.(3)十六进制使用 0,1,2,3,4,5,6,7,8,9，A，B，C，D，E，F 这十六个符号，基数为 16.其中 A，B，C，D，E，F 分别相当于十进制中的10,11,12,13,14,15.它们与十进位制数之间可以转化，两个非十进制数之间也可以以十进制作“桥梁”，进行相互转化3不同的进位制数
11、如何区分？提示 一般地，k 进制数的原理是满 k 进一，k 进制数一般在右下角处标注(k)，以示区别例如 270(8)表示 270 是一个 8 进制数但十进制一般省略不写【例 3】下列四个数中，最大的是()A11011(2)B103(4)C44(5)D25思路点拨：先将各数都转化为十进制数，再比较大小A 11011(2)12412302212112027，103(4)14204134019,44(5)45145024.27252419，最大数是 11011(2)1(变条件)210(6)化成十进制数为_78 210(6)2621678.2(变结论)把 1234(5)化成七进制数为_365(7)1
12、234(5)153252351450194.而 1 234(5)194365(7)进位制的转换方法(1)要把 k 进制数化为十进制数，首先把 k 进制数表示成不同位上数字与 k 的幂的乘积之和，其次按照十进制的运算规则计算和(2)十进制数化为 k 进制数(除 k 取余法)的步骤 课 堂 小 结 提 素 养 1求两个正整数的最大公约数的问题，可以用辗转相除法，也可以用更相减损术用辗转相除法，即根据 anbr 这个式子，反复相除，直到 r0 为止；用更相减损术，即根据 r|ab|这个式子，反复相减，直到 r0 为止2秦九韶算法的关键在于把 n 次多项式转化为一次多项式，注意体会递推的实现过程，实施
13、运算时要由内向外，一步一步执行3把一个非十进制数转化为另一种非十进制数，通常是把这个数先转化为十进制数，然后再利用除 k 取余法，把十进制数转化为 k进制数而在使用除 k 取余法时要注意以下几点：(1)必须除到所得的商是 0 为止；(2)各步所得的余数必须从下到上排列；(3)切记在所求数的右下角标明基数1判断下列结论的正误(正确的打“”，错误的打“”)(1)用辗转相除法与更相减损术都可以求两个正整数的最大公约数()(2)秦九韶算法的优点是减少了乘法运算的次数，提高了运算效率()(3)不同进位制中，十进制的数比二进制的数大()答案(1)(2)(3)2用辗转相除法求 72 与 120 的最大公约数
14、时，需要做除法次数为()A4 B3C5D6B 12072148,7248124,48242.3将八进制数 123(8)化为十进制数，结果为_83 1822813806416383.4用秦九韶算法求多项式 f(x)8x75x63x42x1，当 x2时的值解 根据秦九韶算法，把多项式改写成如下形式：f(x)8x75x60 x53x40 x30 x22x1(8x5)x0)x3)x0)x0)x2)x1.而 x2，所以有 v08，v182521，v2212042，v3422387，v48720174，v517420348，v634822698，v7698211 397.所以当 x2 时，多项式的值为 1 397.点击右图进入 课 时 分 层 作 业 Thank you for watching!
