渠道管理-过云雨

高中数学常见题型解法归纳 - 四种算法案例
【知识要点】
算法案例有辗转相除法、更相减损术、秦九韶算法和进位制.
一、辗转相除法
辗转相除法求两个数的最大公约数，其算法可以描述如下：
① 输入两个正整数
m
和
n
；
② 求余数
r
：计算< br>m
除以
n
，将所得余数存放到变量
r
中；
③更新被 除数和余数：
m
=
n
，
n
=
r
；
④判断余数
r
是否为0.若余数为0，则输出结果；否则转向第②步继续循环执行
如此循环，直到得到结果为止.
例：利用辗转相除法求6105与2146的最大公约数
6105=2146×2+1813 2146=1813×1+333 1813=333×5+148
333=148×2+37 148=37×4+0 最后的除数37是6105与2146的最大公约数.
二、更相减损术
我国早期也有解决求最大公约数问题的算法，就是更相减损术.在《九章算术》中记
载了更相 减损术求最大公约数的步骤：可半者半之，不可半者，副置分母•子之数，以少减多，更相减
损，求其等 也，以等数约之.
解题步骤：以较大的数减去较小的数，接着把所得的差与较小的数比较，并 以大数减小数，继续
这个操作，直到所得的数相等为止,则这个相等的数就是所求的最大公约数.
例：用更相减损术求98与63的最大公约数
98-63=35 63-35=28 35-28=7 28-7=21 21-7=14 14-7=7
所以98和63的最大公约数是7.
三、秦九韶算法
nn1n2
秦九 韶算法适用一般的多项式
f(x)a
n
xa
n1
xa
n2
xa
1
xa
0

nn1n2的求值问题.用秦九韶算法求一般多项式
f(x)a
n
xa
n1< br>xa
n2
xa
1
xa
0
.当
xx
0
时的函
数值，可把
n
次多项式的求值问题转化成求
n
个一次多项式的值的问题，即求
v
0
a
n

v
1
=
v
0
x
+
a
n1

v
2
=
v
1
x
+
a
n2

v
3
=
v
2
x
+
a
n3< br>
……
v
n
=
v
n1
x
+
a
n

这是一个在秦九韶算法中反复执行的步骤，可以用循环结构来实现.
nn1 n2
用秦九韶算法求一般多项式
f(x)a
n
xa
n1xa
n2
xa
1
xa
0
.当
xx
0
时的函数值，需
要
n
次乘法运算，
n
次加 法运算.
四、进位制
1、概念
进位制是一种记数方式，用有限的数字在不同的位 置表示不同的数值.可使用数字符号的个数称为基
数，基数为
n
，即可称
n< br>进位制，简称
n
进制.现在最常用的是十进制，通常使用10个阿拉伯数字0—9进行记数.
对于任何一个数，我们可以用不同的进位制来表示.比如：十进数57，可以用二进制表 示为111001，
也可以用八进制表示为71、用十六进制表示为39，它们所代表的数值都是一样的 .
一般地，若
k
是一个大于1的整数，那么以
k
为基数的
k
进制可以表示为：
a
n
a
n1
...a
1< br>a
0(k)
(0a
n
k,0a
n1
,... ,a
1
,a
0
k)
，
而表示各种进位制数一般在数字右 下脚加注来表示,如111001
(2)
表示二进制数,34
(5)
表示5进 制数.
2、进位制间的转换
（1）非十进制数转换为十进制数比较简单，只要计算下面的式子值即可：
a
na
n1
.....a
1
a
0
(k)a
n< br>k
n
a
n1
k
n1
......... a
1
ka
0

（2）把十进制数转换为
k
进制数，一般利用 “除
k
取余法”.
例：把89化为二进制数.
2|89余数
2|44
2|22
2|1 1
2|5
2|2
2|1
2|0
1
0
0
1
1
0
1

所以
89=1011001

（2）
注意：利用除
k
取余法解答时，最后的余数是从下往上写，不要从上往 下写.
（3）非十进制之间的转换，先把它转换成十进制，再把十进制转换成其他进制.

【方法讲评】
算法案例一 辗转相除法
1、 输入两个正整数m
和
n
；2、求余数
r
：计算
m
除以
n
，将所得余数存放到变量
r
中；3、更新被除数和余数：
m
=n
，
n
=
r
；4、判断余数
r
是否为0.若余 数为0，则输
解题步骤
出结果；否则转向第②步继续循环执行
如此循环，直到得到结果为止.
【例1】数
4557,1953,5115
的最大公约数是（ ）
A．
31
B．
93
C．
217
D．
651


【点评】求 三个数的最大公约数，可以先求其中两个数的最大公约数，再求另外两个数的最大公约数，
再求这两个最 大公约数的最大公约数.
【反馈检测1】三个数390, 455, 546的最大公约数是 （ ）
A.65 B.91 C.26 D.13


算法案例二
解题步骤
这个操作，直到所得的数相等为止,则这个相等的数就是所求的最大公约数.
【例2】根据我国古代数学名著《九章算术》中的“更相减损术”．求得144，28的最大公约数为 （ ）
A．4 B．2 C．0 D．14
【解析】
14428116,1162888,882860,60 2832,32284,

28424,24420,

更相减损术
以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继 续
20416,16412,1248,844
，所以最大公约数是4.
【点评】本题就是利用更相减损术求的最大公约数，也可以利用辗转相除法求解.
【反馈检测2】
459
和
357
的最大公约数是（ ）
A．3 B．9 C．17 D．51

算法案例三 秦九韶算法

把
n
次多项 式的求值问题转化成求
n
个一次多项式的值的问题，即求
解题步骤
v
0
a
n

v
1
=
v
0
x
+
a
n1

v
2
=
v
1
x
+
a
n2

v
3
=
v
2
x
+
a
n3

…… v
n
=
v
n1
x
+
a
n


【例3】已知
f(x)x2x3xx1
，应用秦九韶算法计算当
x3
时
v
3
的值为
_________
.
532

nn1
【点评】
f(x)a
n
xa
n1
xa
2
x
2
a
1
xa0
利用秦九韶算法要经过
n
次乘法和
n
次加法.在利
用 秦九韶算法计算时，必须把缺的项补充起来，缺的指数幂的项的系数为零即可，并按照降幂排列.
【 反馈检测3】用秦九韶算法计算多项式
f(x)12x3x2x
当
x1< br>时的值时，
v
2
的结果为
34
______
.
A．
4
B．
1
C．
5
D．
6

算法案例四 进位制
1、非十进制数转换为十进制数比较简单，只要计算下面的式子值即可：
解题步骤
a
n
a
n1
.....a
1
a
0
(k) a
n
k
n
a
n1
k
n1
.. .......a
1
ka
0
；
2、把十进制数转换为
k
进制数，一般利用 “除
k
取余法”.
3、非十进制之间的转换，先把它转换成十进制，再把十进制转换成其他进制.
【例4】将二进制数
11100
(2)
转化为四进制数，正确的是（ ）
A．
120
(4)

B．
130
(4)

C．
200
(4)

D．
202
(4)


【点评】非十进制之间的转换，先把它转换成十进制，再把十进制转换成其他进制.
【反馈检 测4】若六进制数
10k5
(6)
（
k
为正整数）化为十进制数为< br>239
,则
k
.





参考答案

【反馈检测1答案】13

【反馈检测2答案】51
【反馈检测2详细解析】由更相减损术知

459357102;357102 255;255102153;15310251;1025151
，所以最大公约数为
51
．
【反馈检测3答案】
C

【反馈检测3详细解析】< br>f(x)12x3x2x2x3x0x2x1

34432
(((2x3)x0)x2)x1

x1
时，
v
1
2x35
；
v
2
v
1
x05(1)+0=5
.故选
C
.
【反馈检测4答案】
3

【反馈检测4详细解 析】由题
10k5
(6)
1606k656239
，
2216k239,k3





3210