第一章算法初步§1.3

1、1.3算法案例【课时目标】通过三种算法案例：辗转相除法与更相减损术，秦九韶算法，进位制，进 一步体会算法的思想，提高算法设计水平，体会中国古代数学对世界的贡献.知识梳理1. 辗转相除法(1) 辗转相除法，又叫欧几里得算法，是一种求两个正整数的最大公约数的古老而有效 的算法.给定两个正整数m，n.计算m除以n所得的余数r.m = n，n= r.若r = 0，则m、n的最大公约数等于 m;否则，返回第二步.(2) 辗转相除法的算法步骤 第一步， 第二步， 第三步， 第四步，2约简；若不是，执2. 更相减损术 第一步，任意给定两个正整数，判断它们是否都是偶数.若是，用 行第二步.第二步，以较大的数减

2、去较小的数, 接着把所得的差与较小的数比较, 并以大数减小数， 继续这个操作，直到所得的数相等为止，则这个数 (等数)或这个数与约简的数的乘积就 是所求的最大公约数.3. 秦九韶算法把一个n次多项式f(x) = anxn + an_1xn_1 + ao改写成如下形式：(anx + an_ 1)x + an- 2)x + a1)x + ao，求多项式的值时，首先计算最内层括号内一次多项式的值,即V1= anx+ an-1,然后由内向外逐层计算一次多项式的值，即-V2= Vix+ a-2，V3= V2X+ an_3，Vn = vn-lX+ a0这样，求n次多项式f(x)的值就转化为求n个一次多项式

3、的值. 4.进位制k进一”就是k进制，k进进位制是人们为了计数和运算方便而约定的记数系统，“满 制的基数是k.把十进制转化为k进制数时，通常用除 k取余法.作业设计一、选择题1. 下列说法中正确的个数为()(1) 辗转相除法也叫欧几里得算法；(2) 辗转相除法的基本步骤是用较大的数除以较小的数；(3) 求最大公约数的方法，除辗转相除法之外，没有其他方法; 编写辗转相除法的程序时，要用到循环语句.A . 1B. 2C. 3D. 4答案 C解析 (1)、(2)、(4)正确， (3)错误2用更相减损术求 294 和 84 的最大公约数时，需做减法的次数是 ()A2 答案 解析所以用C4B3C由于 2

4、94 和 84 都是偶数，2 约简：D5294 -2= 147,84 -2= 42,又由于 147 不是偶数,所以 14742=105, 105 42= 63，63 42= 21 ，4221= 21，故需做 4 次减法，故选 C.)D331 037 和 425 的最大公约数是 A51 B17C9答案 B解析 / 1 037= 425 X 2+ 187, 425= 187X 2 51 ，187= 51 X 3 34，51=34X 117，34= 17X 2，17.f(x) = 6x6+ 5x5 + 4x4 + 3x3 + 2/+ x + 7 在 x= 0.4 时的值时,()即 1 037 和 4

5、25 的最大公约数是 4用秦九韶算法计算多项式 需做加法和乘法的次数的和为C12D8A10B9答案 C解析 f(x)= (6x5)x4)x3)x2)x1)x7加法6次，乘法6次， 6+ 6= 12(次)，故选 C.5.已知f(x)= x5 + 2x3+3x2+x+ 1,应用秦九韶算法计算 x = 3时的值时，V3的值为()A27B11C109D36答案 D解析 将函数式化成如下形式.f(x)= (x0)x2)x3)x1)x1 由内向外依次计算：v0= 1 ,vi= 1X 3 + 0 = 3,V2= 3X 3 + 2 = 11,V3= 11 X 3 + 3= 36 ,V4 = 36 X 3 +

6、1 = 109, v5= 109X 3 1 = 328.6下列有可能是 4 进制数的是 ()A. 5 123答案 C 解析 4进制数每位上的数字一定小于4，故选C.二、填空题7.辗转相除法程序中有一空请填上.B. 6 542C. 3103D. 4 312INPUT“a, b = ”； a, bDOr =a= bb = rLOOP UNTILr= 0P RINT aEND答案 a MOD b解析 MOD用来表示a除以b的余数.&更相减损术程序中有两空请填上.INPUT a, bWHILE abr = a- bIF br THENELSEa= rEND IFWENDP RINT bEND答案a=

7、b b = r9.已知三个数12(16), 25(7), 33，将它们按由小到大的顺序排列为 答案33 12(16)25(7)解析将三个数都化为十进制数.12(佝=1 X 16+ 2 = 18,25(7) = 2X 7+ 5= 19,33(4) = 3X 4+ 3= 15,- 33(4)12(16)25(7).三、解答题10 .用两种方法求210与98的最大公约数.解用辗转相除法：210= 98X 2+ 14,98= 14X 7. 210与98的最大公约数为14.用更相减损术： 210与98都是偶数，用2约简得105 和 49，105-49= 56,56 49 = 7,49- 7= 42,42

8、 7 = 35,35 7= 28,28 - 7 = 21,21 - 7= 14,14 -7 = 7. 210与98的最大公约数为 2X 7= 14.11. 用秦九韶算法计算多项式f(x) = x6 - 12x5 + 60x4- 160x3 + 240X2- 192x + 64 当 x= 2 时的值.解将f(x)改写为f(x)= (x- 12)x + 60)x- 160)x + 240)x - 192)x + 64由内向外依次计算一次多项式当x=2时的值V0= 1,V1 = 1X 2 12= 10,V2 = 10 X 2 + 60 = 40,V3 = 40 X 2 160 = 80,V4 = 8

9、0 X 2 + 240 = 80,V5= 80X 2 192= 32,V6 = 32 X 2 + 64= 0. f(2) = 0,即卩x= 2时，原多项式的值为0.【能力提升】12. 把111化为五进制数.解5| J110余数111化为五进制数为421 (5).13.把10 231 (5)化为四进制数. 解先化成十进制数.10 231(5)= 1 X 54 + 0 X 53 + 2 X 5?+ 3X 51.辗转相除法与更相减损术的区别和联系 都是求最大公约数的方法. 二者的实质都是递归的过程. 二者都要用循环结构来实现. + 1 =625+ 50+ 15+ 1=691再化为四进制数余数303224| 6914| 1724| 434| 10010 231(5)= 22 303(4).2. 秦九韶算法的特点秦九韶算法的特点在于把求一个n次多项式的值转化为求 n个一次多项式的值，即把求f(V)三anxn+ an ixn 1 + aix+ ao的值转化为求递推公式：这样可以最多计算(k=n1 次乘法和，nn次加法即可得多项式的值，和直接代入多项式相比减少 了乘法的运算次数