《算法案例》教案1（4课时）

约4160字。

　　第一课时   1.3.1   算法案例---辗转相除法与更相减损术
　　教学要求：理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析；  基本能根据算法语句与程序框图的知识设计出辗转相除法与更相减损术完整的程序框图并写出它们的算法程序.
　　教学重点：理解辗转相除法与更相减损术求最大公约数的方法.
　　教学难点：把辗转相除法与更相减损术的方法转换成程序框图与程序语言.
　　教学过程：
　　一、复习准备：
　　1. 回顾算法的三种表述：自然语言、程序框图（三种逻辑结构）、程序语言（五种基本语句）.
　　2. 提问：①小学学过的求两个数最大公约数的方法？（先用两个公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来.）口算出36和64的最大公约数. ②除了用这种方法外还有没有其它方法？ ， 和28的最大公约数就是64和36的最大公约数，反复进行这个步骤，直至 ，得出4即是36和64的最大公约数.
　　二、讲授新课：
　　1. 教学辗转相除法：
　　例1：求两个正数1424和801的最大公约数.
　　分析：可以利用除法将大数化小，然后逐步找出两数的最大公约数. （适用于两数较大时）
　　①以上我们求最大公约数的方法就是辗转相除法，也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的. 利用辗转相除法求最大公约数的步骤如下：
　　（1）用较大的数m除以较小的数n得到一个商 和一个余数 ；（2）若 ＝0，则n为m，n的最大公约数；若 ≠0，则用除数n除以余数 得到一个商 和一个余数 ；（3）若 ＝0，则 为m，n的最大公约数；若 ≠0，则用除数 除以余数 得到一个商 和一个余数 ；……依次计算直至 ＝0，此时所得到的 即为所求的最大公约数.
　　②由上述步骤可以看出，辗转相除法中的除法是一个反复执行的步骤，且执行次数由余数是否等于0来决定，所以我们可以把它看成一个循环体，它的程序框图如右图：（师生共析，写出辗转相除法完整的程序框图和程序语言）
　　练习：求两个正数8251和2146的最大公约数. （乘法格式、除法格式）
　　2. 教学更相减损术：
　　我国早期也有求最大公约数问题的算法，就是更相减损术. 在《九章算术》中有更相减损术求最大公约数的步骤：可半者半之，不可半者，副置分母•子之数，以少减多，更相减损，求其等也，以等数约之.