1.3.1算法案例 辗转相除法与更相减损术 算法的历史背景 人类最早关于算法的记录是在两河流域发现的公元前两三千年的黏土板，其中一个典型的例子就是计算利息何时能够等于本金。在公元前2100年左右，美索不达米亚人已有了乘法表，其中使用着六十进位制的算法。 算法早期发展中值得一提的是公元前300年古希腊数学家欧几里得提出的欧几里得算法（辗转相除法），用来求两个正整数的最大公约数。 而算法也是中国古代数学的一大特色，《周髀算经》，《九章算术》，《算法启蒙》，《四元玉鉴》都表明我国对算法的研究及应用有着悠久的历史。 新知探究 问题：（1）你能说出30与18的公约数吗？ （2）如何求8251与6105的最大公约数？ 当两个数公有的质因数较大时，用原来的短除法显然困难，须改进算法，用什么方法好？ 关于辗转相除法的算理问题 以上满足： 所以 例1：用辗转相除法求8251与6105的最大公约数． 例题讲解 探究1：用辗转相除法求225和135的最大公约数 完整的过程 8251=6105×1+2146 6105=2146×2+1813 2146=1813×1+333 1813=333×5+148 333=148×2+37 148=37×4+0 显然37是148和37的最大公约数，也就是8251和6105的最大公约数 显然45是90和45的最大公约数，也就是225和135的最大公约数 探究2：用辗转相除法求98和196的最大公约数 225=135×1+90 135=90×1+45 90=45×2 第二步，计算m除以n所得的余数r . 第三步，m=n，n=r. 第四步，若r=0，则m，n的最大公约数等于m； 否则，返回第二步. 第一步，给定两个正整数m，n . 1. 设计算法之算法步骤 如何设计辗转相除法？ （1）确立循环体:求m除以n的余数 r, m=n, n=r （2）初始化变量：输入m, n （3）设定循环控制条件：r=0？ 2. 设计算法之 构造循环结构 求m除以n的余数r 开始 输入m，n m=n n=r r=0？ 是 输出m 结束 否 INPUT m，n DO m=n n=r LOOP UNTIL r =0 PRINT m END r =m MOD n 求m除以n的余数r 开始 输入m，n m=n n≠0？ 否 输出m 结束 是 n=r INPUT m，n WHILE n<>0 r =m MOD n m=n n=r WEND PRINT m END 问题提出：除了用上述算法求两个数的最大公约数之外还有没有别的算法？ 点拨：用“更相减损术”：更相减损术，是我国数学家刘徽的专著《九章算术》中记载的．更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母分子之数，以少减 多，更相减损，求其等也.，以等数约之． 翻译出来为： 第一步：任意给出两个正数；判断它们是否都是偶数．若是，用2约简；若不是，执行第二步． 第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数．继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数． 例2：用更相减损术求91与49的最大公约数，并用辗转相除法检验结果． 解法1：（更相减损术）由于49不是偶数，把91和49以大数减小数，并辗转相减， 即：91－49＝42 49－42＝7 42－7＝35 35－7＝28 28－7＝21 21－7＝14 14－7＝7 ∴91与49的最大公约数是7。 解法2（辗转相除法） 91＝49×1＋42 49＝42×1＋7 42＝7×6 ∴ 91与49的最大公约数是7。 名称 辗转相除法 更相减损术 区别 （1）以除法为主. （2）两个整数差值较大时运算次数较少. （3）相除余数为零时得结果. （1）以减法为主. （2）两个整数差值较大时 运算次数较多. （3）相减，两数相等得结果，相减前要做是否都是偶数的判断. 联系 （1）都是求最大公约数的方法. （2）二者的实质都是递推的过程. （3）二者都要用循环结构来实现. 小结 辗转相除法与更相减损术的比较: 作业：（1）必做题：用辗转相除法求下列两数的最大公约数，并用更相减损术检验你的结果：①228，48；② 185，98 （2）拓展延伸：请查阅相关书籍资料画出更相减损术这种算法的程序框图 ... ...
~~ 您好，已阅读到文档的结尾了 ~~
