高中数学必修3：第12课时5.4.2算法案例二(最大公约数).doc.doc

第12课时5.4 算法案例 重点难点 重点：通过案例分析理解辗转相除法与更相减损术求最大公约数的方法，体会算法思想. 难点：把辗转相除法与更相减损术的方法转换成程序框图与程序语言. 学习要求 1．理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析. 2．基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序. 【课堂互动】 问题： 写出求两个正整数a,b(ab)的最大公约数的一个算法。 1.辗转相除法 公元前3世纪，欧几里得介绍了求两个正整数a,b(ab)的最大公约数的方法，求出一列数：，这列数从第三项开始，每一项都是前两项相除所得的余数（即），余数等于0的前一项，即是a和b的最大公约数，这种方法称为“欧几里得辗转相除法”。 例1 求两个正数8 251和6 105的最大公约数． （分析：8 251与6 105两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根据已有的知识即可求出最大公约数） 【解】8 251＝6 105×1＋2 146 显然8 251和的2 146最大公约数也必是2 146的约数，同样6 105与2 146的公约数也必是8 251的约数，所以8 251与6 105的最大公约数也是6 105与2 146的最大公约数． 6 105＝2146×2＋1813 2 146＝1813×1＋333 1 813＝333×5＋148 333＝148×2＋37 148＝37×4＋0 则37为8 251与6 105的最大公约数． 【小结】以上我们求最大公约数的方法就是欧几里得辗转相除法．其求最大公约数的步骤如下： 第一步：用较大的数除以较小的数,得到一个商和一个余数； 第二步：若，则为的最大公约数；若，则用除数除以余数,得到一个商和一个余数； 第三步：若，则为的最大公约数；若，则用除数除以余数得到一个商和一个余数； …… 依次计算直至，此时所得到的即为所求的最大公约数. 【练习】求a=204，b=85的最大公约数，步骤为： S1 204÷85的余数为34， S2 85÷34的余数为17， S3 34÷17的余数为0。 所以它们的最大公约数为17。 算法描述：计算出a÷b的余数r，若r=0，则b为a，b的最大公约数；若r≠0，则把前面的除数b作为新的被除数，把余数r作为新的除数（a，b要重新赋值，a←b，b←r），继续进行上述运算，直到余数为0(用While循环语句，循环的执行条件是r≠0，当r=0时，循环终止)，此时的除数即为所求的最大公约数。 算法如下: S1 输入两个正整数a,b(ab)； 开始b←rYN结束输入a，ba←b 开始 b←r Y N 结束 输入a，b a←b r←Mod(a,b) Mod(a,b) ≠0 输出b S3 输出最大公约数b. 【流程图】 【伪代码】 Read a,b Read a,b While Mod(a,b)≠0 r←Mod(a,b) a←b b←r End While Print b 2. 更相减损法 我国早期也有解决求最大公约数问题的算法，就是更相减损术． 更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母之数，以少减多，更相减损，求其等也，以等数约之． 翻译出来为： 第一步：任意给出两个正数,判断它们是否都是偶数．若是，用2约简；若不是，执行第二步． 第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数．继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数． 再从这个角度看一下“求a=204，b=85的最大公约数”的问题，S1步可以等价为等式：。S2步可以等价为等式：。这两步从减法的角度可以理解为：204-85，所得的差与减式中的较小数比较，再用大的数减小的数，循环执行以上步骤,直到结果为0。此时减数就是a和b的最大公约数。这一算法根据它的特点，也可以用循环语句完成。 参考代码： /a放较大的数，b放较小的数 If a b Then m ← a a ← b b ← m /交换a，b中的数 End If /确保a是a，b中较大的数 r ← a – b /两数相减 While r ≠ 0 If b r Then a ← b b ← r Else a ← r End If r ← a – b /确保相减后仍用较大的数减去较小的数 End While Print b 用“更相减损法”求多于两个数的最大公约数就可以显示出其优越性 【小结】比较辗转相除法与更相减损术的区别 （1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上