辽宁省新宾满族自治县高级中学高中数学 §1.3 中国古代数学中的算法案例学案 新人教 A 版必修 3三维目标1．理解算法案例的算法步骤和程序框图.2．引导学生得出自己设计的算法程 序.3. 体会算法的基本思想，提高逻辑思维能力，发展有条理地思考与数学表达能力.重点难点教学重 点：引导学生得出自己设计的算法步骤、程序框图和算法程序.教学难点：体会算法的基本思想，提高逻辑思维能力，发展有条理地思考与数学表达能力.案例 1 辗转相除法 辗转相除法求两个数的最大公约数，其算法步骤可以描述如下： 第一步，给定两个正整数 m，n. 第二步，求余数 r：计算 m 除以 n，将所得余数存放到变量 r 中. 第三步，更新被除数和余数：m=n，n=r. 第四步，判断余数 r 是否为 0.若余数为 0，则输出结果；否则转向第二步继续循环执行.如此循环，直到得到结果为止. 这种算法是由欧几里得在公元前 300 年左右首先提出的，因而又叫欧几里得算法.案例 2 更相减损术 我国早期也有解决求最大公约数问题的算法，就是更相减损术. 《九章算术》是中国古代的数学专著，其中的“更相减损术”也可以用来求两个 数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也.以等数约之.”翻译为现代语言如下：第一步，任意给定两个正整数，判断它们是否都是偶数，若是，用 2 约简；若不是，执行第二步.第二步，以较大的 数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数相等为止，则这个数（等数）或这个数与约简的数的乘积就是所求的最大公约数.应用示例例 1 用辗转相除法求 28 8 与 123 的最大公约数例 2 用更相减损术求 98 与 63 的最大公约数点评：更相减损术与辗转相除法的比较：尽管两种算法分别来源于东、西方古代 数学名著，但是二者的算理却是相似的，有异曲同工之妙．主要区别在于辗转相除法进行的是除法运算，即辗转相除；而更相减损术进行的是减法运算，即辗转相减，但是实质都是一个不断的递归过程．拓展思考（选做）： 用辗转相除法或者更相减损术求三个数 324,243,135 的最大公约数. 例 3 （1）用辗转相除法求 12 3 和 48 的最大公约数.（2）用更相减损术求 80 和 36 的最大公约数. 点评：对比两种方法控制好算法的结束，辗转相除法是到达余数为 0，更相减损术是到达减数和差相等.案例 3 割圆术 阅读教材...
