2017_2018学年高中数学第一章算法初步1.3算法案例学案含解析新人教a版必修3

1、- 1 -1.3 算法案例辗转相除法与更相减损术提出问题问题 1：如何求 18 与 54 的最大公约数？提示：短除法问题 2：要求 6 750 与 3 492 的最大公约数，上述法还好用吗？提示：数值太大，短除法不方便用问题 3：还有没有其他方法，可用来解决“问题 2”中的问题？提示：有导入新知1辗转相除法(1)辗转相除法，又叫欧几里得算法，是一种求两个正整数的最大公约数的古老而有效的算法(2)辗转相除法的算法步骤：第一步，给定两个正整数 m， n.第二步，计算 m 除以 n 所得的余数 r.第三步， m n， n r.第四步，若 r0，则 m， n 的最大公约数等于 m；否则返回第二步2更相减损术(1)更相减损术是我国古代数学专著九章算术中介绍的一种求两个正整数的最大公约数的算法(2)其基本过程是：第一步，任意给定两个正整数，判断它们是否都是偶数若是，用 2 约简；若不是，执行第二步第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数化解疑难辗转相除法与更相减损术

2、的比较- 2 -两种方法 辗转相除法 更相减损术计算法则 除法 减法终止条件 余数为 0 减数与差相等最大公约数的选取最后一步中的除数 最后一步中的减数计算次数 步骤较少，运算复杂 步骤较多，运算简单相同点 同为求两个正整数最大公约数的方法，都是递归过程秦九韶算法提出问题已知多项式 f(x) x53 x43 x34 x2 x1.问题 1：求 f(1)提示： f(1)1334113.问题 2：若求 f(39)，再代入运算出现什么情况？提示：运算量太大，不易运算问题 3：当 x 的值较大时，有没有更好的方法求函数值呢？提示：有可将 f(x)转化为求一次多项式的值导入新知秦九韶算法的算法原理把一个 n 次多项式 f(x) anxn an1 xn1 a1x a0改写成如下形式：f(x) anxn an1 xn1 a1x a0( anxn1 an1 xn2 a1)x a0( anxn2 an1 xn3 a2)x a1)x a0( anx an1 )x an2 )x a1)x a0.求多项式的值时，首先计算最内层括号内一次多项式的值，即 v1 anx an1 ，然后由内向外逐层计算一次多项式的值，

3、即v2 v1x an2 ，v3 v2x an3 ，vn vn1 x a0.这样，求 n 次多项式 f(x)的值就转化为求 n 个一次多项式的值化解疑难秦九韶算法的步骤- 3 -进位制提出问题问题 1：今天是星期二，那么 20 天后是星期几？提示：20 天后是星期一问题 2：每周七天，逢七便又是一循环，这与我们所学过的十进制，逢十进一是否有相似之处？提示：其实一周七天，与十进制一样，相当于逢七进一，是七进制论法导入新知1进位制(1)概念：进位制是为了计数和运算方便而约定的记数系统， “满几进一”就是几进制(2)基数：几进制的基数就是几2不同进位制之间的互化(1)k 进制化为十进制的方法：anan1 a1a0(k) ankn an1 kn1 a1k a0(an， an1 ， a1， a0N，0 an k,0 an1 ， a1， a0 k)(2)十进制化为 k 进制的方法除 k 取余数化解疑难常见的进位制(1)二进制：只使用 0 和 1 两个数字；满二进一，如 1110.(2)八进制：使用 0,1,2,3,4,5,6,7 八个不同的数字；满八进一，如 7110.(3)十六进制：使用 0,1,

4、2,3,4,5,6,7,8,9， A， B， C， D， E， F 这十六个不同的数码，其中 A， B， C， D， E， F 分别代表十进制中的 10,11,12,13,14,15；满十六进一，如F12 E10.- 4 -求最大公约数例 1分别用辗转相除法和更相减损术求 779 与 209 的最大公约数解(1)辗转相除法：7792093152，209152157，15257238，5738119，38192.所以，779 与 209 的最大公约数为 19.(2)更相减损术：779209570，1525795，570209361, 955738，361209152, 573819，20915257, 381919.所以 779 和 209 的最大公约数为 19.类题通法1用辗转相除法求最大公约数的步骤2用更相减损术求最大公约数的步骤第一步，给定两个正整数 m， n(m n 且 m， n 不全是偶数)第二步，计算 m n 所得的差 k.第三步，比较 n 与 k 的大小，其中大者用 m 表示，小者用 n 表示第四步，若 m n，则 m， n 的最大公约数等于 m；否则，返回第二步活学活用用

5、辗转相除法和更相减损术求 1 515 与 600 的最大公约数，需要运算的次数分别为()- 5 -A4,15 B5,14C5,13 D4,12解析：选 B辗转相除法：15156002315；6003151285,315285130,28530915,30152，故最大公约数为 15，且需计算 5 次用更相减损术法：1515600915，915600315,600315285，31528530,28530255,25530225,22530195,19530165,16530135,13530105,1053075,753045,453015,301515，故最大公约数为 15，且需计算 14 次.秦九韶算法及其应用例 2用秦九韶算法求多项式 f(x)6 x65 x54 x43 x32 x2 x 当 x2 时的值解 f(x)(6 x5) x4) x3) x2) x1) x，当 x2 时，有v06，v162517，v2172438，v3382379，v47922160，v516021321，v63212642，故当 x2 时，多项式 f(x)6 x65 x54 x43 x32 x2 x 的

6、值为 642.类题通法秦九韶算法原理及注意事项(1)秦九韶算法的原理是Error!(k1,2， n)(2)在运用秦九韶算法进行计算时，应注意每一步的运算结果，像这种一环扣一环的运算，如果错一步，那么下一步，一直到最后一步就会全部算错，同学们在计算这种题时应格外小心活学活用用秦九韶算法计算多项式 f(x)3 x64 x55 x46 x37 x28 x1.当 x0.4 时的值时，需要做乘法和加法的次数分别是()A6,6 B5,6C5,5 D6,5解析：选 A f(x)(3 x4) x5) x6) x7) x8) x1，所以需要进行 6 次乘法和6 次加法- 6 -进位制例 3(1)将 101 111 011(2)转化为十进制数；(2)将 235(7)转化为十进制数；(3)将 137(10)转化为六进制数；(4)将 53(8)转化为二进制数解(1)101 111 011(2)12 802 712 612 512 412 302 212 112 0379 (10)(2)235(7)27 237 157 0124 (10)(3)13736 2465，137 (10)345 (6)(4)53(8)

7、58 138 043 (10)53 (8)101 011 (2)类题通法1 k 进制数化为十进制数的步骤(1)把 k 进制数写成不同数位上的数字与 k 的幂的乘积之和的形式(2)按十进制数的运算规则运算出结果2十进制数化为 k 进制数(除 k 取余法)的步骤活学活用若六进制数 13m502(6)化为十进制数等于 12 710，求数字 m 的值解：因为 13m502(6)- 7 -16 536 4 m6356 206 126 0216 m11 846，令 216m11 84612 710，所以 m4.2.利 用 秦 九 韶 算 法 求 值 的 易 错 点典例利用秦九韶算法求 f(x) x5 x3 x2 x1 当 x3 时的值()A121 B283C321 D239解析原多项式可化为：f(x)( x0) x1) x1) x1) x1.当 x3 时，v01， v11303， v233110，v3103131， v4313194，v59431283.所以，当 x3 时 f(3)283.答案B易错防范当多项式中间出现空项时，用秦九韶算法求函数值要补上系数为 0 的相应项，否则，本题极易出现如下所

8、示的错误算法，从而误选 A. f(x)( x1) x1) x1) x1，当 x3 时，v01， v1314，v243113，v3133140，v440311201121，所以当 x3 时， f(3)121.成功破障用秦九韶算法求多项式 f(x) x50.11 x30.15 x0.04 当 x0.3 时的值解：根据秦九韶算法，将 f(x)写为：- 8 -f(x)( x0) x0.11) x0) x0.15) x0.04.按照从内到外的顺序，依次计算一次多项式当 x0.3 时的值：v01；v1 v00.300.3；v2 v10.30.110.2；v3 v20.300.06；v4 v30.30.150.132；v5 v40.30.040.079 6.所以，当 x0.3 时，多项式的值为0.079 6.随堂即时演练1在对 16 和 12 求最大公约数时，整个操作如下：16124,1248,844.由此可以看出 12 和 16 的最大公约数是()A4 B12C16 D8解析：选 A根据更相减损术的方法判断2用秦九韶算法求多项式 f(x)12 x x23 x32 x4在 x1 时的值， v2的结果是()A4 B1C5 D6解析：选 D n4， a42， a33， a21， a12， a01，由秦九韶算法的递推关系式得 v02， v1 v0x a35， v2 v1x a26.3将 51 化为二进制数得_解析：答案：110 011 (2)4用辗转相除法求 294 和 84 的最大公约数时，需要做除法的次数是_解析：29484342，84422.答案：25将 1 234(5)转化为八进制数解：将 1 234(5)转化为十进制数：- 9 -1 234(5)15 325 235 145 0194.再将十进制数 194 转化为八进制数：所以 1 234(5

《2017_2018学年高中数学第一章算法初步1.3算法案例学案含解析新人教a版必修3》由会员小**分享，可在线阅读，更多相关《2017_2018学年高中数学第一章算法初步1.3算法案例学案含解析新人教a版必修3》请在金锄头文库上搜索。