高中数学必修三1.3算法案例-辗转相除法

知识1．求两个正整数的最大公约数的算法 （1）辗转相除法①定义：辗转相除法是用于求_____________的最大公约数的一种算法，这种算法是由欧几里得在公元前300年左右首先提出的，因而又叫欧几里得算法．就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成一对新数，继续上面的除法，直到余数为零，则这时较小的数就是原来两个数的最大公约数． ②算法步骤用辗转相除法求两个正整数的最大公约数，其算法步骤如下： 第一步，给定两个正整数,m n ． 第二步，计算m 除以n 所得的余数r ． 第三步，,m n n r ==．第四步，若0r =，则,m n 的最大公约数等于m ；否则，返回第二步． ③程序框图如图所示：④程序如下：INPUT m ，n DOr=m MOD n m=n n=rPRINT m END或INPUT m ，nr=1 While r>0 r=m MOD n m=n n=rPRINT m END（2）更相减损术①定义：中国古代的数学专著《九章算术》中记载着“更相减损术”，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也．以等数约之．” ②算法步骤第一步，任意给定两个正整数，判断它们是否都是偶数．若是，用2约简；若不是，执行第二步． 第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数．继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数． ③程序框图④程序如下：INPUT “a ，b=”;a ，b WHILE a≠b r=a-bIF b>r THEN a=b b=r ELSE a=r END IF WEND PRINT b END2．秦九韶算法（1）定义及原理：把一个n 次多项式1110()n n n n f a x a x x a x a --=++⋅⋅⋅++改写成如下形式：2110()((()))n n n f a x a x x a x a x a --=⋅⋅⋅+++⋅⋅+⋅+．求多项式的值时，首先计算最内层括号内一次多项式的值，即11n n v a x a -=+，然后由内向外逐层计算一次多项式的值，即212323,n n v v x a v v x a --=+=+，…，10n n v v x a -=+，这种求n 次多项式()f x 的值的方法叫做秦九韶算法．（2）秦九韶算法程序化的可行性探讨：观察秦九韶算法中的n 个一次式，可见计算k v 时要用到1k v -的值，若令0n v a =，我们可以得到下面的递推公式：0____________(1,2,,)n k v a v k n =⎧⎨==⋅⋅⋅⎩．这是一个在秦九韶算法中反复执行的步骤，可以用循环结构来实现． （3）算法步骤第一步，输入多项式次数n 、最高次项的系数n a 和x 的值． 第二步，将v 的值初始化为n a ，将i 的值初始化为n －1． 第三步，输入i 次项的系数i a ． 第四步，,1i v vx a i i =+=-．第五步，判断i是否大于或等于0．若是，则返回第三步；否则，输出多项式的值v．（4）程序框图如图所示：（5）程序如下：INPUT “n=”；nINPUT “an=”；aINPUT “x=”；xv=ai=n-1WHILE i>=0PRINT “i=”；iINPUT “ai=”；av=v*x+ai=i-1WENDPRINT vEND3．进位制（1）定义：进位制是人们为了计数和运算方便而约定的记数系统，约定满二进一，就是二进制；满十进一，就是十进制；满六十进一，就是六十进制；等等．也就是说，“满几进一”就是几进制，几进制的基数就是几．一般地，若k 是一个大于1的整数，那么以k 为基数的k 进制数可以表示为一串数字连写在一起的形式：1210()110110(,,,,,0<,0,,,)n n n k n n n n a a a a a a a a a a k a a a k ----⋅⋅⋅⋅⋅⋅∈<≤⋅⋅⋅<N ．说明：①若一个数为十进制数，其基数可以省略不写．②若是其他进位制的数，在没有特别说明的前提下，其基数必须写出，常在数的右下角标明基数． （2）将k 进制数转化为十进制数 ①算法步骤：计算k 进制数a 的右数第i 位数字i a 与1i k -的乘积1i i a k -⋅，再将其累加，这是一个重复操作的步骤．所以，可以用循环结构来构造算法，算法步骤如下： 第一步，输入,a k 和n 的值．第二步，将b 的值初始化为0，i 的值初始化为1． 第三步，1,1i i b b a k i i -=+⋅=+．第四步，判断i n >是否成立．若是，则执行第五步；否则，返回第三步． 第五步，输出b 的值． ②程序框图如图所示：③程序如下：INPUT “a ，k ，n=”；a ，k ，n b=0 i=1 t=a MOD 10 DOb=b+t*k^(i-1) a=a\10 t=a MOD 10 i=i+1LOOP UNTIL i>n PRINT b END（3）将十进制数转化为k 进制数 ①转化方法：十进制数化为k 进制数用____________，即先把十进制数a 除以k ，商为0q ，余数为0r ，再把0q 除以k ，商为1q ，余数为1r ，…，反复进行这种除法，直到商1n q -除以k 所得的商为0，余数是n r ，即1n n q r -=为止，此时将所有余数按从右到左排列就得到所要求的k 进制数10()n n k r r r -⋅⋅⋅． ②算法步骤：第一步，给定十进制正整数a 和转化后的数的基数k ． 第二步，求出a 除以k 所得的商q ，余数r ． 第三步，把得到的余数依次从右到左排列．第四步，若0q ≠，则a q =，返回第二步；否则，输出全部余数r 排列得到的k 进制数． ③程序框图如图所示：④程序如下：INPUT “a ，k=”；a ，k b=0 i=0 DO q=a\k r=a MOD k b=b+r*10^i i=i+1 a=qLOOP UNTIL q=0 PRINT b END知识参考答案： 1．（1）两个正整数2．（2）1k n k v x a --+3．（3）①除k 取余法重点重点辗转相除法、更相减损术、秦九韶算法、进位制难点用秦九韶算法求多项式的值，进位制间的转换易错易对秦九韶算法中的运算次数理解错误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．秦九韶算法秦九韶算法的实质是：求多项式1110()n n n n f a x a x x a x a --=++⋅⋅⋅++的值时，转化为求n 个一次多项式的值，共进行n 次乘法运算和n 次加法运算．这种算法的运算次数较少，是多项式求值比较先进的算法． 【例3】 用秦九韶算法计算多项式f （x ）=12+35x –8x 2+79x 3+6x 4+5x 5+3x 6在x =–4时的值时，V 3的值为A ．–845B ．220C ．–57D ．34【答案】C【解析】∵多项式f （x ）=12+35x –8x 2+79x 3+6x 4+5x 5+3x 6=（（（（（3x +5）x +6）x +79）x –8）x +35）x +12， 当x =–4时，∴v 0=3，v 1=3×（–4）+5=–7，v 2=–7×（–4）+6=34，v 3=34×（–4）+79=–57．故选C ．【例4】用秦九韶算法计算函数f （x ）=2x 4+3x 3+5x –4在x =2时的函数值．【答案】62【名师点睛】利用秦九韶算法计算多项式的值的策略：（1）正确地将多项式改写，若在多项式中有几项不存在，可将这些项的系数看成0，即把这些项看做0n x ⨯． （2）由内向外逐次计算．（3）每一步计算结果准确，由于下一次计算用到上一次计算的结果，应认真、细致地计算每一步． 3．进位制把一个非十进制数转化为另一种非十进制数，通常是把这个数先转化为十进制数，然后再利用除k 取余法，把十进制数转化为k 进制数． 【例5】将八进制数127（8）化为十进制数． 【答案】87【解析】()21081271828786416787=⨯+⨯+⨯=++=．【例6】已知一个k 进制的数123（k ）与十进制的数38相等，求k 的值． 【答案】5【解析】将转化为十进制，()210212312323k k k k k k =⨯+⨯+⨯=++， 由题意，得k 2+2k +3=38， 所以k 2+2k –35=0， 所以k =5或k =–7（舍） 所以k =5．【名师点睛】除k 取余法的两个关注点：①要连续除：用k 连续去除十进制数或所得的商，直到商为零为止． ②若是其他进位制的数，在没有特别说明的前提下，其基数必须写出，常在数的右下角标明基数．基础训练1．秦九韶算法的先进性主要体现在减少运算次数，下列说法正确的是A ．可以减少加法运算次数B ．可以减少乘法运算次数C ．同时减少加法和乘法的运算次数D ．加法次数和乘法次数都有可能减少2．用秦九韶算法求多项式652()7632f x x x x =+++，当4x =时的值，先算的是A ．4×4=16B ．7×4=28C ．4×4×4=64D ．7×4+6=343．把十进制的23化成二进制数是A ．00 110（2）B ．10 111（2）C ．10 1111（2）D ．11 101（2）4．若十进制数26等于k 进制数32，则k 等于A ．4B ．5C ．6D ．85．用更相减损术求294和84的最大公约数时，需要做减法的次数是A ．3B ．4C ．5D ．66．1 037和425的最大公约数是A ．51B ．17C ．9D ．37．已知多项式54321()4322f x x x x x x =++---，用秦九韶算法求(2)f -等于 A ．1972-B ．1972C ．1832D ．1832-8．用更相减损术求156与91的最大公约数时，需要做减法的次数是__________． 9．将45（6）改写成十进制数为__________．10．用秦九韶算法计算多项式5432()54321f x x x x x x =+++++当4x =时的值时，乘法运算的次数为__________．11．用更相减损术求288与153的最大公约数．12．用秦九韶算法求多项式5432()3532f x x x x x x =-+-+当2x =时的值．能力提升13．在下列四个数中，最小的数是A ．(9)85B ．(6)210C ．(4)1000D ．(2)11111114．用秦九韶算法计算多项式65432()256238103f x x x x x x x =+++-+-当4x =-时的值时，3v 的值为A ．742-B ．49-C ．18D ．18815．若98与63的最大公约数为a ，二进制数(2)110011化为十进制数为b ，则a b +=A ．53B ．54C ．58D ．6016．用更相减损术求123和48的最大公约数是A ．3B ．7C ．9D ．1217．计算机是将信息转换成二进制处理，二进制即“逢二进一”，如(2)1101表示二进制数．将它转化成十进制形式是32101212021213⨯+⨯+⨯+⨯=，那么将二进制数1611111个（2）转换成十进制形式是A ．217-2B ．216-2C ．216-1D ．215-118．在下列各数中，最大的数是A ．(9)85B ．(6)210C ．(4)1000D ．(2)1111119．完成进位制之间的转化：(5)413=__________(7)． 20．（1）把八进制数()87341化为十进制数；（2）把1285化为16进制数．21．先将412（5）化成十进制的数，然后用“除k取余法”再化成七进制的数．22．用辗转相除法和更相减损术求261与319的最大公约数．参考答案1 2 3 4 5 6 7 13 14 15 16 17 18B D B D B B A D BC A C B 1．【答案】B【解析】通过对秦九韶算法的理解，可知它的主要作用是减少乘法的次数，将原来的乘法次数由(1)2n n减少到n，而对加法没有影响．故选B．2．【答案】D3．【答案】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【解析】由题意知，10 2632k k =⨯+⨯，解得8k =．故选D ． 5．【答案】B【解析】()()()()()294,84210,84126,8484,4242,42→→→→． 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【解析】∵1()((((43)2)1)1)2f x x x x x x =++---，∴197(2)2f -=-．8．【答案】5【解析】求最大公约数的过程如下：1569165-=，916526-=，652639-=，392613-=，261313-=．故13是最大公约数，共进行了5次减法运算． 9．【答案】29（10）【解析】由于45（6）=4×61+5×60=29（10）．故答案为：29（10）． 10．【答案】5【解析】5432((((54)3)2)1()54321)1f x x x x x x x x x x x =++++++++++=，不难发现要经过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【解析】因为(9)8589577=⨯+=，2(6)210261678=⨯+⨯=，3(4)10001464=⨯=，543210(2)11111122222263=+++++=，所以最小的数是(2)111111．故选D ．14．【答案】B【解析】65432()256238103f x x x x x x x =+++-+- (((((25)6)23)8)10)3x x x x x x =+++-+-，则010212,52(4)53,63(4)618v v v x v v x ==+=⨯-+=-=+=-⨯-+=，322318(4)v v x =+=⨯-2349+=-，故选B ． 15．【答案】C【解析】∵9816335=⨯+，6313528=⨯+，351287=⨯+，2874=⨯，∴98和63的最大公约数是7，即7a =．二进制数(2)110011化为十进制数为54321012120202121251⨯+⨯+⨯+⨯+⨯+⨯=，即51b =，则58a b +=．故选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【解析】161111个（2）1514016=12+12++12=21⨯⨯⨯-．18．【答案】B19．【答案】213【解析】∵012(5)41335154535425108=⨯+⨯+⨯=++⨯=，012108371727=⨯+⨯+⨯，∴(7)(5)421313=．20．【答案】（1）3809；（2）()16505．【解析】（1）()87341=3210783848183809⨯+⨯+⨯+⨯=；（2）用16连续去除1285，直到商为0为止，所得到的余数依次从右向左排列，就得到()161285505=． 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．。