高中数学人教版新课标A必修31.1.1算法的概念一课一练

 www.ks5u.com§1.3　算法案例

课时目标　通过三种算法案例：辗转相除法与更相减损术，秦九韶算法，进位制，进一步体会算法的思想，提高算法设计水平，体会中国古代数学对世界的贡献．

1．辗转相除法

(1)辗转相除法，又叫欧几里得算法，是一种求两个正整数的最大公约数的古老而有效的算法．

(2)辗转相除法的算法步骤

第一步，给定两个正整数m，n.

第二步，计算m除以n所得的余数r.

第三步，m＝n，n＝r.

第四步，若r＝0，则m、n的最大公约数等于m；否则，返回第二步．

2．更相减损术

第一步，任意给定两个正整数，判断它们是否都是偶数．若是，用2约简；若不是，执行第二步．

第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数．

3．秦九韶算法

把一个n次多项式f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0改写成如下形式：

(…((anx＋an－1)x＋an－2)x＋…＋a1)x＋a0，

求多项式的值时，首先计算最内层括号内一次多项式的值，即v1＝anx＋an－1，然后由内向外逐层计算一次多项式的值，即

v2＝v1x＋an－2，

v3＝v2x＋an－3，

…

vn＝vn－1x＋a0

这样，求n次多项式f(x)的值就转化为求n个一次多项式的值．

4．进位制

进位制是人们为了计数和运算方便而约定的记数系统，“满k进一”就是k进制，k进制的基数是k.

把十进制转化为k进制数时，通常用除k取余法．

一、选择题

1．下列说法中正确的个数为(　　)

(1)辗转相除法也叫欧几里得算法；

(2)辗转相除法的基本步骤是用较大的数除以较小的数；

(3)求最大公约数的方法，除辗转相除法之外，没有其他方法；

(4)编写辗转相除法的程序时，要用到循环语句．

A．1      B．2      C．3      D．4

答案　C

解析　(1)、(2)、(4)正确，(3)错误．

2．用更相减损术求294和84的最大公约数时，需做减法的次数是(　　)

A．2      B．3      C．4      D．5

答案　C

解析　由于294和84都是偶数，

所以用2约简：

294÷2＝147，

84÷2＝42，

又由于147不是偶数，

所以147－42＝105，

105－42＝63，

63－42＝21，

42－21＝21，

故需做4次减法，故选C.

3．1 037和425的最大公约数是(　　)

A．51     B．17      C．9      D．3

答案　B

解析　∵1 037＝425×2＋187，

425＝187×2＋51，

187＝51×3＋34，

51＝34×1＋17，

34＝17×2，

即1 037和425的最大公约数是17.

4．用秦九韶算法计算多项式f(x)＝6x6＋5x5＋4x4＋3x3＋2x2＋x＋7在x＝0.4时的值时，需做加法和乘法的次数的和为(　　)

A．10      B．9      C．12      D．8

答案　C

解析　f(x)＝(((((6x＋5)x＋4)x＋3)x＋2)x＋1)x＋7

∴加法6次，乘法6次，

∴6＋6＝12(次)，故选C.

5．已知f(x)＝x5＋2x3＋3x2＋x＋1，应用秦九韶算法计算x＝3时的值时，v3的值为(　　)

A．27      B．11      C．109      D．36

答案　D

解析　将函数式化成如下形式．

f(x)＝(((x＋0)x＋2)x＋3)x＋1)x＋1

由内向外依次计算：

v0＝1，

v1＝1×3＋0＝3，

v2＝3×3＋2＝11，

v3＝11×3＋3＝36，

v4＝36×3＋1＝109，

v5＝109×3＋1＝328.

6．下列有可能是4进制数的是(　　)

A．5 123      B．6 542      C．3 103      D．4 312

答案　C

解析　4进制数每位上的数字一定小于4，故选C.

二、填空题

7．辗转相除法程序中有一空请填上．

答案　a MOD b

解析　MOD用来表示a除以b的余数．

8．更相减损术程序中有两空请填上．

答案　a＝b　b＝r

9．已知三个数12(16)，25(7)，33(4)，将它们按由小到大的顺序排列为________．

答案　33(4)<12(16)<25(7)

解析　将三个数都化为十进制数．

12(16)＝1×16＋2＝18，

25(7)＝2×7＋5＝19，

33(4)＝3×4＋3＝15，

∴33(4)<12(16)<25(7)．

三、解答题

10．用两种方法求210与98的最大公约数．

解　用辗转相除法：

210＝98×2＋14，

98＝14×7.

∴210与98的最大公约数为14.

用更相减损术：

∵210与98都是偶数，用2约简得

105和49，

105－49＝56,56－49＝7，

49－7＝42,42－7＝35，

35－7＝28,28－7＝21，

21－7＝14,14－7＝7.

∴210与98的最大公约数为2×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＝1×2－12＝－10，

v2＝－10×2＋60＝40，

v3＝40×2－160＝－80，

v4＝－80×2＋240＝80，

v5＝80×2－192＝－32，

v6＝－32×2＋64＝0.

∴f(2)＝0，即x＝2时，原多项式的值为0.

能力提升

12．把111化为五进制数．

解　

∴111化为五进制数为421(5)．

13．把10 231(5)化为四进制数．

解　先化成十进制数．

10 231(5)＝1×54＋0×53＋2×52＋3×51＋1

＝625＋50＋15＋1

＝691

再化为四进制数

∴10 231(5)＝22 303(4).

1．辗转相除法与更相减损术的区别和联系

(1)都是求最大公约数的方法．

(2)二者的实质都是递归的过程．

(3)二者都要用循环结构来实现．

2．秦九韶算法的特点

秦九韶算法的特点在于把求一个n次多项式的值转化为求n个一次多项式的值，即把求f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0的值转化为求递推公式：

这样可以最多计算n次乘法和n次加法即可得多项式的值，和直接代入多项式相比减少了乘法的运算次数，提高了运算效率．

3．十进制与其他进制的转化

(1)将k进制转化为十进制的方法：先把k进制数写成各位上的数字与k的幂的乘积的形

式，再按十进制的运算规则计算．

(2)将十进制化成k进制的方法：用除k取余法，用k连续去除十进制数所得的商，直到商为零为止，然后将各步所得的余数倒序写出，即为相应的k进制数．