1、揭阳第三中学教案表 课题1.3 算法案例（1）课型新授课教学目标1理解算法案例的算法步骤和程序框图. 来源:Z。xx。k.Com2引导学生得出自己设计的算法程序.3. 体会算法的基本思想，提高逻辑思维能力，发展有条理地思考与数学表达能力.重点难点重点：引导学生得出自己设计的算法步骤、程序框图和算法程序.难点：体会算法的基本思想，提高逻辑思维能力，发展有条理地思考与数学表达能力.教具准备多媒体课件课时安排1课时教学过程与教学内容教学方法、教学手段与学法、学情一、情境导入 大家喜欢打乒乓球吧，由于东、西方文化及身体条件的不同，西方人喜欢横握拍打球，东方人喜欢直握拍打球，对于同一个问题，东、西方人处
2、理问题方式是有所不同的.在小学，我们学过求两个正整数的最大公约数的方法：先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来. 当两个数公有的质因数较大时（如8 251与6 105），使用上述方法求最大公约数就比较困难.下面我们介绍两种不同的算法辗转相除法与更相减损术,由此可以体会东、西方文化的差异.来源:学科网二、新知探究 提出问题（1）怎样用短除法求最大公约数？（2）怎样用穷举法（也叫枚举法）求最大公约数？（3）怎样用辗转相除法求最大公约数？（4）怎样用更相减损术求最大公约数？讨论结果：（1）短除法 求两个正整数的最大公约数的步骤：先用两个数公有的质因数连
3、续去除，一直除到所得的商是两个互质数为止，然后把所有的除数连乘起来.（2）穷举法（也叫枚举法） 穷举法求两个正整数的最大公约数的解题步骤：从两个数中较小数开始由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数.（3）辗转相除法 辗转相除法求两个数的最大公约数，其算法步骤可以描述如下： 第一步，给定两个正整数m，n. 第二步，求余数r：计算m除以n，将所得余数存放到变量r中. 第三步，更新被除数和余数：m=n，n=r. 第四步，判断余数r是否为0.若余数为0，则输出结果；否则转向第二步继续循环执行. 如此循环，直到得到结果为止. 这种算法是由欧几里得在公元前300年左右首先提出
4、的，因而又叫欧几里得算法.（4）更相减损术 我国早期也有解决求最大公约数问题的算法，就是更相减损术. 九章算术是中国古代的数学专著，其中的“更相减损术”也可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也.以等数约之.”翻译为现代语言如下： 第一步，任意给定两个正整数，判断它们是否都是偶数，若是，用2约简；若不是，执行第二步. 第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数相等为止，则这个数（等数）或这个数与约简的数的乘积就是所求的最大公约数.应用示例例1 用辗转相除法求8 251与6
5、 105的最大公约数,写出算法分析，画出程序框图，写出算法程序.解：用两数中较大的数除以较小的数，求得商和余数：8 251=6 1051+2 146.由此可得，6 105与2 146的公约数也是8 251与6 105的公约数，反过来，8 251与6 105的公约数也是6 105与2 146的公约数，所以它们的最大公约数相等.对6 105与2 146重复上述步骤：6 105=2 1462+1 813.同理，2 146与1 813的最大公约数也是6 105与2 146的最大公约数.继续重复上述步骤：2 146=1 8131+333，1 813=3335+148，333=1482+37，148=37
6、4. 最后的除数37是148和37的最大公约数，也就是8 251与6 105的最大公约数. 这就是辗转相除法.由除法的性质可以知道，对于任意两个正整数，上述除法步骤总可以在有限步之后完成，从而总可以用辗转相除法求出两个正整数的最大公约数.算法分析：从上面的例子可以看出，辗转相除法中包含重复操作的步骤，因此可以用循环结构来构造算法.算法步骤如下：第一步，给定两个正整数m，n.第二步，计算m除以n所得的余数为r.第三步，m=n，n=r.第四步，若r=0，则m，n的最大公约数等于m；否则，返回第二步.程序框图如右图：程序：INPUT m,nDO r=m MOD n m=n n=rLOOP UNTIL
7、 r=0PRINT mEND点评：从教学实践看，有些学生不能理解算法中的转化过程，例如：求8 251与6 105的最大公约数,为什么可以转化为求6 105与2 146的公约数.因为8 251=6 1051+2 146，可以化为8 251-6 1051=2 164，所以公约数能够整除等式两边的数，即6 105与2 146的公约数也是8 251与6 105的公约数.变式训练 你能用当型循环结构构造算法，求两个正整数的最大公约数吗？试画出程序框图和程序.解：当型循环结构的程序框图如下图：程序：INPUT m，nr=1WHILE r0 r=m MOD n m=n n=rWENDPRINT mEND例2
8、 用更相减损术求98与63的最大公约数.解：由于63不是偶数，把98和63以大数减小数，并辗转相减，如下图所示.98-63=3563-35=2835-28=728-7=2121-7=1414-7=7所以，98和63的最大公约数等于7.点评：更相减损术与辗转相除法的比较：尽管两种算法分别来源于东、西方古代数学名著，但是二者的算理却是相似的，有异曲同工之妙主要区别在于辗转相除法进行的是除法运算，即辗转相除；而更相减损术进行的是减法运算，即辗转相减，但是实质都是一个不断的递归过程变式训练 用辗转相除法或者更相减损术求三个数324,243,135的最大公约数.解：324=243181，243=8130
9、，则324与243的最大公约数为81.又135=81154，81=54127，54=2720，则 81 与 135的最大公约数为27.所以,三个数324、243、135的最大公约数为27.另法：324243=81,24381=162,16281=81，则324与243的最大公约数为81.13581=54,8154=27,5427=27，则81与135的最大公约数为27.所以，三个数324、243.135的最大公约数为27.例3 （1）用辗转相除法求123和48的最大公约数.（2）用更相减损术求80和36的最大公约数.解：（1）辗转相除法求最大公约数的过程如下：12324827，4812721，
10、271216，21363，623+0，最后6能被3整除，得123和48的最大公约数为3.（2）我们将80作为大数，36作为小数，因为80和36都是偶数，要除公因数2.802=40，362=18.40和18都是偶数，要除公因数2.402=20，182=9.下面来求20与9的最大公约数，209=11，119=2，92=7，72=5，52=3，32=1，21=1，可得80和36的最大公约数为221=4.点评：对比两种方法控制好算法的结束，辗转相除法是到达余数为0，更相减损术是到达减数和差相等.变式训练 分别用辗转相除法和更相减损术求1 734，816的最大公约数解：辗转相除法：1 734=8162+
11、102，816=1028（余0），来源:Zxxk.Com1 734与816的最大公约数是102更相减损术：因为两数皆为偶数，首先除以2得到867，408，再求867与408的最大公约数867-408=459，459-408=51，408-51=357，357-51=306，306-51=255，255-51=204，204-51=153，153-51=102，102-51=51.1 734与816的最大公约数是512=102利用更相减损术可另解：1 734816918，918816102，816102714，714102612，612102510，510102408，408102306，306
12、102204，204102102.1 734与816的最大公约数是102知能训练 求319，377，116的最大公约数解：377=3191+58，319=585+29，58=292.377与319的最大公约数为29，再求29与116的最大公约数116=294.29与116的最大公约数为29.377，319，116的最大公约数为29.三、课堂小结来源:学科网ZXXK（1）用辗转相除法求最大公约数.（2）用更相减损术求最大公约数.思想方法：递归思想.四、布置作业分别用辗转相除法和更相减损术求261，319的最大公约数.来源:Z。xx。k.Com板书1.3 算法案例（1）一、辗转相除法二、更相减损术教学反思
