人教版高中数学必修三知识讲解，巩固练习（教学资料，补习资料）：专题1.3 算法案例

知识
1．求两个正整数的最大公约数的算法
（1）辗转相除法
①定义：辗转相除法是用于求_____________的最大公约数的一种算法，这种算法是由欧几里得在公元前300年左右首先提出的，因而又叫欧几里得算法．就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成一对新数，继续上面的除法，直到余数为零，则这时较小的数就是原来两个数的最大公约数．
②算法步骤
用辗转相除法求两个正整数的最大公约数，其算法步骤如下：
第一步，给定两个正整数．
第二步，计算除以所得的余数．
第三步，．
第四步，若，则的最大公约数等于；否则，返回第二步．
③程序框图如图所示：
④程序如下：
INPUT m，n
DO
r=m MOD n
m=n
n=r
?LOOP UNTIL r=0
PRINT m
END
或
INPUT m，n
r=1
While r>0
r=m MOD n
m=n
n=r
? WEND
PRINT m
END
（2）更相减损术
①定义：中国古代的数学专著《九章算术》中记载着“更相减损术”，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也．以等数约之．”
②算法步骤
第一步，任意给定两个正整数，判断它们是否都是偶数．若是，用2约简；若不是，执行第二步．
第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数．继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数．
③程序框图
④程序如下：
INPUT “a，b=”;a，b
WHILE a≠b
r=a-b
IF b>r THEN
a=b
b=r
ELSE
a=r
END IF
WEND
PRINT b
END
2．秦九韶算法
（1）定义及原理：把一个n次多项式改写成如下形式：．求多项式的值时，首先计算最内层括号内一次多项式的值，即，然后由内向外逐层计算一次多项式的值，即，…，，这种求n次多项式的值的方法叫做秦九韶算法．
（2）秦九韶算法程序化的可行性探讨：观察秦九韶算法中的n个一次式，可见计算时要用到的值，若令，我们可以得到下面的递推公式：．这是一个在秦九韶算法中反复执行的步骤，可以用循环结构来实现．
（3）算法步骤
第一步，输入多项式次数n、最高次项的系数和x的值．
第二步，将v的值初始化为，将i的值初始化为n－1．
第三步，输入i次项的系数．
第四步，．
第五步，判断i是否大于或等于0．若是，则返回第三步；否则，输出多项式的值v．
（4）程序框图如图所示：
（5）程序如下：
INPUT “n=”；n
INPUT “an=”；a
INPUT “x=”；x
v=a
i=n-1
WHILE i>=0
PRINT “i=”；i
INPUT “ai=”；a
v=v*x+a
i=i-1
WEND
PRINT v
END
3．进位制
（1）定义：进位制是人们为了计数和运算方便而约定的记数系统，约定满二进一，就是二进制；满十进一，就是十进制；满六十进一，就是六十进制；等等．也就是说，“满几进一”就是几进制，几进制的基数就是几．
一般地，若k是一个大于1的整数，那么以k为基数的k进制数可以表示为一串数字连写在一起的形式：．
说明：①若一个数为十进制数，其基数可以省略不写．
②若是其他进位制的数，在没有特别说明的前提下，其基数必须写出，常在数的右下角标明基数．
（2）将进制数转化为十进制数
①算法步骤：
计算进制数的右数第位数字与的乘积，再将其累加，这是一个重复操作的步骤．所以，可以用循环结构来构造算法，算法步骤如下：
第一步，输入和的值．
第二步，将的值初始化为0，的值初始化为1．
第三步，．
第四步，判断是否成立．若是，则执行第五步；否则，返回第三步．
第五步，输出的值．
②程序框图如图所示：
③程序如下：
INPUT “a，k，n=”；a，k，n
b=0
i=1
t=a MOD 10
DO
b=b+t*k^(i-1)
a=a10
t=a MOD 10
i=i+1
LOOP UNTIL i>n
PRINT b
END
（3）将十进制数转化为进制数
①转化方法：
十进制数化为进制数用____________，即先把十进制数a除以，商为，余数为，再把除以，商为，余数为，…，反复进行这种除法，直到商除以所得的商为0，余数是，即为止，此时将所有余数按从右到左排列就得到所要求的进制数．
②算法步骤：
第一步，给定十进制正整数a和转化后的数的基数．
第二步，求出a除以所得的商，余数．
第三步，把得到的余数依次从右到左排列．
第四步，若，则，返回第二步；否则，输出全部余数排列得到的进制数．
③程序框图如图所示：
④程序如下：
INPUT “a，k=”；a，k
b=0
i=0
DO
q=ak
r=a MOD k
b=b+r*10^i
i=i+1
a=q
LOOP UNTIL q=0
PRINT b
END
知识参考答案：
1．（1）两个正整数 2．（2） 3．（3）①除取余法
重点
重点
辗转相除法、更相减损术、秦九韶算法、进位制
难点
用秦九韶算法求多项式的值，进位制间的转换
易错
易对秦九韶算法中的运算次数理解错误
1．辗转相除法与更相减损术
辗转相除法与更相减损术有着相同的算法依据，但要注意运算过程的差别．
两者的区别是：
（1）辗转相除法进行的是除法运算，即辗转相除，更相减损术进行的是减法运算，即辗转相减，但其实质都是一个不断的递推过程．
（2）辗转相除法，下一次进行相除时，由上一次的除数和余数直接相除即可．而更相减损术下一次相减前必须有一个判断大小的过程，以区别谁做被减数．
注意：用更相减损术求两正整数的最大公约数时，若两数为偶数，可先约去2，这时莫忘记求得的相等两数乘以约简的数才是所求的最大公约数．
【例1】用辗转相除法和更相减损术求840与1764的最大公约数．
【答案】840与1764的最大公约数是84．
【解析】辗转相除法：
1764=840×2+84，
840=84×10+0，
∴840与1764的最大公约数是84．
更相减损术：
1764–840=924，
924–840=84，
840–84=756，
756–84=672，
672–84=588，
588–84=504，
504–84=420，
420–84=336，
336–84=252，
252–84=168，
168–84=84，
∴840与1764的最大公约数是84．
【例2】利用辗转相除法求3869与6497的最大公约数．
【答案】3869与6497的最大公约数为73．
【名师点睛】辗转相除法计算次数少，而更相减损术计算次数多，但是更相减损术每一步的计算都是减法，比做除法运算要简单一些，所以一般当数较小时考虑用更相减损术，当数较大时考虑用辗转相除法．
2．秦九韶算法
秦九韶算法的实质是：求多项式的值时，转化为求n个一次多项式的值，共进行n次乘法运算和n次加法运算．这种算法的运算次数较少，是多项式求值比较先进的算法．
【例3】 用秦九韶算法计算多项式f（x）=12+35x–8x2+79x3+6x4+5x5+3x6在x=–4时的值时，V3的值为
A．–845 B．220
C．–57 D．34
【答案】C
【解析】∵多项式f（x）=12+35x–8x2+79x3+6x4+5x5+3x6=（（（（（3x+5）x+6）x+79）x–8）x+35）x+12，
当x=–4时，∴v0=3，v1=3×（–4）+5=–7，v2=–7×（–4）+6=34，v3=34×（–4）+79=–57．故选C．
【例4】用秦九韶算法计算函数f（x）=2x4+3x3+5x–4在x=2时的函数值．
【答案】62
【名师点睛】利用秦九韶算法计算多项式的值的策略：
（1）正确地将多项式改写，若在多项式中有几项不存在，可将这些项的系数看成0，即把这些项看做．
（2）由内向外逐次计算．
（3）每一步计算结果准确，由于下一次计算用到上一次计算的结果，应认真、细致地计算每一步．
3．进位制
把一个非十进制数转化为另一种非十进制数，通常是把这个数先转化为十进制数，然后再利用除k取余法，把十进制数转化为k进制数．
【例5】将八进制数127（8）化为十进制数．
【答案】87
【解析】．
【例6】已知一个k进制的数123（k）与十进制的数38相等，求k的值．
【答案】5
【解析】将转化为十进制，，
由题意，得k2+2k+3=38，
所以k2+2k–35=0，
所以k=5或k=–7（舍）
所以k=5．
【名师点睛】除k取余法的两个关注点：①要连续除：用k连续去除十进制数或所得的商，直到商为零为止．
②若是其他进位制的数，在没有特别说明的前提下，其基数必须写出，常在数的右下角标明基数．
基础训练
1．秦九韶算法的先进性主要体现在减少运算次数，下列说法正确的是
A．可以减少加法运算次数
B．可以减少乘法运算次数
C．同时减少加法和乘法的运算次数
D．加法次数和乘法次数都有可能减少
2．用秦九韶算法求多项式，当时的值，先算的是
A．4×4=16 B．7×4=28
C．4×4×4=64 D．7×4+6=34
3．把十进制的23化成二进制数是
A．00 110（2） B．10 111（2）
C．10 1111（2） D．11 101（2）
4．若十进制数26等于k进制数32，则k等于
A．4 B．5 C．6 D．8
5．用更相减损术求294和84的最大公约数时，需要做减法的次数是
A．3 B．4 C．5 D．6
6．1 037和425的最大公约数是
A．51 B．17 C．9 D．3
7．已知多项式，用秦九韶算法求等于
A． B． C． D．
8．用更相减损术求156与91的最大公约数时，需要做减法的次数是__________．
9．将45（6）改写成十进制数为__________．
10．用秦九韶算法计算多项式当时的值时，乘法运算的次数为__________．
11．用更相减损术求288与153的最大公约数．
12．用秦九韶算法求多项式当时的值．
能力提升
13．在下列四个数中，最小的数是
A． B． C． D．
14．用秦九韶算法计算多项式当时的值时，的值为
A． B． C． D．
15．若98与63的最大公约数为，二进制数化为十进制数为，则
A．53 B．54 C．58 D．60
16．用更相减损术求123和48的最大公约数是
A．3 B．7 C．9 D．12
17．计算机是将信息转换成二进制处理，二进制即“逢二进一”，如表示二进制数．将它转化成十进制形式是，那么将二进制数（2）转换成十进制形式是
A．217-2 B．216-2 C．216-1 D．215-1
18．在下列各数中，最大的数是
A． B． C． D．
19．完成进位制之间的转化：__________．
20．（1）把八进制数化为十进制数；
（2）把1285化为16进制数．
21．先将412（5）化成十进制的数，然后用“除k取余法”再化成七进制的数．
22．用辗转相除法和更相减损术求261与319的最大公约数．
参考答案
1
2
3
4
5
6
7
13
14
15
16
17
18
B
D
B
D
B
B
A
D
B
C
A
C
B
1．【答案】B
【解析】通过对秦九韶算法的理解，可知它的主要作用是减少乘法的次数，将原来的乘法次数由减少到n，而对加法没有影响．故选B．
2．【答案】D
3．【答案】B
【解析】23÷2=11…1，11÷2=5…1，5÷2=2…1，2÷2=1…0，1÷2=0…1，故23（10）=10111（2）．故选B．
4．【答案】D
【解析】由题意知，，解得．故选D．
5．【答案】B
【解析】．
6．【答案】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．
7．【答案】A
【解析】∵，∴．
8．【答案】5
【解析】求最大公约数的过程如下：，，，，．故13是最大公约数，共进行了5次减法运算．
9．【答案】29（10）
【解析】由于45（6）=4×61+5×60=29（10）．故答案为：29（10）．
10．【答案】5
【解析】，不难发现要经过5次乘法，5次加法运算．
11．【答案】详见解析．
【解析】288－153＝135，153－135＝18，135－18＝117，117－18＝99，99－18＝81，81－18＝63，63－18＝45，
45－18＝27，27－18＝9，18－9＝9．
因此288与153的最大公约数为9．
12．【答案】详见解析．
13．【答案】D
【解析】因为，，，，所以最小的数是．故选D．
14．【答案】B
【解析】
，
则，，故选B．
15．【答案】C
【解析】∵，，，，∴和的最大公约数是7，即．二进制数化为十进制数为，即，则．故选C．
16．【答案】A
【解析】123-48=75，75-48=27，48-27=21，27-21=6，21-6=15，15-6=9，9-6=3，6-3=3，所以123和48的最大公约数是3．
17．【答案】C
【解析】（2）．
18．【答案】B
19．【答案】213
【解析】∵，，∴．
20．【答案】（1）3809；（2）．
【解析】（1）=；
（2）用16连续去除1285，直到商为0为止，所得到的余数依次从右向左排列，就得到．
21．【答案】详见解析．
【解析】412（5）=2×50+1×51+4×52=2+5+4×25=107，
∵107=7×15+2，
15=7×2+1，
2=7×0+2．
∴把5进制的数412（5）化为7进制是212（7）．
22．【答案】详见解析．
【解析】辗转相除法：
319＝261×1＋58，
261＝58×4＋29，
58=29×2，
所以261与319的最大公约数为29．