1．3算法案例1．3.1辗转相除法与更相减损术理解辗转相除法与更相减损术的含义和运算．1．我们求最大公约数的方法就是辗转相除法，也叫欧几里得算法，它是由欧几里得在公元前300年左右首先提出的．利用辗转相除法求最大公约数的步骤如下：第一步，用较大的数m除以较小的数n得到一个商q0和一个余数r0.第二步，若r0＝0，则n为m，n的最大公约数；若r0≠0，则用除数n除以余数r0得到一个商q1和一个余数r1.第三步，若r1＝0，则r0为m，n的最大公约数；若r1≠0，则用除数r0除以余数r1得到一个商q2和一个余数r2.……依次计算直至rn＝0，此时所得到的rn－1即为所求的最大公约数．例如：12与18的最大公约数为多少？解析：18＝12×1＋6；12＝6×2；所以12与18的最大公约数6.2．更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之．翻译成现代语言为：第一步，任意给定两个正整数，判断它们是否都是偶数．若是，用2约简；若不是，执行第二步．第二步，以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数．继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数．3．语句“r＝mMODn”表示m除以n余数为r，则：“14MOD3”等于________．答案:211．下列各组关于最大公约数的说法中不正确的是(C)A．16和12的最大公约数是4B．78和36的最大公约数是6C．85和340的最大公约数是17D．105和315的最大公约数是1052．在对16和12求最大公约数时，整个操作如下：(16，12)→(4，12)→(4，8)→(4，4)，由此可以看出12和16的最大公约数是(A)A．4B．12C．16D．83．今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何(B)A．2323B．23C．46D．694．284和1024的最小公倍数是(C)A．1024B．142C．72704D．5681．用辗转相除法求得168与486的最大公约数(C)A．3B．4C．6D．162．阅读下面语句：a＝70b＝83c＝92d＝88e＝82PRINT“p＝”；(a＋b＋c＋d＋e)/5END赋值语句表示的结果为________．答案:p＝833．(2015·全国Ⅱ卷)右边程序框图的算法思路源于我国古代数学名著《九章算术》中的“更相减损术”，执行该程序框图，若输入a，b分别为14，18，则输出的a＝()2A．0B．2C．4D．14解析：程序在执行过程中，a，b的值依次为a＝14，b＝18；b＝4；a＝10；a＝6；a＝2；b＝2，此时a＝b＝2程序结束，输出a的值为2，故选B.答案：B4．阅读下面语句：i＝1S＝0DOS＝S＋1/ii＝i＋1LOOPUNTILi>＝4PRINTSEND语句计算结果为________．答案:5．下列所画程序框图是已知直角三角形两条直角边a，b，求斜边的算法，其中正确的是(A)6．阅读下列语句，i＝1S＝0WHILEi<3S＝S＋1/(2*i＋1)i＝i＋1WENDPRINTS3END语句计算结果为________．答案：7．用辗转相除法求得78和36的最大公约数是(B)A．3B．6C．9D．128．利用辗转相除法求3869与6497的最大公约数与最小公倍数．解析：6497＝3869×1＋2628，3869＝2628×1＋1241，2628＝1241×2＋146，1241＝146×8＋73，146＝73×2＋0，所以3869与6497的最大公约数为73.最小公倍数为3869×6497/73＝344341.9．用辗转相除法或者更相减损术求三个数324，243，135的最大公约数．解析：324－243＝81，243－81＝162，162－81＝81；135－81＝54，81－54＝27，54－27＝27.故324，243，135最大公约数是27.1．求最大公约数的方法要熟练使用，但一般不要求会编写相应的程序．2．三个数的最大公约数求法一般是只求第一与第二个数的最大公约数，然后求这个最4大公约数与第三个数的最大公约数．5
