LOOP UNTIL a=b PRINT a^i END
要点诠释:
用辗转相除法步骤较少,而更相减损术虽然有些步骤较长,但运算简单. 要点三、秦九韶计算多项式的方法
121210
1231210
231210
1210()()(())((()))n n n n n n n n n n n n n n n n n n n f x a x a x a x a x a a x a x a x a x a a x a x a x a x a a x a x a x a x a --------------=+++
++=+++++=+++++=
=+++
+
+
令12(1)(
(()))k n n n n k n k v a x a x a x a x a -----=+++
++,则有01n
k k n
k
v a v v x a
--=??
=+?,其中
n k ,2,1=.这样,我们便可由0v 依次求出n v v v ,,21;
1323212101,,,a x v v a x v v a x v v a x v v n n n n n +=+=+=+=----
要点诠释:
显然,用秦九韶算法求n 次多项式的值时只需要做n 次乘法和n 次加法运算 要点四、进位制
进位制是一种记数方式,用有限的数字在不同的位置表示不同的数值.可使用数字符号的个数称为基数,基数为n ,即可称n 进位制,简称n 进制.现在最常用的是十进制,通常使用10个阿拉伯数字0-9进行记数.
对于任何一个数,我们可以用不同的进位制来表示.比如:十进数57,可以用二进制表示为111001,也可以用八进制表示为71、用十六进制表示为39,它们所代表的数值都是一样的.
表示各种进位制数一般在数字右下角加注来表示,如111001(2)表示二进制数,34(5)表示5进制数. 1.k 进制转换为十进制的方法:
012211)(0121a k a k a k a k a a a a a a a n n n n k n n +?+?++?+?=--- ,
把k 进制数a 转化为十进制数b 的算法程序为:
INPUT “ a,k,n=”;a,k,n i=1 b=0
WHILE i<=n t=GET a[i] b=b+t*k^(i-1) i=i+1 WEND PRINT b END
2.十进制转化为k 进制数b 的步骤为:
第一步,将给定的十进制整数除以基数k ,余数便是等值的k 进制的最低位; 第二步,将上一步的商再除以基数k ,余数便是等值的k 进制数的次低位;
第三步,重复第二步,直到最后所得的商等于0为止,各次所得的余数,便是k 进制各位的数,最后一次余数是最高位,即除k 取余法.
要点诠释:
1、在k 进制中,具有k 个数字符号.如二进制有0,1两个数字.
2、在k 进制中,由低位向高位是按“逢k 进一”的规则进行计数.
3、非k 进制数之间的转化一般应先转化成十进制,再将这个十进制数转化为另一种进制的数,有的也可以相互转化.
【典型例题】
类型一:辗转相除法与更相减损术
例1.用辗转相除法求下列两数的最大公约数,并且用更相减损术检验你的结果: (1)80,36;(2)294,84. 【答案】(1)4(2)42
【解析】(1)80=36×2+8,
36=8×4+4.
8=4×2+0.
即80与36的最大公约数是4.
验证:80-36=44,
44-36=8.
36-8=28.
28-8=20.
20-8=12.
12-8=4.
8-4=4.
∴80与36的最大公约数为4.
(2)294=84×3+42,
84=42×2.
即294与84的最大公约数是42.
验证:∵294与84都是偶数可同时除以2,
即取147与42的最大公约数后再乘2.
147-42=105.
105-42=63.
63-42=21.
42-21=21.
∴294与84的最大公约数为21×2=42.
【总结升华】比较辗转相除法与更相减损术的区别
(1)都是求最大公约数的方法,计算上辗转相除法以除法为主,更相减损术以减法为主,计算次数上辗转相除法计算次数相对较少,特别当两个数字大小区别较大时计算次数的区别较明显;
(2)从结果体现形式来看,辗转相除法体现结果是以相除余数为0则得到,而更相减损术则以减数与差相等而得到.
由该题可以看出,辗转相除法得最大公约数的步骤较少.
对比两种方法控制好算法的结束,辗转相除法是到达余数为0,更相减损术是到达减数和差相等.
举一反三:
【变式1】(1)用辗转相除法求123和48的最大公约数.
(2)分别用辗转相除法和更相减损术求105与357的最大公约数.
【答案】21
【解析】(1)123=2×48+27
48=1×27+21
27=1×21+6
21=3×6+3
6=2×3+0
最后6能被3整除,得123和48的最大公约数为3.
(2)辗转相除法:357=105×3+42,105=42×2+21,42=21×2.
故105与357的最大公约数为21.
更相减损术:357-105=252,252-105=147,147-105=42,105-42=63,63-42=21,42-21=21.故105与357的最大公约数为21.
例2.求三个数:168,54,264的最大公约数.
【思路点拨】运用更相减损术或辗转相除法,先求168与54的最大公约数a ,再求a 与264的最大公约数.
【答案】6 【解析】
采用更相减损术先求168与54的最大公约数.
(168,54)→(114,54)→(60,54)→(6,54)→(6,48)→(6,42)→(6,36)→(6,30)→(6,24)→(6,18)→(6,12)→(6,6) 故168与54的最大公约数为6.
采用辗转相除法求6和264的最大公约数.
因为264=44×6+0,所以6为264与6的最大公约数,也是三个数的最大公约数.
【总结升华】求最大公约数通常有两种方法:一是辗转相除法;二是更相减损术,对于3个数的最大公约数的求法,则是先求其中两个数的最大公约数m ,再求m 与第三个数的最大公约数.同样可推广到求3个数以上的数的最大公约数.
举一反三:
【变式1】求三个数324,243,135的最大公约数. 【解析】∵324=243×1+81, 243=81×3+0,
∴324与243的最大公约数为81. 又135=81×1+54, 81=54×1+27, 54=27×2+0,
∴81与135的最大公约数为27.
∴三个数324,243,135的最大公约数为27. 更相减损术: ∵324-243=81, 243-81=162, 162-81=81,
∴81是324和243的最大公约数. 又135-81=54, 81-54=27, 54-27=27,
∴27是81与135的最大公约数.
∴三个数324,243,135的最大公约数为27.
类型二:秦九韶算法
例3.(2018秋 福建月考)利用秦九韶算法计算5
4
3
2
()23456f x x x x x x =+++++在x =5时的值. 【思路点拨】据秦九韶算法,把多项式改写为f (x )=((((x +2)x +3)x +4)x +5)x +6.按照从内到外的顺序,依次计算x =5时的值,即可得出.
【答案】4881.
【解析】依据秦九韶算法,把多项式改写为f (x )=((((x +2)x +3)x +4)x +5)x +6. 按照从内到外的顺序,依次计算x =5的值:
01v =,
11527v =?+=;
275338v =?+=; 33854194v =?+=; 419455975v =?+=; 5975564881v =?+=,
故f (5)=4881.
【总结升华】利用秦九韶算法计算多项式的值的关键是能正确地将所给多项式改写,然后由内向外逐层计算,由于下一次计算需用到上一次的结果,故应认真、细心,确保中间结果的准确性. 举一反三: 【变式1】(2017秋 河北张家口月考)用秦九韶算法计算多项式
23456()1235879653f x x x x x x x =+-++++在x =―4时的V 4值.
【答案】-220.
【解析】f (x )=(((((3x +5)x +6)x +79)x ―8)x +35)x +12,
v 0=3,
v 1=3×(―4)+5=―7, v 2=(-7)×(―4)+6=34, v 3=34×(―4)+79=―57, v 4=―57×(―4)―8=-220.
【变式2】用秦九韶算法计算多项式6
5
4
3
2
()654327f x x x x x x x =++++++在x=0.4时的值时,需做加法和乘法的次数和是( )
A .10
B .9
C .12
D .8 【答案】 C
【解析】 ()(((((6
5)4)3)2)1f x x x x x x x =++++++.
∴加法6次,乘法6次, ∴6+6=12(次),故选C .
类型三:进位制
例4.把87化为二进制数. 【答案】1010111(2)
【解析】 因为87=2×43+1,43=2×21+1,21=2×10+1,10=2×5+0,5=2×2+1,2=2×1+0.1=2×0+1.
所以87=2×(2×(2×(2×(2×2+1)+0)+1)+1)+1 =2×(2×(2×(2×(22+1)+0)+1)+1)+1 =…
=1×26+0×25+1×24+0×23+1×22+1×2+1 =1010111(2). 【总结升华】(1)本题的算法叫除2取余法.上述解法可以推广到把十进制数化为k 进制数的算法,称为除k 取余法.
(2)本题还可以用下面的除法算式表示如图:
把上式各步所得的余数从下到上排列,得87=1010111
(2).
举一反三: 【变式】(1)将十进制数2l 转化为五进制数. (2)把十进制数48转化为二进制数.
【解析】(1)用除5取余法,可得
∴21=41(5).
(2) 将十进制数48转化为二进制数的除法算式如图所示. 把上式中各步所得的余数从下到上排列,得到48=110000(2).
【总结升华】在解答过程中常会出现把上图中各步所得的余数从上到下排列的错误,应注意避免. 例5.把下列各数化为十进制数.
(1)20121(3);(2)20121(4). 【答案】(1)178 (2)537
【解析】 (1)20121(3)=2×34+0×33+1×32+2×3+1=178. (2)20121(4)=2×44+0×43+1×42+2×4+1=537. 【总结升华】k 进制数转化为十进制数的方法是把k 进制数表示为各位上的数字与k 的幂的乘积之和,从右边起,第i 位数字对应k 的幂为1i k -.
举一反三:
【变式1】在十进制中,01232004410010010210=?+?+?+?,那么在五进制中数码2 004折合成十进制为( )
A .29
B .254
C .602
D .2 004 【答案】B
【解析】0123200445050525254=?+?+?+?=,故选B .
【变式2】将十进制数34换算成二进制数,即(34)10=________. 【答案】100010(2). 【解析】34÷2=17......0 17÷2=8......1 8÷2=4......0 4÷2=2......0 2÷2=1......0 1÷2=0 (1)
故34(10)=100010(2) 故答案为:100010(2).
【总结升华】在解答过程中常会出现把图中各步所得的余数从上到下排列的错误,应注意避免.
【巩固练习】
1.1337与382的最大公约数是( ).
A .3
B .382
C .191
D .201
2.用辗转相除法求得459和357的最大公约数是( ). A .3 B .9 C .17 D .51
3. 用秦九韶算法求多项式6
5
2
()7632f x x x x =+++当x=4时的值时,先算的是( ). A .4×4=16 B .7×4=28 C .4×4×4=64 D .7×4+6=34
4.用秦九韶算法计算5
4
3
2
()6429f x x x x x x =-+--,需要加法(或减法)与乘法运算的次数分别为( ).
A .5,4
B .5,5
C .4,4
D .4,5 5.用秦九韶算法计算多项式
65432()126016024019264f x x x x x x x =-+-+-+,当2x =时,(2)f 的值为
A .0
B .2
C .-2
D .4 6.(2018春 广东珠海期末)将二进制数11100(2)转化为四进制数,正确的是( )
A .120(4)
B .130(4)
C .200(4)
D .202(4) 7. 已知一个k 进制数132与十进制数30相等,那么k 等于( ). A .-7或4 B .-7 C .4 D .都不对 8. 下列各数中最小的数是( ).
A .85(9)
B .210(6)
C .1000(4)
D .111111(2) 9.(2018春 湖南怀化期末)四进制数123(4)化为十进制数为________. 10. 三个数72,120,168的最大公约数是 。
11.(2017 河北冀州市模拟)在不同的进位制之间的转化中,若132(k )=42(10),则k =________. 12.(2017春 福州月考)用秦九韶算法计算多项式5
4
3
2
()54321f x x x x x x =+++++,求当x =3时的值. 13.(2018秋 湖北汉川市期中)(1)利用辗转相除法求8251和6105的最大公约数
(2)利用秦九韶算法求多项式5
4
3
2
()1f x x x x x x =+++++在x =3时的值.(两问都按算法写步骤方可得分)
14. 把“五进制”数)5(1234转化为“十进制”数,再把它转化为“八进制”数。
【答案与解析】
1.【答案】C
【解析】 1337=382×3+191,382=191×2+0,1337与382的最大公约数为191。 2.【答案】D
【解析】 ∵459=357×1+102,357=102×3+51,102=51×2+0,即51为459和357的最大公约数。 3.【答案】D
【解析】因为11101210()(
(()))n n n n n n n f x a x a x a x a a x a x a x a x a ----=++
++=++++,所以用秦
九韶算法求多项式65
2
()7632f x x x x =+++当x=4时的值时,先算的是7×4+6=34。
4.【答案】D
【解析】 n 次多项式当最高次项的系数不为1时,需进行n 次乘法,若各项均不为零,则需进行n 次加法(或减法),缺一项就减少一次加法(或减法)运算,而这个五次多项式与5次项系数不为1,缺常数项。因而乘法次数为5次,加法(或减法)次数为5-1=4(次)。 5.【答案】 A 【解析】6
5
4
3
2
()126016024019264f x x x x x x x =-+-+-+
(((((12)60)160)240)192)64x x x x x x =-+-+-+,然后由内向外计算.
6.【答案】B
【解析】先将“二进制”数11100(2)化为十进制数为432
(10)12121228?+?+?= 然后将十进制的28化为四进制:
28÷4=7余0 7÷4=1余3 1÷4=0余1
所以结果是130(4) 故选:B . 7. 【答案】C
【解析】 ∵132(k )=1×k2+3k+2=30,∴k=-7或k=4。又∵k >0,∴k=4。故选C 。 8. 【答案】 D
【解析】 ∵85(9)=8×9+5=77;
216(6)=2×62+1×6=78;1000(4)=1×43=64; 111111(2)=1×25+1×24+1×23+1×22+1×2+1=63。 因此111111(2)最小,故选D 。 9.【答案】27 【解析】由题,2
1
123(4)14243427=?+?+?=, 故答案为:27. 10. 【答案】24
【解析】12072148,7248124,48242,168247=?+=?+=?=? 11.【答案】5
【解析】∵132(k )=42(10),
∴ 23242k k ++=, 解得:k =5,或k =-8(舍去),
故答案为:5
12.【答案】1642
【解析】f (x )=((((5x +4)x +3)x +2)x +1)x +1
当x =3时 v 0=5
v 1=5×3+4=19
v 2=19×3+3=60 v 3=60×3+2=182 v 4=182×3+1=547 v 5=547×3+1=1642
所以当x =2时,f (3)=1642 13.【答案】(1)37;(2)364 【解析】(1)8251=6105×1+2145
6105=2146×2+1813 2146=1813×1+333 333=148×2+37 148=37×4
所以8251与6105的最大公约数就是37
(2)5
4
3
2
()1((((1)1)1)1)1f x x x x x x x x x x x =+++++=+++++ 当x =3时
03v =, 14v =; 213v =; 340v =;
4121v =; 5364v =.
14. 【答案】194 302
【解析】3210
123415253545194=?+?+?+?=(5)
8194824830余
203
194302∴=(8)