算法案例【学习目标】1.理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析；2.基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序；3.了解秦九韶算法的计算过程，并理解利用秦九韶算法可以减少计算次数提高计算效率的实质；4.了解各种进位制与十进制之间转换的规律，会利用各种进位制与十进制之间的联系进行各种进位制之间的转换.【要点梳理】要点一、辗转相除法也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的.利用辗转相除法求最大公约数的步骤如下：第一步：用较大的数m除以较小的数n得到一个商q0和一个余数r；第二步：若r0=0，则n为m，n的最大公约数；若r≠0，则用除数n除以余数r得到一个商q1和一个余数r1；第三步：若r1=0，则r为m，n的最大公约数；若r1≠0，则用除数r除以余数r1得到一个商q2和一个余数r2；……依次计算直至rn =0，此时所得到的rn－1即为所求的最大公约数.用辗转相除法求最大公约数的程序框图为：程序：INPUT “m=”;m INPUT “n=”;n IF m<n THEN x=mm=nn=xEND IFr=m MOD n WHILE r<>0r=m MOD nm=nn=rWEND PRINT n END 要点诠释：辗转相除法的基本步骤是用较大的数除以较小的数，考虑到算法中的赋值语句可以对同一变量多次赋值，我们可以把较大的数用变量m 表示，把较小的数用变量n 表示，这样式子)0(n r r q n m <≤+⋅=就是一个反复执行的步骤，因此可以用循环结构实现算法.要点二、更相减损术我国早期也有解决求最大公约数问题的算法，就是更相减损术.更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也.以等数约之.翻译出来为：第一步：任意给出两个正整数；判断它们是否都是偶数.若是，用2约简；若不是，执行第二步.第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数.继续这个操作，直到所得的数相等为止，则这个数(等数)就是所求的最大公约数.理论依据：由r b a r b a +=→=-，得b a ,与r b ,有相同的公约数 更相减损术一般算法：第一步，输入两个正整数)(,b a b a >；第二步，如果b a ≠，则执行3S ，否则转到5S ； 第三步，将b a -的值赋予r ；第四步，若r b >，则把b 赋予a ，把r 赋予b ，否则把r 赋予a ，重新执行2S ； 第五步，输出最大公约数b . 程序:INPUT “a=”，a INPUT “b=”，b WHILE a<>bIF a>=ba=a-b;ELSEb=b-aWENDENDPRINT b或者INPUT “请输入两个不相等的正整数”；a，bi=0WHILE a MOD 2=0 AND b MOD 2=0a=a/2b=b/2i=i+1WENDDOIF b<a THENt=aa=bb=tEND IFc=a－ba=bb=cLOOP UNTIL a=bPRINT a^iEND要点诠释：用辗转相除法步骤较少，而更相减损术虽然有些步骤较长，但运算简单.要点三、秦九韶计算多项式的方法12121012312102312101210()()(())((()))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 --------------=+++++=+++++=+++++==+++++L L L L LL L令12(1)((()))k n n n n k n k v a x a x a x a x a -----=+++++L L ，则有01nk k n kv a v v x a --=⎧⎨=+⎩，其中n k Λ,2,1=.这样，我们便可由0v 依次求出n v v v Λ,,21；01323212101,,,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=0WHILE i<=nt=GET a[i]b=b+t*k^(i-1)i=i+1WENDPRINT bEND2.十进制转化为k进制数b的步骤为：第一步，将给定的十进制整数除以基数k，余数便是等值的k进制的最低位；第二步，将上一步的商再除以基数k，余数便是等值的k进制数的次低位；第三步，重复第二步，直到最后所得的商等于0为止，各次所得的余数，便是k进制各位的数，最后一次余数是最高位，即除k取余法.要点诠释：1、在k进制中，具有k个数字符号.如二进制有0，1两个数字.2、在k进制中，由低位向高位是按“逢k进一”的规则进行计数.3、非k进制数之间的转化一般应先转化成十进制，再将这个十进制数转化为另一种进制的数，有的也可以相互转化.【典型例题】类型一：辗转相除法与更相减损术例1．分别用辗转相除法和更相减损术求378与90的最大公约数．【答案】18【解析】用辗转相除法：378=90×4+18，90=18×5．∴378与90的最大公约数是18．用更相减损术：∵378与90都是偶数，∴用2约分后得189和45．189－45=144，144－45=99，99－45=54，54－45=9，45－9=36，36－9=27，27－9=18，18－9=9．【总结升华】比较辗转相除法与更相减损术的区别(1)都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显；(2)从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到.由该题可以看出，辗转相除法得最大公约数的步骤较少.对比两种方法控制好算法的结束，辗转相除法是到达余数为0，更相减损术是到达减数和差相等.举一反三：【变式1】（1）用更相减损术求两个正数84与72的最大公约数．（2）利用辗转相除法求3869与6497的最大公约数与最小公倍数．【解析】（1）因为84=21×4，72=18×4，所以21－18=3，18－3=15，15－3=12，12－3=9，9－3=6，6－3=3．所以21和18的最大公约数等于3．所以84和72的最大公约数等于12．【总结升华】先约简，再求21与18的最大公约数，然后乘以约简的4得84与72的最大公约数．（2）6497=3869×1+2628，3869=2628×1+1241，2628=1241×2+146，1241=146×8+73，146=73×2+0．最小公倍数为3 869×6497÷73=344341．例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的最大公约数．【答案】27【解析】∵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.甲、乙、丙三种溶液分别重147g、343g、133g，现要将它们分别全部装入小瓶中，每个小瓶装入液体的质量相同，问每瓶最多装多少？【思路点拨】由题意，每个小瓶最多能装的溶液的质量应是三种溶液质量的最大公约数.【答案】7g【解析】先求147与343的最大公约数.343-147=196，196-147=49，147-49=98，98-49=49，∴147与343的最大公约数是49.再求49与133的最大公约数.133-49=84，84-49=35，49-35=14，35-14=21，21-14=7，14-7=7.∴147，343，133的最大公约数是7.故每瓶最多装7g.【总结升华】本题关键是分析清楚题意，找出三个数的最大公约数.求三个以上(含三个数)的数的最大公约数时，可依次通过求两个数的最大公约数与第三个数的最大公约数来求得.类型二：秦九韶算法例4．利用秦九韶算法求2345()10.50.166630.041680.00835f x x x x x x =+++++在x=0.2时的值．写出详细计算过程．【思路点拨】秦九韶算法是我国南宋的数学家秦九韶首先提出来的．（1）特点：它通过一次式的反复计算，逐步计算高次多项式的求值问题，即将一个n 次多项式的求值问题，归结为重复计算n个一次式1()i i a x a -+．即1210()((()))n n n f x a x a x a x a x a --=++++L L ．（2）具体方法如下：已知一个一元n 次多项式1110()n n n n f x a x a x a x a --=++++L 0．当x=x 0，我们可按顺序一项一项地计算，然后相加，求得0()f x ．【答案】1.2214024 【解析】 v 0=0.00835，v 1=v 0x+0.04168=0.00835×0.2+0.04168=0.043 35， v 2=v 1x+0.16663=0.04335×0.2+0.16663=0.1753， v 3=v 2x+0.5=0.1753×0.2+0.5=0.53506， v 4=v 3x+1=0.53506×0.2+1=1.107012， v 5=v 4x+1=1.107012×0.2+1=1.2214024． 【总结升华】秦九韶算法的原理是01(1,2,3,,)n kk n k v a v v x a k n --=⎧⎨=+=⎩L ．在运用秦九韶算法进行计算时，应注意每一步的运算结果，像这种一环扣一环的运算，如果错一步，则下一步，一直到最后一步就会全部算错．同学们在计算这种题时应格外小心． 举一反三：【变式1】用秦九韶算法求多项式764()85321f x x x x x =++++当x=2时的值． 【答案】1397【解析】765432()85030021((((((85)0)3)0)0)2)1f x x x x x x x x x x x x x x x =++⋅++⋅+⋅++=+++++++． v 0=8，v 1=8×2+5=21，v 2=21×2 4-0=42，v 3=42×2 4-3=87，v 4=87×2+0=174，v 5=174×2+0=348，v 6=348×2+2=698，v 7=698×2+1=1397，所以，当x=2时，多项式的值为1397．【变式2】用秦九韶算法计算多项式65432()654327f x x x x x x x =++++++在x=0.4时的值时，需做加法和乘法的次数和是（ ）A ．10B ．9C ．12D ．8【答案】 C【解析】 ()(((((65)4)3)2)1)7f x x x x x x x =++++++．∴加法6次，乘法6次，∴6+6=12（次），故选C ．类型三：进位制例5．（1）试把十进制数136转化为二进制数；（2）试把十进制数1 234转化为七进制数．【答案】（1）10001000【解析】 （1）由于136=2×68+0，68=2×34+0．34=2×17+0．17=2×8+1．8=2×4+0．4=2×2+0．2=2×1+0．1=2×0+1．所以136=10001000（2）．（2）1234=7×176+2，176=7×25+1．25=7×3+4．3=7×0+3．所以1234=3412（7）．【总结升华】（1）应注意搞清每一次除法中的被除数、除数，当商为零时停止除法，把每步所得的余数倒着排成一个数，就是相应的二进制数．（2）十进制数转化为七进制数与转化为二进制数的方法类似，要认真体会其原理．举一反三：【变式1】（1）把十进制数89转化为二进制数；（2）将十进制数2l转化为五进制数．【解析】（1）用除2取余法：∴89=2×(2×(2×(2×(2×(2×(2×0+1)+0)+1)+1)+0)+0)+1=2×(2×(2×(2×2×(22×0+2+0)+1)+1)+0)+0)+1 =……=1×26+0×25+1×24+1×23+0×22×0×21+1×20=1011001(2)（2）用除5取余法，可得．∴21=41（5）例6．把210121l转化为八进制数．（3）【答案】3326（8）【解析】先将三进制数转化为十进制数，再将十进制数转化为八进制数．2101211（3）=2×36+1×35+1×33+2×32+1×31+1×30=1458+243+27+18+3+1=1750．1750=8×218+6．218=8×27+2．27=8×3+3．∴1750=8×218+6=8（8×27+2）+6=8（8（8×3+3）+2）+6=8（3×82+3×8+2）+6=3×83+3×82+2×8+6=3326（8），∴2101211（3）=3326（8）．【总结升华】从本例的解答中，大家要有两个提高．第一，把三进制数转化为八进制数，十进制数起了桥梁和纽带的作用，具体体现是2101211（3）=1750=3326（8）．第二，在把1750转化为3326（8）时，我们没有列竖式，大家要从中体会一下方法的内在规律．举一反三：【变式1】在十进制中，01232004410010010210=⨯+⨯+⨯+⨯，那么在五进制中数码2 004折合成十进制为（ ）A ．29B ．254C ．602D ．2 004【答案】B解析：0123200445050525254=⨯+⨯+⨯+⨯=，故选B ．【变式2】（1）将二进制数1611111L 123个（2）转化成十进制数；（2）将七进制数235（7）转化成八进制数．【答案】（1）2621-（2）174（8）【解析】对于（1），按照形式a n a n ―1a n ―2…a 1a 0（2）=a n ×2n+a n ―1×2n ―1+…+a 1×2+a n 计算即可；对于（2），先将七进制数转化成十进制数，再将所得十进数转化成八进制数．（1）151********(2)11111212121221=⨯+⨯++⨯+⨯=-L L 123个．（2）235（7）=2×72+3×7+5=124，利用除8取余法得124=174（8），过程如图所示，所以235（7）转化成八制数为174（8）． 【巩固练习】 1．1337与382的最大公约数是（ ）．A ．3B ．382C ．191D ．2012．用辗转相除法求得459和357的最大公约数是（ ）．A ．3B ．9C ．17D ．513.下列各数中最小的是( )A.)2(111111B.)6(210C.)4(1000D.(9)814.用秦九韶算法计算多项式65432()126016024019264f x x x x x x x =-+-+-+，当2x =时，(2)f 的值为A ．0B ．2C ．-2D ．45．把67转化为二进制数为（ ）．A ．1100001（2）B ．1000011（2）C ．110000（2）D ．100011l （2）6．用秦九韶算法求多项式52()42f x x x =-+当x=3时的值时，需要进行的乘法运算和加减运算的次数分别为（ ）．A ．4，2B ．5，3C ．5，2D ．6．27．已知一个k 进制数132与十进制数30相等，那么k 等于（ ）．A ．－7或4B ．－7C ．4D ．都不对8. 计算机中常用的十六进制是逢16进1的计数制，采用数字0～9和字母A ～F 共16个计数符号，这些符号与十进制数的对应关系如下表：十六进制0 1 2 3 4 5 6 7 8 9 A B C D E F 十进制 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 例如，用十六进制表示：E+D=1B ，则A ×B 等于（ ）．A ．6EB ．72C ．5FD ．B09.三个数72,120,168的最大公约数是．10．（1）l 011010（2）=________．（2）154（6）=________（7）．11．已知a=333，b=24，则使得a=bq+r （q ，r 均为自然数，且0≤r ＜b ）成立的q 和r 的值分别为________．12. 秦九韶的算法中有n 个一次式，若令0n v a =，我们可以得到01___(12).n k k v a v v x k n -=⎧⎨=+=⎩L ，，，，我们可以利用 结构来实现.13．用秦九韶算法求多项式x x x x x x x x f ++++++=234567234567)(当3=x 时的值．14．古时候，当边境有敌人来犯时，守边的官兵通过在烽火台上举火向国内报告，如下图，若烽火台上点火，则用数字1表示，若不点火用数字0表示，约定二进制数对应的十进制数的单位是1000，请你计算一下，这组烽火台表示边境有多少敌人入侵？15．设有甲、乙、丙三种溶液，质量分别为146kg 、334kg 、229kg ．要将它们分别全部装入小瓶中，每个小瓶装入液体的质量相同．每瓶最多装多少？【答案与解析】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. 【答案】A【解析】把这四个数都化为十进制数63111111)2(=，78210)6(=，641000)4(=，(9)8173=，故选A.4．【答案】A【解析】 按秦九韶算法计算．5．【答案】B【解析】 利用除2取余法易得67=1000011（2）．6．【答案】C【解析】52()42(((4))1))2f x x x x x x x x =-+=-+，所以需要进行5次乘法运算和2次加减运算．7. 【答案】C【解析】 ∵132（k ）=1×k2+3k+2=30，∴k=－7或k=4．又∵k ＞0，∴k=4．故选C ．8. 【答案】A【解析】A ×B 用十进制可以表示为10×11=110，而110=6×16+14，所以用十六进制表示为6E ，故选A ．9. 【答案】24【解析】 12072148,7248124,48242,168247=⨯+=⨯+=⨯=⨯10．【答案】80 130【解析】（1）1011010（2）=0×20+1×21+0×22+1×23+1×24+0×25+1×26=90．（2）154（6）=4×60+5×61+1×62=4+30+36=70．将70转化为七进制数，故70=130（7）．11．【答案】13，21【解析】 用333除以24，商即为q ，余数就是r ．333=24×13+21．12. 【答案】n k a -；循环13. 【答案】21324【解析】()((((((76)5)4)3)2)1)f x x x x x x x =++++++012345677,73627,273586,8634262,26236789,789322369,2369317108,71083021324,V V V V V V V V ==⨯+==⨯+==⨯+==⨯+==⨯+==⨯+==⨯+=(3)21324f ∴=14．【答案】27000【解析】由题图可知，从左到右的五个烽火台，表示二进制数的自左到右的五个数位．这组烽火台表示的二进制数是11011（2），转化为十进制数为11011（2）=1×24+1×23+0×22+1×21+1×20=16+8+2+1=27．又27×1000=27000，所以，这组烽火台表示边境共有27000个敌人入侵．15．【答案】536【解析】12515046636==，31513534436==，2208029936==． 15013515363636-=，13515120363636-=，12015105363636-=， 1051590363636-=，901575363636-=，751560363636-=， 601545363636-=，451530363636-=，301515363636-=， 即146与334的最大公约数为1536． 801565363636-=，651550363636-=，501535363636-=， 351520363636-=，20155363636-=，155********-=，1055363636-=． 综上所述，146、334、229的最大公约数是536．。