高中数学 算法案例 （1）教案 新人教A版必修3VIP免费

算法案例教学目标：(1)理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析；(2)基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序；（3）进一步体会算法的基本思想；教学重点：理解辗转相除法与更相减损术求最大公约数的方法。教学难点：把辗转相除法与更相减损术的方法转换成程序框图与程序语言。.教学用具：投影仪教学方法：启发式教学教学过程：一、新课导入：提出问题：在小学，我们已经学过求最大公约数的知识，如口算求出12与20的公约数。其方法为：先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来。我们都是利用找公约数的方法来求最大公约数，如果公约数比较大而且根据我们的观察又不能得到一些公约数，我们又应该怎样求它们的最大公约数？比如求8251与6105的最大公约数？这就是我们这一堂课所要探讨的内容。二、讲授新课：1．辗转相除法例1求两个正数8251和6105的最大公约数。分析：8251与6105两数都比较大，而且没有明显的公约数，我们可以考虑用两数中较大的数除以较小的数，求得商和余数：8251＝6105×1＋2146显然6105与2146的公约数也必是8251与6105的公约数，反过来，8251与6105的最大公约数也是6105与2146的最大公约数，所以它们的最大公约数相等。6105＝2146×2＋18132146＝1813×1＋3331813＝333×5＋148333＝148×2＋37148＝37×4＋0最后的除数37是148和37的最大公约数，也就是8251与6105的最大公约数。以上我们求最大公约数的方法就是辗转相除法。也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的。利用辗转相除法求最大公约数的步骤如下：（1）.用较大的数m除以较小的数n得到一个商和一个余数；（2）.若＝0，则n为m，n的最大公约数；若≠0，则用除数n除以余数得到一个商和一个余数；（3）.若＝0，则为m，n的最大公约数；若≠0，则用除数除以余数得到一个商和一个余数；……依次计算直至＝0，此时所得到的即为所求的最大公约数。思考:你能把辗转相除法编成一个计算机程序吗?例如,把上面的例子为例.算法步骤:第一步，给定两个正整数m,n；第二步，计算m除以n所得的余数r;1第三步，m=n,n=r.第四步，若r=0，则m,n的最大公约数等于m；否则，返回第二步。程序框图：否是程序：2．更相减损术我国早期也有求最大公约数问题的算法，就是更相减损术。在《九章算术》中有更相减损术求最大公约数的步骤：可半者半之，不可半者，副置分母•子之数，以少减多，更相减损，求其等也，以等数约之。翻译为：（1）.任意给定两个正数,判断它们是否都是偶数。若是，用2约简；若不是，执行第二步。（2）.以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。继续这个操作，直到所得的数相等为止，则这个数（等数）或这个数与约简的数的乘积就是所求的最大公约数。2输入m,nm=nn=rr=0？输出m开始结束求m除以n的余数rINPUTm,nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND例2用更相减损术求98与63的最大公约数.分析：（略）辗转相除法与更相减损术的区别：（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到三．巩固练习：1．试用当型循环结构构造算法，求两个正整数的最大公约数；写出算法步骤、程序框图和程序。2．P45练习1四．小结：对比分析辗转相除法与更相减损术求最大公约数的计算方法及完整算法程序。3