高中数学之算法案例

算法案例（讲义）
? 知识点睛
典型算法举例：
1. 辗转相除法
①方法概述：两数相除，较大数除以较小数，得商和余数，继而较小数除以余数，重复操作 ，直
至除尽，此时除数即为最大公约数．
②原理：在a=bq+r中，除数b和余数r能被同 一个数整除，那么被除数a也能被这个数整除．或
者说，除数与余数的最大公约数，就是被除数与除数的 最大公约数．
2. 秦九韶算法
把一个n次多项式改写成如下形式：
f(x)? a
n
x
n
?a
n?1
x
n?1
?…?a< br>1
x?a
0
?(a
n
x
n?1
?a
n?1
x
n?2
?…?a
1
)x?a
0
?((a< br>n
x
n?2
?a
n?1
x
n?3
?…?a< br>2
)x?a
1
)x?a
0

?…
?(…(( a
n
x?a
n?1
)x?a
n?2
)x?…?a
1
)x?a
0
记
v
0
?a
n
，
v< br>1
?a
n
x?a
n?1
，…，
v
n
?v
n?1
x?a
0
．

求多项式的值时，首先计算最内层 括号内一次多项式的值，即v
1
，然后由内向外逐层计算
．
3. 进位制
①k进制：若k是一个大于1的整数，那么以k为基数的k进制数可以表示为一串数字连写在一
起的形式
．

a
n
a
n?1
…a
1
a
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
i
与
k
i?1
的乘积
a
i
?k
i?1
，再将其累加，重复操
作求和
．< br>
十进制数转k进制数（除k取余法）：
如右图，十进制数化为二进制数，
89=1011001
（
2
）
．




2
2
2
2
89
44
22
11< br>25
2
2
2
1
0
余数
1
0
0
1
1
0
1
? 精讲精练
1. 用“辗转相除法”求下列数的最大公约数：
（1）
459
和
357
的最大公约数是____________；



1

（2）三个数
324，243，135
的最大公约数是____________．



2. 用秦九韶算法求多项式的值：
（1）计算多项式f(x)?3x
6
?4x
5
?5x
4
?6x
3
?7x
2
?8x
在
x?0.1
时的值时，需要做乘法和加法的次数分别是_______，_______；



（2）求多项式
f(x)?12?35x?8x
2< br>?79x
3
?6x
4
?5x
5
?3x
6在x=-4的值时，
v
4
的值为_______；



（3）计算多项式
f(x)?8x
5
?5x
4
? 3x
3
?2x
2
?6x?1
，当
x?2
时的值为_ _______．
3. 完成下列进制的转化：
10202
(3)
?____
(10)
；
101
(10)
?
__________(8)
；
1231
(5)
=_____________
(7)
．


4. 三位七进制的数表示的最大的十进制的数是（ ）
A．322



5. 在下列各数中，最小的数是（ ）
A．
85
(9)




6. 已知三个 数12
(16)
，25
(7)
，33
(4)
，按照从小到大 的顺序排列为________________．

2

B．402 C．342 D．365
B．
210
(6)
C．
1000
(4)
D．
111111
(2)

7. 已知
175
(r)
=
125
(10)
，则r=________．



8. 如图所示的程序框图的算法思路来源于我国古代数学名著《九章算术》中的“更相减损术”，执< br>行该程序框图，若输入的a，b的值分别为14，18，则输出的
a
的值为（ ）
A．0 B．2 C．4 D．14
开始
输入a，b
是
是
a=a-b


9. 如图所示的程序框图给出了利用秦九韶算法求多项式值的一个实例，若输入n，x的值分别为3，
2，则 输出v的值为（ ）
A．35
开始
输入n，x
v=1
i =n-1
i=i-1
v=vx+i
i
≥
0？
否
输出 v
结束
是
a
≠
b？
否
b=b-a
否
输出a
结束

a>b？
B．20 C．18 D．9


3

10. 下面是把二进制数
11 111
(2)
化为十进制数的一个程序框图，判断框内应填入的条件是（ ）
A．
i?5
？ B．
i
≤
4
？ C．
i?4
？ D．
i
≤
5
？
开始
S=1，i=1
是
否
S=1+2S
i=i+1


11. 执行如图所示的程序框图后，输出的值为4，则P的取值范
围是（ ）
715
A．
?P
≤

816
37
C．
?P
≤

48
开始
输入P
n=1，S=0
S

是
S=S+
2
n
n=n+1
1
输出S
结束







15

16
715
D．
≤
P?

816
B．
P?
否
输出n
结束

12. 设
a
是一个各位数字都不是0且没有重复数字的三位数．将组成
a
的3个数字 按从小到大排成的
三位数记为I(a)，按从大到小排成的三位数记为D(a)（例如a=815，则I (a)=158，D(a)=851）．阅
读如图所示的程序框图，运行相应的程序，任意输入一个a
，输出的结果
b?
________．
4

开始
输入a
b=D(a)-I(a)
b=a？是
输出b
结束
否
a=b


?
2x?1 （x?0）
?
13. 已知函数
y?
?
x
2
?1 （0
≤
x?1）
，写出求该函数的函数
?
x
3
?2x （x
≥
1）
?
值的算法，并画出程序框图．


















14. 设计一算法，求使
1
2
?2
2
?3
2
???n
2
?2006
成 立的最小正整数
n
的值.




5

15. 设计算法计算：
S?1?
1
2?
3?
4?
5?
1< br>1
1
1
6?
1
7
，画出程序框图．































6

【参考答案】
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. 略

算法案例（随堂测试）
1. 372和684的最大公约数是（ ）
A．36

（ ）
A．-57 B．-22 C．34 D．74

3. 1234
（
8
）
=________
（
10
）
；300=________
（
5
）
；300=_______
（
6
）
．


111
4. 设计一个算法，输入正整数n，输出
1???…?
．
23n




7

B．186 C．12 D．589
2. 用秦九韶算法计算多项式
f(x)?3x
6?5x
5
?6x
4
?79x
3
?8x
2
?35x?12
在x=-4时的值时，v
2
的值为

【参考答案】
1. C
2. C
3. 668；2 200；1 220
4. 略

算法案例（习题）
? 巩固练习
5. 求下列数的最大公约数：
（1）1 443与999的最大公约数是_____________；


（2）319，377，116的最大公约数是___________．


6. 用秦九韶算法求n次多项式
f(x)?a
n
x
n
?a
n?1
x
n?1
?…?a
1
x?a
0
，当 x=x
0
时，
f(x
0
)
需要算乘法、加
法的次数 分别为（ ）
A．n
2
，n

B．2n，n
8
C．n，2n D．n，n

7. 已知
f(x)?x
5
?2x
3
?3x
2?x?1
，运用秦九韶算法计算x=3时的值时，v
3
的值为（ ）
A．27



B．11 C．109 D．36
8. 用秦九韶算法求多项式
f(x)?7x
7
?6x
6
?5x
5
?4x
4
?3x
3
?2x
2?x
在x=3时的值为________．



9. 把21化为二进制数，则此数为（ ）
A．10011
（
2
）
B．10110
（
2
）
C．10101
（
2
）
D．11001
（
2
）



10. 一个k进制的三位数与某六进制的二位数等值，则k不可能是（ ）
A．3 B．4 C．5


11. 下列各数中，最小的数是（ ）
D．7
A．75 B．210
（
6
）
C．111111
（
2
）
D．85
（
9
）




12. 若a= 33
（
10
）
，b=52
（
6
）
，c=1 1111
（
2
）
，则三个数的大小关系是（ ）
A．c
＞
b
＞
a B．b
＞
c
＞
a C．c
＞
a
＞
b D．a
＞
b
＞
c



13. 中国古 代有计算多项式值的秦九韶算法，如图是实现该算法的程序框图．执行该程序框图，若输
入的x=2，n =2，依次输入的a为2，2，5，则输出的s=（ ）
A．7 B．12 C．17 D．34
9

开始
输入x，n
开始< br>k=0，s=0
s=0，n=2，i=1
输入a
是
s=s·x+ai
＞
10？
k=k+1
否
输出s
k
＞
n？
否
s=s+
1
n
是
输出s
n=n?2
结束
结束
i=i?1

第9题图 第10题图
14. 如图是一个算法的程序框图，该算法所输出的结果是（
A．
1?
1
2
?
1
3
?…?
1111
10< br> B．
1?
3
?
5
?…?
19

C．
11111111
2
?
4
?
6
?…?
20
D．
2
?
2
2
?
23
?…?
2
10



15. 某程序框图如图所示，若输出的S=57，则判断框内为（
A．k
＞
4？ B．k
＞
5？ C．k
＞
6？ D．k
＞
7？
开始
开始
S=1，k=1
S=0，k=0
k=k+1
S=S+
1
S=2S+k
k
否
k=k?2
是
否
是
输出 S
输出 k
结束

结束
10

）

）

第11题图 第12题图
16. 执行如图所示的程序框图，若输入k的值为8，则判断框图可填入的条件是（ ）
515
311
A．S
≤
？
B．S
≤？
C．S
≤？
D．S
≤？

624
412


17. 设计一个算法，输入两个数，输出两个数中较大的一个．










?
x
2
?1（x??1）
?
18. 已知函数
y?
?
x?1（x?1
≤
x
≤
1）
，试画出求函数值的 程序框图．
?
（x?1）
?
3x?3










19. 对任意给定的正 整数n，写出一个求1
3
+2
3
+3
3
+…+n
3
的算法程序框图．










11

20. 设计算法求
1111
的值，要求画出程序框图．
???…?
1?22?33?499?100









【参考答案】
1. （1）111
2. D
3. D
4. 21324
5. C
6. D
7. C
8. D
9. C
10. C
11. A
12. C
13. 略
14. 略
15. 略
16. 略



2）29

（
12