1、 13 算 法 案 例 1用两数中的数减去的数，再用构成新的一对数，再用减，以同样的操作一直做下去，直到所得的两数相等为止，这个数就是这两个数的最大公约数这个方法称作“更相减损术”，用它编写的算法称作“等值算法”较大较小所得差和较小数大数小数 2古希腊求两个正整数的最大公约数的方法是：用除以所得的和构成新的一对数，继续做上面的除法，直到大数被小数除尽，这个较小的数就是最大公约数据此编写的算法，也称作“欧几里得算法”辗转相除法较大数较小数余数较小数 3对于正整数m与n(mn)，总能找到整数q和r(0rn)，用m除以n，若商为q1，余数为r1(0r1n)，则mnq1r1，显然若x是m和n的公约数，
2、即x能整除m和n，则x也必然能整除r1，这样x也是n和r1的公约数，故求m和n的公约数就是求n和r1的公约数；同理，用n除以r1，得nr1q2r2(0r2nr1r2，所以到某一步必然有riri1qi2，即ri恰能被ri1整除，这时ri1是ri和ri1的最大公约数，它也必然是ri1和ri、ri2和ri1、r1与r2、n和r2、m和n的最大公约数(2)辗转相除法的算法分析：由以上辗转相除法的原理可以发现，辗转相除法的基本步骤是用较大的数除以较小的数，考虑到算法中的赋值语句可以对同一变量多次赋值，我们可以把较大的数用变量m表示，把较小的数用变量n表示，这样式子mnqr(0rb时，将ab赋给a，bb，
3、当ab时，aa，将ba赋给b然后再进行比较，依次类推用循环结构实现(2)更相减损术求最大公约数的程序设计如下：请自行将其直到型循环结构算法写出来 3辗转相除法与更相减损术有着相同的算法依据，但要注意运算过程的差别，辗转相除法的上一次运算的除数和余数分别作为下一次运算的被除数和除数，其结果直至余数为零得出更相减损术在上一次运算结束后，比较减数和差的大小，将大的作为下一次运算的被减数，小的作为减数，直至出现相等数时得到结果 由此可见，二者算法是相似的主要区别在于，辗转相除法进行的是除法运算，即辗转相除，更相减损术进行的是减法运算，即辗转相减，但其实质都是一个不断的递归过程另外两者在算法设计上有一个
4、重要的区别点，辗转相除法，下一次进行相除时，由上一次的除数和余数直接相除即可而更相减损术下一次相减前必须有一个判断大小的过程，以区别谁做被减数这些内容都是应特别注意的关键环节 4用更相减损术求两正整数的最大公约数时，若两数为偶数，可先约去2，这时莫忘记求得的相等两数乘以约简的数才是所求最大公约数 一、填空题 1在对16和12求最大公约数时，整个操作如下：(16,12)(4,12)(4,8)(4,4)，由此可 以 看 出 12 和 16 的 最 大 公 约 数 是_ 答案 4 21443与999的最大公约数是_ 答案 111 解析 (999,1443)(999,444)(555,444)(111
5、,444)(111,333)(111,222)(111,111)或1443999444,999444555,555444 111,444 111 333,333 111 222,222111111.自己用辗转相除法写出解答过程 3运算速度快是计算机一个很重要的特点，而 算 法 好 坏 的 一 个 重 要 标 志 是_ 答案 运算次数 42004与4509的最大公约数为_ 答案 501 解析 450933167，2004与4509的最大公约数为3167501.自己用辗转相除法和更相减损术写出解答 二、解答题 5写出从键盘任意输入两个正整数a，b，输出这两个数的最小公倍数的算法，画出程序框图，写出算法语句解析 从键盘输入两数 a，b 后，先求两数的最大公约数 k，再计算两数的最小公倍数 pabk，输出 p 即可程序框图如右图程序为：INPUT“正整数 a，b”；a，b pa*bIF ab THEN ta ab btEND IFDO ra MOD b ab br LOOP UNTIL r0 pp/a PRINT“m、n的最小公倍数为”；p END.
