1、算法案例编稿：丁会敏 审稿：王静伟【学习目标】1.理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析；2.基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序；3.了解秦九韶算法的计算过程，并理解利用秦九韶算法可以减少计算次数提高计算效率的实质；4.了解各种进位制与十进制之间转换的规律，会利用各种进位制与十进制之间的联系进行各种进位制之间的转换.【要点梳理】要点一、辗转相除法也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的.利用辗转相除法求最大公约数的步骤如下：第一步：用较大的数m除以较小的数n得到一个商q0和一个余数r0；第二步：若r0=0，
2、则n为m，n的最大公约数；若r00，则用除数n除以余数r0得到一个商q1和一个余数r1；第三步：若r1=0，则r0为m，n的最大公约数；若r10，则用除数r0除以余数r1得到一个商q2和一个余数r2；依次计算直至rn=0，此时所得到的rn1即为所求的最大公约数.用辗转相除法求最大公约数的程序框图为：程序：INPUT “m=”;mINPUT “n=”;nIF mn THEN x=mm=n n=xEND IFr=m MOD nWHILE r0 r=m MOD n m=nn=rWENDPRINT nEND要点诠释：辗转相除法的基本步骤是用较大的数除以较小的数，考虑到算法中的赋值语句可以对同一变量多次
3、赋值，我们可以把较大的数用变量m表示，把较小的数用变量n表示，这样式子就是一个反复执行的步骤，因此可以用循环结构实现算法.要点二、更相减损术我国早期也有解决求最大公约数问题的算法，就是更相减损术.更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也.以等数约之.翻译出来为：第一步：任意给出两个正整数；判断它们是否都是偶数.若是，用2约简；若不是，执行第二步.第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数.继续这个操作，直到所得的数相等为止，则这个数(等数)就是所求的最大公约数.理论依据：由，得与有相同的公约数更相减
4、损术一般算法：第一步，输入两个正整数；第二步，如果，则执行，否则转到；第三步，将的值赋予；第四步，若，则把赋予，把赋予，否则把赋予，重新执行；第五步，输出最大公约数.程序:INPUT “a=”，aINPUT “b=”，bWHILE ab IF a=ba=a-b;ELSE b=b-aWENDENDPRINT b或者INPUT “请输入两个不相等的正整数”；a，bi=0WHILE a MOD 2=0 AND b MOD 2=0a=a/2b=b/2i=i+1WENDDOIF ba THENt=aa=bb=tEND IFc=aba=bb=cLOOP UNTIL a=bPRINT aiEND要点诠释：用
5、辗转相除法步骤较少，而更相减损术虽然有些步骤较长，但运算简单.要点三、秦九韶计算多项式的方法令，则有，其中.这样，我们便可由依次求出；要点诠释：显然，用秦九韶算法求n次多项式的值时只需要做n次乘法和n次加法运算要点四、进位制进位制是一种记数方式，用有限的数字在不同的位置表示不同的数值.可使用数字符号的个数称为基数，基数为n，即可称n进位制，简称n进制.现在最常用的是十进制，通常使用10个阿拉伯数字0-9进行记数.对于任何一个数，我们可以用不同的进位制来表示.比如：十进数57，可以用二进制表示为111001，也可以用八进制表示为71、用十六进制表示为39，它们所代表的数值都是一样的.表示各种进位
6、制数一般在数字右下角加注来表示,如111001(2)表示二进制数,34(5)表示5进制数.1.k进制转换为十进制的方法：，把k进制数a转化为十进制数b的算法程序为：INPUT “ a,k,n=”;a,k,ni=1b=0WHILE i=n t=GET ai b=b+t*k(i-1) i=i+1WENDPRINT bEND2.十进制转化为k进制数b的步骤为：第一步，将给定的十进制整数除以基数k，余数便是等值的k进制的最低位；第二步，将上一步的商再除以基数k，余数便是等值的k进制数的次低位；第三步，重复第二步，直到最后所得的商等于0为止，各次所得的余数，便是k进制各位的数，最后一次余数是最高位，即除
7、k取余法.要点诠释：1、在k进制中，具有k个数字符号.如二进制有0，1两个数字.2、在k进制中，由低位向高位是按“逢k进一”的规则进行计数.3、非k进制数之间的转化一般应先转化成十进制，再将这个十进制数转化为另一种进制的数，有的也可以相互转化.【典型例题】类型一：辗转相除法与更相减损术例1分别用辗转相除法和更相减损术求378与90的最大公约数【答案】18 【解析】 用辗转相除法： 378=904+18，90=185 378与90的最大公约数是18 用更相减损术： 378与90都是偶数， 用2约分后得189和45 18945=144，14445=99，9945=54，5445=9，459=36，
8、369=27，279=18，189=9 378与90的最大公约数为29=18【总结升华】比较辗转相除法与更相减损术的区别(1)都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显；(2)从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到.由该题可以看出，辗转相除法得最大公约数的步骤较少.对比两种方法控制好算法的结束，辗转相除法是到达余数为0，更相减损术是到达减数和差相等.举一反三： 【变式1】（1）用更相减损术求两个正数84与72的最大公约数
9、 （2）利用辗转相除法求3869与6497的最大公约数与最小公倍数【解析】 （1） 因为84=214，72=184， 所以2118=3， 183=15， 153=12， 123=9， 93=6， 63=3 所以21和18的最大公约数等于3 所以84和72的最大公约数等于12 【总结升华】先约简，再求21与18的最大公约数，然后乘以约简的4得84与72的最大公约数 （2）6497=38691+2628， 3869=26281+1241， 2628=12412+146， 1241=1468+73， 146=732+0 所以3 869与6 497的最大公约数为73， 最小公倍数为3 86964977
10、3=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=446+0， 6为264与6的最大公约数，也是这三个数的最大公约数【总结升华】 求最大公约数通常有两种方法：一是辗转相除法；二是更相减损术，对
11、于3个数的最大公约数的求法，则是先求其中两个数的最大公约数m，再求m与第三个数的最大公约数同样可推广到求3个以上数的最大公约数 举一反三：【变式1】求三个数324，243，135的最大公约数【答案】27【解析】324=2431+81， 243=813+0， 324与243的最大公约数为81 又135=811+54， 81=541+27， 54=272+0， 81与135的最大公约数为27 三个数324，243，135的最大公约数为27 更相减损术： 324243=81， 24381=162， 16281=81， 81是324和243的最大公约数 又13581=54， 8154=27， 5427
12、=27， 27是81与135的最大公约数 三个数324，243，135的最大公约数为27 例3.甲、乙、丙三种溶液分别重、，现要将它们分别全部装入小瓶中，每个小瓶装入液体的质量相同，问每瓶最多装多少？【思路点拨】由题意，每个小瓶最多能装的溶液的质量应是三种溶液质量的最大公约数.【答案】【解析】先求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
13、.147，343，133的最大公约数是7.故每瓶最多装.【总结升华】本题关键是分析清楚题意，找出三个数的最大公约数.求三个以上(含三个数)的数的最大公约数时，可依次通过求两个数的最大公约数与第三个数的最大公约数来求得.类型二：秦九韶算法例4利用秦九韶算法求在x=0.2时的值写出详细计算过程【思路点拨】秦九韶算法是我国南宋的数学家秦九韶首先提出来的（1）特点：它通过一次式的反复计算，逐步计算高次多项式的求值问题，即将一个n次多项式的求值问题，归结为重复计算n个一次式即（2）具体方法如下：已知一个一元n次多项式0当x=x0，我们可按顺序一项一项地计算，然后相加，求得【答案】1.2214024 【解
14、析】 v0=0.00835， v1=v0x+0.04168=0.008350.2+0.04168=0.043 35， v2=v1x+0.16663=0.043350.2+0.16663=0.1753， v3=v2x+0.5=0.17530.2+0.5=0.53506， v4=v3x+1=0.535060.2+1=1.107012， v5=v4x+1=1.1070120.2+1=1.2214024 【总结升华】秦九韶算法的原理是 在运用秦九韶算法进行计算时，应注意每一步的运算结果，像这种一环扣一环的运算，如果错一步，则下一步，一直到最后一步就会全部算错同学们在计算这种题时应格外小心 举一反三：【
15、变式1】用秦九韶算法求多项式当x=2时的值【答案】1397【解析】 v0=8， v1=82+5=21， v2=212 4-0=42， v3=422 4-3=87， v4=872+0=174， v5=1742+0=348， v6=3482+2=698， v7=6982+1=1397， 所以，当x=2时，多项式的值为1397【变式2】用秦九韶算法计算多项式在x=0.4时的值时，需做加法和乘法的次数和是（ ） A10 B9 C12 D8 【答案】 C 【解析】 加法6次，乘法6次， 6+6=12（次），故选C类型三：进位制例5（1）试把十进制数136转化为二进制数；（2）试把十进制数1 234转化为
16、七进制数【答案】（1）10001000 【解析】 （1）由于136=268+0， 68=234+0 34=217+0 17=28+1 8=24+0 4=22+0 2=21+0 1=20+1 所以136=10001000（2） （2）1234=7176+2， 176=725+1 25=73+4 3=70+3 所以1234=3412（7） 【总结升华】（1）应注意搞清每一次除法中的被除数、除数，当商为零时停止除法，把每步所得的余数倒着排成一个数，就是相应的二进制数（2）十进制数转化为七进制数与转化为二进制数的方法类似，要认真体会其原理举一反三： 【变式1】（1）把十进制数89转化为二进制数； （2
17、）将十进制数2l转化为五进制数【解析】（1）用除2取余法： 89=2(2(2(2(2(2(20+1)+0)+1)+1)+0)+0)+1=2(2(2(22(220+2+0)+1)+1)+0)+0)+1 =126+025+124+123+022021+120=1011001(2)（2）用除5取余法，可得 21=41（5）例6把210121l（3）转化为八进制数 【答案】3326（8） 【解析】 先将三进制数转化为十进制数，再将十进制数转化为八进制数 2101211（3） =236+135+133+232+131+130 =1458+243+27+18+3+1 =1750 1750=8218+6 2
18、18=827+2 27=83+3 1750=8218+6 =8（827+2）+6 =8（8（83+3）+2）+6 =8（382+38+2）+6 =383+382+28+6 =3326（8）， 2101211（3）=3326（8） 【总结升华】从本例的解答中，大家要有两个提高 第一，把三进制数转化为八进制数，十进制数起了桥梁和纽带的作用，具体体现是2101211（3）=1750=3326（8）第二，在把1750转化为3326（8）时，我们没有列竖式，大家要从中体会一下方法的内在规律举一反三： 【变式1】在十进制中，那么在五进制中数码2 004折合成十进制为（ ）A29 B254 C602 D2 004【答案】B解析：，故选B 【变式2】（1）将二进制数（2）转化成十进制数； （2）将七进制数235（7）转化成八进制数 【答案】（1）（2）174（8） 【解析】对于（1），按照形式anan1an2a1a0（2）=an2n+an12n1+a12+an计算即可；对于（2），先将七进制数转化成十进制数，再将所得十进数转化成八进制数（1）（2）235（7）=272+37+5=124，利用除8取余法得124=174（8），过程如图所示，所以235（7）转化成八制数为174（8）
