n n -1 1 0
n n -1 1
0 n n -1 2 1
0 i
i
算法案例（讲义）
? 知识点睛
典型算法举例：
1. 辗转相除法
①方法概述：两数相除，较大数除以较小数，得商和余数， 继而较小数除以余数，重复操作，直至除尽，此时除数即为最大公约数．
②原理：在 a =bq +r 中，除数 b 和余数 r 能被同一个数整除， 那么被除数 a 也能被这个数整除．或者说，除数与余数的最大公约数，就是被除数与除数的最大公约数．
2. 秦九韶算法
把一个 n 次多项式改写成如下形式：
f (x ) = a x n + a x n -1 + …+ a x + a = (a x n -1 + a x n -2 + …+ a )x + a = ((a x n -2 + a x n -3 + …+ a )x + a )x + a = …
= (…((a n x + a n -1) x + a n -2 ) x + …+ a 1) x + a 0
记v 0 = a n ， v 1 = a n x + a n -1 ，…， v n = v n -1x + a 0 ．
求多项式的值时，首先计算最内层括号内一次多项式的值， 即 v 1，然后由内向外逐层计算．
3. 进位制
①k 进制：若 k 是一个大于 1 的整数，那么以 k 为基数的 k 进制数可以表示为一串数字连写在一起的形式．
a n a n -1 …a 1a 0 (k )
（a n ，a n -1 ，…，a 1 ，a 0 ∈ N ，0 < a n < k ，0 ≤a n -1 ，…，a 1 ，a 0 < k ）
②进位制数相互转化：
k 进制转十进制，计算 k 进制数 a 的右数第 i 位数字a 与k i -1 的 乘积a ? k
i -1 ，再将其累加，重复操作求和． 十进制数转 k 进制数（除 k 取余法）：
如右图，十进制数化为二进制数，
89=1011001（2）．
1
?精讲精练
1.用“辗转相除法”求下列数的最大公约数：
（1）459 和357 的最大公约数是；
（2）三个数324，243，135 的最大公约数是．
2.用秦九韶算法求多项式的值：
（1）计算多项式 f (x) = 3x6 + 4x5 + 5x4 + 6x3 + 7x2 + 8x 在
x = 0.1 时的值时，需要做乘法和加法的次数分别是，；
（2）求多项式f (x) = 12 + 35x - 8x 2+ 79x 3+ 6x 4+ 5x 5+ 3x 6在
x=-4 的值时，v
4
的值为；
（3）计算多项式 f (x) = 8x5 + 5x4 + 3x3 + 2x2 + 6x +1 ，当x = 2
时的值为．
3.完成下列进制的转化：
10202
(3) = ?
(10)
；
101
(10) = ?
(8)
；
1231(5)= (7)．
2
． 4. 三位七进制的数表示的最大的十进制的数是（
） A ．322 B ．402 C ．342 D ．365
5. 在下列各数中，最小的数是（
） A ． 85(9)
B ． 210 (6)
C ．1000(4) D
6. 已知三个数 12(16)，25(7)，33(4)，按照从小到大的顺序排列为
．
7. 已知175( r ) =125(10) ，则 r = ．
8. 如图所示的程序框图的算法思路来源于我国古代数学名著
《九章算术》中的“更相减损术”，执行该程序框图，若输入的 a ，b 的值分别为 14，18，则输出的a 的值为（
） A ．0 B ．2 C ．4 D ．14
3
111111(2)
9.如图所示的程序框图给出了利用秦九韶算法求多项式值的一
个实例，若输入n，x的值分别为3，2，则输出v 的值为（）A．35 B．20 C．18 D．9
化为十进制数的一个程序框图，判10.下面是把二进制数11111
(2)
断框内应填入的条件是（）
A．i> 5 ？B．i ≤4 ？C．i > 4 ？D．i ≤5 ？
4
<
11.执行如图所示的程序框图后，输出的值为4，则P 的取值范
围是（）
A．7
15 8 16
C．3
7
4 8
B．P >
15
16
7 15
D．≤P
8 16
12.设a 是一个各位数字都不是0 且没有重复数字的三位数．将
组成a 的3 个数字按从小到大排成的三位数记为I(a)，按从大到小排成的三位数记为D(a)（例如a=815 ，则I(a)=158 ，D(a)=851）．阅读如图所示的程序框图，运行相应的程序，任意输入一个a ，输出的结果b = ?．
5
? ?
?2x -1 13. 已知函数 y = ?x 2 + 1 ?x 3 + 2x （x < 0） （0 ≤ x < 1），写出求该函数的函数 （x ≥1） 值的算法，并画出程序框图．
14. 设计一算法，求使12 + 22 + 32 + + n 2 > 2006 成立的最小正
整数n 的值.
6
15. 设计算法计算：S = 1+
1
2 +
1
3 +
1
4 +
1
，画出程序框图．
5 +
1
6 +
1
7
7
【参考答案】
1. （1）51；（2）27
2. （1）6；5；（2）220；（3）381
3. 101 145 362
4. C
5. D
6. 33
(4) < 12
(16)
< 25
(7)
7. 8
8. B
9. C
10.C
11.C
12. 495
13.略
14.略
15.略
8