1、第一章 算法初步13 算法案例内 容 标 准学 科 素 养1.会用辗转相除法与更相减损术求两个数的最大公约数.2.会用秦九韶算法求多项式的值.3.会在不同进位制间进行相互转化.提升数学运算发展逻辑推理培养数据分析01 课前 自主预习02 课堂 合作探究03 课后 讨论探究04 课时 跟踪训练基础认识知识点一 辗转相除法与更相减损术预习教材 P3437，思考并完成以下问题韩信是秦末汉初的著名军事家据说有一次汉高祖刘邦在卫士的簇拥下来到练兵场，刘邦问韩信有什么方法，不要逐个报数，就能知道场上的士兵的人数韩信先令士兵排成 3 列纵队，结果有 2 个人多余；接着立即下令将队形改为 5 列纵队，这一改，
2、又多出 3 人；随后他又下令改为 7 列纵队，这次又剩下 2 人无法成整行在场的人都哈哈大笑，以为韩信不能清点出准确的人数，不料笑声刚落，韩信高声报告共有士兵 2 333 人众人听了一愣，不知道韩信用什么方法这么快就能得出正确的结果的(1)如何求 18 与 54 的最大公约数？提示：短除法(2)要求 6 750 与 3 492 的最大公约数，上述法还好用吗？提示：数值太大，短除法不方便用知识梳理 1.辗转相除法(1)辗转相除法，又叫欧几里得算法，是一种求两个正整数的_的古老而有效的算法(2)辗转相除法的算法步骤：第一步，给定_第二步，计算_第三步，_第四步，若 r0，则 m，n 的最大公约数等
3、于_；否则返回_最大公约数两个正整数m，nm除以n所得的余数rmn，nrm第二步2更相减损术(1)更相减损术是我国古代数学专著九章算术中介绍的一种求_的算法(2)其基本过程是：第一步，任意给定两个正整数，判断它们是否都是_若是，_；若不是，执行_第二步，以_的数减去_的数，接着把所得的差与_的数比较，并以大数减小数，继续这个操作，直到所得的数_为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数两个正整数的最大公约数偶数用2约简第二步较大较小较小相等知识点二 秦九韶算法预习教材 P3739，思考并完成以下问题已知多项式 f(x)x53x43x34x2x1.(1)求 f(1)提示：
4、f(1)1334113.(2)若求 f(39)，再代入运算出现什么情况？提示：运算量太大，不易运算知识梳理 秦九韶算法的算法原理把一个 n 次多项式 f(x)anxnan1xn1a1xa0 改写成如下形式：f(x)anxnan1xn1a1xa0(anxn1an1xn2a1)xa0(anxn2an1xn3a2)xa1)xa0(anxan1)xan2)xa1)xa0.求多项式的值时，首先计算最内层括号内一次多项式的值，即 v1anxan1，然后由内向外逐层计算一次多项式的值，即v2v1xan2，v3v2xan3，vnvn1xa0.这样，求 n 次多项式 f(x)的值就转化为求 n 个一次多项式的值
5、知识点三 进位制预习教材 P4045，思考并完成以下问题(1)今天是星期二，那么 20 天后是星期几？提示：20 天后是星期一(2)每周七天，逢七便又是一循环，这与我们所学过的十进制，逢十进一是否有相似之处？提示：其实一周七天，与十进制一样，相当于逢七进一，是七进制法知识梳理 1.进位制(1)概念：进位制是为了_而约定的记数系统，“满几进一”就是几进制(2)基数：几进制的基数就是_2不同进位制之间的互化(1)k 进制化为十进制的方法：anan1a1a0(k)_(an，an1，a1，a0N，0ank，0an1，a1，a0k)(2)十进制化为 k 进制的方法_计数和运算方便几anknan1kn1a
6、1ka0除k取余数自我检测1设计程序框图，用秦九韶算法求多项式的值，所选用的结构是()A顺序结构 B条件结构C循环结构D以上都有解析：根据秦九韶算法的含义知选 D.答案：D2以下各数有可能是五进制数的是()A15 B106C731 D21 340解析：五进制数中各个数字均是小于 5 的自然数，故选 D.答案：D3228 与 1 995 的最大公约数是_解析：1 9952288171，228171157，171573，57 是 228 与 1 995 的最大公约数答案：57探究一 求两个正整数的最大公约数阅读教材 P36 例 1用更相减损术求 98 与 63 的最大公约数方法步骤：第一步，任意给
7、定两个正整数 m，n(mn)第二步，计算 mn 所得的差 k.第三步，比较 n 与 k 的大小，其中大者用 m 表示，小者用 n 表示第四步，若 mn，则 m，n 的最大公约数等于 m；否则，返回第二步例 1 分别用辗转相除法和更相减损术求 261 和 319 的最大公约数解析 法一：(辗转相除法)3192611(余 58)，261584(余 29)，58292(余 0)，所以 319 与 261 的最大公约数为 29.法二：(更相减损术)31926158，26158203，20358145，1455887，875829，582929，29290，所以 319 与 261 的最大公约数是 29
8、.方法技巧 1.利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数2利用更相减损术求两个正整数的最大公约数的一般步骤是：首先判断两个正整数是否都是偶数若是，用 2 约简也可以不除以 2，直接求最大公约数，这样不影响最后结果跟踪探究 1.用辗转相除法求 80 与 36 的最大公约数，并用更相减损术检验你的结果解析：803628，36844，8420，即 80 与 36 的最大公约数是 4.验证：80240，36218.40220，1829
9、.20911，1192.927，725.523，321.211，1224.所以 80 与 36 的最大公约数为 4.探究二 秦九韶算法阅读教材 P38 例 2已知一个 5 次多项式为 f(x)4x52x43.5x32.6x21.7x0.8，用秦九韶算法求这个多项式当 x5 时的值方法步骤：第一步，改写多项式；第二步，由内到外依次计算；第三步，结论例 2 用秦九韶算法求多项式 f(x)7x76x65x54x43x32x2x 当 x3 时的值解析 f(x)(7x6)x5)x4)x3)x2)x1)x所以有v07，v173627，v2273586，v38634262，v426233789，v57893
10、22 369，v62 369317 108，v77 108321 324.故当 x3 时，多项式 f(x)7x76x65x54x43x32x2x 的值为 21 324.方法技巧 秦九韶算法原理及注意事项(1)秦九韶算法的原理是v0an，vkvk1xank，(k1，2，n)(2)在运用秦九韶算法进行计算时，应注意每一步的运算结果，像这种一环扣一环的运算，如果错一步，那么下一步，一直到最后一步就会全部算错，同学们在计算这种题时应格外小心跟踪探究 2.用秦九韶算法计算多项式 f(x)1235x8x26x45x53x6 在 x4 时的值时，v3 的值为()A144 B136C57 D34解析：根据秦九
11、韶算法多项式可化为 f(x)(3x5)x6)x0)x8)x35)x12.由内向外计算 v03；v13(4)57；v27(4)634；v334(4)0136.答案：B3用秦九韶算法计算 f(x)6x54x4x32x29x，需要加法(或减法)与乘法运算的次数分别为()A5，4 B5，5C4，4 D4，5解析：n 次多项式需进行 n 次乘法；若各项均不为零，则需进行 n 次加法，缺一项就减少一次加法运算f(x)中无常数项，故加法次数要减少一次，为 514.故选 D.答案：D探究三 进位制阅读教材 P41 例 3把二进制数 110 011(2)化为十进制数方法步骤：第一步，写成不同位上数字与 2 的幂
12、的乘积之和；第二步，按照十进制数的运算规则进行计算例 3 把“五进制”数 1 234(5)转化为“十进制”数，再把它转化为“八进制”数解析 1 234(5)153252351450194，而1 234(5)194302(8)方法技巧 1.把 k 进制数化为十进制数的方法是：先把这个 k 进制数写成用各位上的数字与 k 的幂的乘积之和的形式，再按照十进制数的运算法则计算出结果2将十进制数化为 k 进制数的方法是除 k 取余法，即用 k 连续地去除十进制数所得的商，直到商为 0 为止，然后将余数倒排写出，即得到所求的 k 进制数3把一个非十进制数转化为另一个非十进制数，通常是把这个数先转化为十进制
13、数，然后再利用除 k 取余法，再把这个数转化为另一个非十进制数延伸探究 1.将例题改为：把 210(6)化成十进制数为_85 化成七进制数为_解析：210(6)2621678，所以 85151(7)答案：78 151(7)2将例题改为：把 1234(5)化成七进制数为_解析：1234(5)153252351450194.而1 234(5)194365(7)答案：365(7)课后小结1求两个正整数的最大公约数的问题，可以用辗转相除法，也可以用更相减损术用辗转相除法，即根据 anbr 这个式子，反复相除，直到 r0 为止；用更相减损术，即根据 r|ab|这个式子，反复相减，直到 r0 为止2秦九韶
14、算法的关键在于把 n 次多项式转化为一次多项式，注意体会递推的实现过程，实施运算时要由内向外，一步一步执行3把一个非十进制转化为另一种非十进制数，通常是把这个数先转化为十进制数，然后再利用除 k 取余法，把十进制数转化为 k 进制数而在使用除 k 取余法时要注意以下几点：(1)必须除到所得的商是 0 为止；(2)各步所得的余数必须从下到上排列；(3)切记在所求数的右下角标明基数素养培优对秦九韶算法中的运算次数理解错误已知 f(x)x52x43x34x25x6，用秦九韶算法求这个多项式当 x2 时的值时，做了几次乘法？几次加法？易错分析 在 v1 中虽然“v1224”，而计算机还是做了 1 次乘法“v12124”因为用秦九韶算法计算多项式 f(x)anxnan1xn1a1xa0 当 xx0 时的值时，首先将多项式改写成 f(x)(anxan1)xa1)xa0，然后再计算 v1anxan1，v2v1xan2，v3v2xan3，vnvn1xa0.无论 an 是不是 1，这次的乘法都是要进行的自我纠正 由以上分析，共做了 5 次乘法，5 次加法课时 跟踪训练