1、第一章 算法初步 1.3 算法案例 学习 目标 1.理解辗转相除法与更相减损术的含义，了解其执行过程. 2.理解秦九韶算法的计算过程，并了解它提高计算效率的实质. 3.理解进位制的概念，能进行不同进位制间的转化. 4.了解进位制的程序框图和程序. 知识梳理 自主学习 题型探究 重点突破 当堂检测 自查自纠 栏目 索引 知识梳理 自主学习 知识点一 辗转相除法与更相减损术 1.辗转相除法 (1)辗转相除法，又叫欧几里得算法，是一种求两个正整数的 的 古老而有效的算法. (2)辗转相除法的算法步骤 第一步，给定 . 第二步，计算 . 第三步， . 第四步，若r0，则m，n的最大公约数等于 ；否则，
2、返回 . 最大公约数 两个正整数m，n m除以n所得的余数r mn，nr m 第二步 答案 2.更相减损术 第一步，任意给定两个正整数，判断它们是否都是 .若是，用 约 简；若不是，执行 . 第二步，以 的数减去 的数，接着把所得的差与 的数比较， 并以大数减小数.继续这个操作，直到所得的数 为止，则这个数(等 数)或这个数与约简的数的乘积就是所求的最大公约数. 偶数 2 第二步 较大 较小 较小 相等 答案 3.辗转相除法和更相减损术的区别与联系： 名称 辗转相除法 更相减损术 区别 (1)以除法为主； (2)两个整数的差值较大 时，运算次数较少； (3)相除，余数为0时得 结果 (1)以减
3、法为主； (2)两个整数的差值较大时，运算次数 较多； (3)相减，减数与差相等时得结果； (4)相减前要进行是否都是偶数的判断 联系 (1)都是求两个正整数最大公约数的方法； (2)二者的实质都是递归的过程； (3)二者都要用循环结构来实现 思考 实际应用更相减损术时要做的第一步工作是什么？ 答 先判断a，b是否为偶数，若是，都除以2再进行. 答案 知识点二 秦九韶算法 1.秦九韶算法简介 (1)秦九韶算法要解决的问题是求多项式的值. (2)秦九韶算法的特点： 通过一次式的反复计算，逐步得到高次多项式的值，即将一个n次多项 式的求值问题归结为重复计算n个一次多项式的值的问题. (3)秦九韶算
4、法的原理： 将f(x)anxnan1xn1a1xa0改写为： f(x)(anxn1an1xn2a1)xa0 (anxn2an1xn3a2)xa1)xa0 先计算最内层括号内一次多项式的值，即v1anxan1，再由内向外 逐层计算一次多项式vk的值. 2.秦九韶算法的操作方法 (1)算法步骤如下： 第一步，输入多项式次数n、最高次项的系数an和x的值. 第二步，将v的值初始化为an，将i的值初始化为n1. 第三步，输入i次项的系数ai. 第四步，vvxai，ii1. 第五步，判断i是否大于或等于0.若是，则返回第三步；否则，输出多 项式的值v. (2)程序框图如图所示. (3)程序如下： INP
5、UT “n”；n INPUT “an”；a INPUT “x”；x va in1 WHILE i0 PRINT “i”；i INPUT “ai”；a vv*xa ii1 WEND PRINT v END 知识点三 进位制 1.进位制的概念 进位制是为了计数和运算方便而约定的记数系统，约定“满几进一” 就是几进制，几进制的基数(大于1的整数)就是几. 2.常见的进位制 (1)二进制： 只使用0和1两个数学； 满二进一，即1110(2). (2)八进制； 使用0,1,2,3,4,5,6,7这八个不同数学； 满八进一，即7110(8). 思考 任何进位制中都要用到的数字是什么？ 答 0和1. 返回
6、答案 题型探究 重点突破 题型一 求两个正整数的最大公约数 例1 分别用辗转相除法和更相减损术求261和319的最大公约数. 解 方法一 (辗转相除法) 3192611(余58)， 261584(余29)， 58292(余0)， 所以319与261的最大公约数为29. 方法二 (更相减损术) 31926158， 26158203， 20358145， 1455887， 875829， 582929， 29290， 所以319与261的最大公约数是29. 解析答案 反思与感悟 跟踪训练1 用辗转相除法求80与36的最大公约数，并用更相减损术检 验你的结果. 解 803628，36844,8420
7、， 即80与36的最大公约数是4. 验证： 80240,36218；40220,1829； 20911,1192；927,725； 523,321；211,1224； 所以80与36的最大公约数为4. 解析答案 题型二 秦九韶算法的应用 例2 用秦九韶算法求多项式f(x)x55x410x310x25x1当x2 时的值. 解 f(x)x55x410x310x25x1(x5)x10)x10)x5)x1. 当x2时，有v01； v1v0xa41(2)53； v2v1xa33(2)104； v3v2xa24(2)102； v4v3xa12(2)51； v5v4xa01(2)11. 故f(2)1. 解析
8、答案 反思与感悟 跟踪训练2 用秦九韶算法计算多项式f(x)x612x560x4160x3 240x2192x64当x2时的值. 解 根据秦九韶算法，把多项式改写成如下形式： f(x)(x12)x60)x160)x240)x192)x64. 由内向外依次计算一次多项式当x2时的值； v01； v1121210； v21026040； v340216080； v480224080； v580219232； v6322640. 所以当x2时，多项式的值为0. 解析答案 题型三 进位制之间的互化 例3 (1)把二进制数1110011(2)化为十进制数. 解 1110011(2)12612512402
9、30221211115. (2)将8进制数314706(8)化为十进制数. 解 314706(8)385184483782081680104902. 所以，化为十进制数是104902. 解析答案 反思与感悟 跟踪训练3 将53(8)转化为二进制数. 解 先将八进制数53(8)转化为十进制数： 53(8)58138043； 再将十进制数43转化为二进制数： 所以53(8)101011(2). 解析答案 转化与化归思想 思想方法 例4 下列各数中，最小的数是( ) A.85(9) B.210(6) C.1000(4) D.111111(2) 分析 先将它们转化为十进制数，再进行比较. 解析 85(
10、9)89577, 210(6)26216078, 1000(4)14364, 111111(2)12512412312212163. 故最小的是63. D 解析答案 解后反思 分析 数制转化方法掌握不牢致错 易错点 例5 把十字进制数49化为二进制数. 分析 对进位制间的换算，要弄清解题的办法，将十进制数转化为k进 制数用“除k取余法”. 解 所以49110 001(2). 解后反思 本例常出现的错误是把上式中各步所得的余数从上到下排 列，这是基本方法掌握不牢造成的，应加以注意. 分析 解析答案 解后反思 返回 当堂检测 1 2 3 4 5 1.1 337与382的最大公约数是( ) A.3
11、B.382 C.191 D.201 解析 利用辗转相除法，1 3373823191,3821912， 故两数的最大公约数为191. C 解析答案 1 2 3 4 5 2.把189化为三进制数，则末位数字是( ) A.0 B.1 C.2 D.3 解析 采用“除k取余法”，得 即18921 000(3) A 解析答案 1 2 3 4 5 3.用秦九韶算法求n次多项式f(x)anxnan1xn1a1xa0当xx0 时的值，求f(x0)需要乘方、乘法、加法的次数分别为( ) A. ，n，n B.n,2n，n C.0,2n，n D.0，n，n nn1 2 解析 因为f(x)(anxan1)xan2)xa
12、1)xa0， 所以乘方、乘法、加法的次数分别为0，n，n. D 解析答案 1 2 3 4 5 4.用秦九韶算法求多项式f(x)7x66x53x22，当x4时的值时，先 算的是( ) A.4416 B.7428 C.44464 D.74634 解析 因为f(x)anxnan1xn1a1xa0 (anxan1)xan2)xa1)xa0， 所以用秦九韶算法求多项式f(x)7x66x53x22当x4时的值时，先 算的是74634. D 解析答案 1 2 3 4 5 5.用更相减损术求36与134的最大公约数，第一步应为_ _. 解析 36与134都是偶数， 第一步应为：先除以2，得到18与67. 先除
13、以2，得到 18与67 解析答案 课堂小结 返回 1.求两个正整数的最大公约数的问题，可以用辗转相除法，也可以用更相 减损术.用辗转相除法，即根据anbr这个式子，反复相除，直到r0为 止；用更相减损术，即根据r|ab|这个式子，反复相减，直到r0为止. 2.秦九韶算法的关键在于把n次多项式转化为一次多项式，注意体会递推的 实现过程，实施运算时要由内向外，一步一步执行. 3.把一个非十进制数转化为另一种非十进制数，通常是把这个数先转化为 十进制数，然后再利用除k取余法，把十进制数转化为k进制数.而在使用除 k取余法时要注意以下几点：(1)必须除到所得的商是0为止；(2)各步所得的 余数必须从下到上排列；(3)切记在所求数的右下角标明基数.
