算法案例1---辗转相除法和更相减损术-8.docVIP

PAGE PAGE 5 1.3 算法案例 1.3 算法案例——案例1 辗转相除法与更相减损术8 **学习目标** 1．理解辗转相除法与更相减损术求最大公约数的方法。 2．把辗转相除法与更相减损术的方法转换成程序框图与程序语言． **要点精讲** 1．辗转相除法 例如，求两个正数8251和6105的最大公约数。 分析与解：8251与6105两数都比较大，而且没有明显的公约数，可以考虑用两数中较大的数除以较小的数，求得商和余数： 8251＝6105×1＋2146 显然8251与6105的公约数也必是2146的约数，同样6105与2146的公约数也必是8251的约数，所以8251与6105的最大公约数也是6105与2146的最大公约数。 6105＝2146×2＋1813， 2146＝1813×1＋333， 1813＝333×5＋148 333＝148×2＋37， 148＝37×4＋0 则37为37与148的最大公约数，也是148与333的最大公约数，也是333与1813的最大公约数，也是1813与2146的最大公约数，也是2146与6105的最大公约数。 所以，2146与6105的最大公约数是37。 以上我们求最大公约数的方法就是辗转相除法。也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的。 2．更相减损术 我国早期也有解决求最大公约数问题的算法，就是更相减损术。在《九章算术》中记载了更相减损术求最大公约数的步骤：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。 翻译为： （1）任意给出两个正数；判断它们是否都是偶数。若是，用2约简；若不是，执行第二步。 （2）以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数。 **范例分析** 例1．试分别用辗转相除法和更相减损术求840与1764、440与556的最大公约数。 例2．给定两个正整数， （1）用辗转相除法编一个计算机程序，求与的最大公约数； （2）用更相减损术编一个计算机程序，求与的最大公约数。 例3．（1）用辗转相除法或者更相减损术求三个数 324 , 243 , 135 的最大公约数。 （2）输入3个数，输出其中最大的公约数，编程序完成上述功能。 例4．（1）我国《算经十书》之一《孙子算经》中有这样一个问题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？答曰：二十三.”你能用程序解决这个问题吗？ （1）第（1）小题的答案是不唯一的，你能用程序求出1000以内满足条件的数吗？ **规律总结** 1．在辗转相除法中，余数在有限次减小后，总可以达到；在更相减损术中，由于每一步得到的减数及差是正数，且它们的值在逐渐减小，所以经过有限步后，总会出现减数与差相等的情况。 2．辗转相除法与更相减损术的区别： （1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。 （2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0得到，而更相减损术则以减数与差相等而得到。 3．辗转相除法与更相减损术的联系：二者算理相似，都是在运算过程中两数的最大公约数保持不变，在有限步内将两书逐渐变小，直至找到两数的最大公约数为止。 4．最大公约数的应用：例如，长、宽、高分别为24cm,40cm,56cm的长方体能够分解成多少个棱长最大的正方体？答：24，40，56的最大公约数为8，故能够分解成个棱长最大的正方体。 **基础训练** 一、选择题 1．已知7163＝209×34+57，209＝57×3+38，57＝38×l+19，38＝19×2。根据上述系列等式，确定7163和209的最小公约数是( )． A．57 　　　 B．3 　　　　 C．19 　　　　　 D．34 2．840和1764的最大公约数是（ ） A．84 B. 12 C. 168 D. 252 3．7x+3y＝46的正整数解有( )组． A．0 　　　　　B．1 　　　　 C．2 　　　　 D．3 4．三个数36，60，84的最大公约数和最小公倍数分别是( ) A．12，15120 　　　B．12，1260 　　 C．6，1260 　　 D． 5．下左程序运行后输出的结果为( ) A. 50 B. 5 C. 25 D. 0 INPUT “ INPUT “m,n=”;m,n r=