1.3.1 算法案例---辗转相除法与更相减损术

《1.3.1 算法案例---辗转相除法与更相减损术》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第一课时1.3.1算法案例---辗转相除法与更相减损术教学要求：理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析；基本能根据算法语句与程序框图的知识设计出辗转相除法与更相减损术完整的程序框图并写出它们的算法程序.教学重点：理解辗转相除法与更相减损术求最大公约数的方法.教学难点：把辗转相除法与更相减损术的方法转换成程序框图与程序语言.教学过程：一、复习准备：1.回顾算法的三种表述：自然语言、程序框图（三种逻辑结构）、程序语言（五种基本语句）.2.提问：①小学学过的求两个数最大公约数

2、的方法？（先用两个公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来.）口算出36和64的最大公约数.②除了用这种方法外还有没有其它方法？，和28的最大公约数就是64和36的最大公约数，反复进行这个步骤，直至，得出4即是36和64的最大公约数.二、讲授新课：1.教学辗转相除法：例1：求两个正数1424和801的最大公约数.分析：可以利用除法将大数化小，然后逐步找出两数的最大公约数.（适用于两数较大时）①以上我们求最大公约数的方法就是辗转相除法，也叫欧几里德算法，它是由欧几里德在

3、公元前300年左右首先提出的.利用辗转相除法求最大公约数的步骤如下：（1）用较大的数m除以较小的数n得到一个商和一个余数；（2）若＝0，则n为m，n的最大公约数；若≠0，则用除数n除以余数得到一个商和一个余数；（3）若＝0，则为m，n的最大公约数；若≠0，则用除数除以余数得到一个商和一个余数；……依次计算直至＝0，此时所得到的即为所求的最大公约数.②由上述步骤可以看出，辗转相除法中的除法是一个反复执行的步骤，且执行次数由余数是否等于0来决定，所以我们可以把它看成一个循环体，它的程序框图如右图：（师生共析

4、，写出辗转相除法完整的程序框图和程序语言）练习：求两个正数8251和2146的最大公约数.（乘法格式、除法格式）2.教学更相减损术：我国早期也有求最大公约数问题的算法，就是更相减损术.在《九章算术》中有更相减损术求最大公约数的步骤：可半者半之，不可半者，副置分母•子之数，以少减多，更相减损，求其等也，以等数约之.翻译为：（1）任意给出两个正数；判断它们是否都是偶数.若是，用2约简；若不是，执行第二步.（2）以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数.继续这个操作，直到所得的数相

5、等为止，则这个数（等数）就是所求的最大公约数.例2：用更相减损术求91和49的最大公约数.分析：更相减损术是利用减法将大数化小，直到所得数相等时，这个数（等数）就是所求的最大公约数.（反思：辗转相除法与更相减损术是否存在相通的地方）练习：用更相减损术求72和168的最大公约数.3.小结：辗转相除法与更相减损术及比较①都是求最大公约数的方法，辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少；②结果上，辗转相除法体现结果是以相除余数为0得到，而更相减损术则以减数与差相等而得到

6、.三、巩固练习：1、练习：教材P35第1题　　2、作业：教材P38第1题教学后记：板书设计：第二课时1.3.2算法案例---秦九韶算法教学要求：了解秦九韶算法的计算过程，并理解利用秦九韶算法可以减少计算次数、提高计算效率的实质；理解数学算法与计算机算法的区别，理解计算机对数学的辅助作用.教学重点：秦九韶算法的特点及其程序设计.教学难点：秦九韶算法的先进性理解及其程序设计.教学过程：一、复习准备：1.分别用辗转相除法和更相减损术求出两个正数623和1513的最大公约数.2.设计一个求多项式当时的值的算法.

7、（学生自己提出一般的解决方案：将代入多项式进行计算即可）提问：上述算法在计算时共用了多少次乘法运算？多少次加法运算？此方案有何优缺点？(上述算法一共做了5＋4＋3＋2＋1＝15次乘法运算，5次加法运算.优点是简单、易懂；缺点是不通用，不能解决任意多项式的求值问题，而且计算效率不高.)二、讲授新课：1.教学秦九韶算法：①提问：在计算的幂值时，可以利用前面的计算结果，以减少计算量，即先计算，然后依次计算，，的值，这样计算上述多项式的值，一共需要多少次乘法，多少次加法?（上述算法一共做了4次乘法运算，5次加法

8、运算）②结论：第二种做法与第一种做法相比，乘法的运算次数减少了，因而能提高运算效率，而且对于计算机来说，做一次乘法所需的运算时间比做一次加法要长得多，因此第二种做法能更快地得到结果.③更有效的一种算法是：将多项式变形为：，依次计算，，，，故.――这种算法就是“秦九韶算法”.（注意变形，强调格式）④练习：用秦九韶算法求多项式当时的值.（学生板书师生共评教师提问：上述算法共需多少次乘法运算？多少次加法运算？）⑤如何用秦九韶算法完成一般多项式的求