高中数学 （1.3 算法案例）示范教案 新人教A版必修3.doc

1161.3算法案例整体设计教学分析在学生学习了算法的初步知识理解了表示算法的算法步骤、程序框图和程序三种不同方式以后再结合典型算法案例让学生经历设计算法解决问题的全过程体验算法在解决问题中的重要作用体会算法的基本思想提高逻辑思维能力发展有条理地思考与数学表达能力.三维目标1．理解算法案例的算法步骤和程序框图.2．引导学生得出自己设计的算法程序.3.体会算法的基本思想提高逻辑思维能力发展有条理地思考与数学表达能力.重点难点教学重点：引导学生得出自己设计的算法步骤、程序框图和算法程序.教学难点：体会算法的基本思想提高逻辑思维能力发展有条理地思考与数学表达能力.课时安排3课时教学过程第1课时案例1辗转相除法与更相减损术导入新课思路1（情境导入）大家喜欢打乒乓球吧由于东、西方文化及身体条件的不同西方人喜欢横握拍打球东方人喜欢直握拍打球对于同一个问题东、西方人处理问题方式是有所不同的.在小学我们学过求两个正整数的最大公约数的方法：先用两个数公有的质因数连续去除一直除到所得的商是互质数为止然后把所有的除数连乘起来.当两个数公有的质因数较大时（如8251与6105）使用上述方法求最大公约数就比较困难.下面我们介绍两种不同的算法——辗转相除法与更相减损术由此可以体会东、西方文化的差异.思路2（直接导入）前面我们学习了算法步骤、程序框图和算法语句.今天我们将通过辗转相除法与更相减损术来进一步体会算法的思想.推进新课新知探究提出问题（1）怎样用短除法求最大公约数？（2）怎样用穷举法（也叫枚举法）求最大公约数？（3）怎样用辗转相除法求最大公约数？（4）怎样用更相减损术求最大公约数？讨论结果：（1）短除法求两个正整数的最大公约数的步骤：先用两个数公有的质因数连续去除一直除到所得的商是两个互质数为止然后把所有的除数连乘起来.（2）穷举法（也叫枚举法）穷举法求两个正整数的最大公约数的解题步骤：从两个数中较小数开始由大到小列举直到找到公约数立即中断列举得到的公约数便是最大公约数.（3）辗转相除法辗转相除法求两个数的最大公约数其算法步骤可以描述如下：第一步给定两个正整数mn.第二步求余数r：计算m除以n将所得余数存放到变量r中.第三步更新被除数和余数：m=nn=r.第四步判断余数r是否为0.若余数为0则输出结果；否则转向第二步继续循环执行.如此循环直到得到结果为止.这种算法是由欧几里得在公元前300年左右首先提出的因而又叫欧几里得算法.（4）更相减损术我国早期也有解决求最大公约数问题的算法就是更相减损术.《九章算术》是中国古代的数学专著其中的“更相减损术”也可以用来求两个数的最大公约数即“可半者半之不可半者副置分母、子之数以少减多更相减损求其等也.以等数约之.”翻译为现代语言如下：第一步任意给定两个正整数判断它们是否都是偶数若是用2约简；若不是执行第二步.第二步以较大的数减去较小的数接着把所得的差与较小的数比较并以大数减小数继续这个操作直到所得的数相等为止则这个数（等数）或这个数与约简的数的乘积就是所求的最大公约数.应用示例例1用辗转相除法求8251与6105的最大公约数写出算法分析画出程序框图写出算法程序.解：用两数中较大的数除以较小的数求得商和余数：8251=6105×1+2146.由此可得6105与2146的公约数也是8251与6105的公约数反过来8251与6105的公约数也是6105与2146的公约数所以它们的最大公约数相等.对6105与2146重复上述步骤：6105=2146×2+1813.同理2146与1813的最大公约数也是6105与2146的最大公约数.继续重复上述步骤：2146=1813×1+3331813=333×5+148333=148×2+37148=37×4.最后的除数37是148和37的最大公约数也就是8251与6105的最大公约数.这就是辗转相除法.由除法的性质可以知道对于任意两个正整数上述除法步骤总可以在有限步之后完成从而总可以用辗转相除法求出两个正整数的最大公约数.算法分析：从上面的例子可以看出辗转相除法中包含重复操作的步骤因此可以用循环结构来构造算法.算法步骤如下：第一步给定两个正整数mn.第二步计算m除以n所得的余数为r.第三步m=nn=r.第四步若r=0则mn的最大公约数等于m；否则返回第二步.程序框图如下图：程序：INPUTmnDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND点评：从教学实践看有些学生不能理解算法中的转化过程例如：