8.§1.3.1算法案例——辗转相除法与更相减损术

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

1、教师课时教案备课人授课时间课题§1.3.1算法案例——辗转相除法与更相减损术课标要求理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析。教学目标知识目标在辗转相除法与更相减损术求最大公约数的学习过程中对比我们常见的约分求公因式的方法，比较它们在算法上的区别，并从程序的学习中体会数学的严谨，领会数学算法计算机处理的结合方式，初步掌握把数学算法转化成计算机语言的一般步骤。技能目标通过具体的实例，掌握循环语句的具体应用，利用循环语句表达具体问题的过程，体会算法的基本思想借助框图中的循

2、环结构，借助Scilab语言中的循环语句来设计程序，进一步体会算法的重要性和有效性情感态度价值观在学习古代数学家解决数学问题的方法的过程中培养严谨的逻辑思维能力，在利用算法解决数学问题的过程中培养理性的精神和动手实践的能力。重点理解辗转相除法与更相减损术求最大公约数的方法。难点把辗转相除法与更相减损术的方法转换成程序框图与程序语言。教学过程及方法问题与情境及教师活动学生活动一．复习引入思考1：18与30的最大公约数是多少？你是怎样得到的？（1）短除法求两个正整数的最大公约数的步骤：先用两个数公有的质

3、因数连续去除，一直除到所得的商是两个互质数为止，然后把所有的除数连乘起来.（2）穷举法（也叫枚举法）穷举法求两个正整数的最大公约数的解题步骤：从两个数中较小数开始由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数.思考2：:对于8251与6105这两个数，由于其公有的质因数较大，利用上述方法求最大公约数就比较困难二．研探新知探究一:辗转相除法思考1：对于8251与6105这两个数，注意到8251=6105×1+2146，那么8251与6105这两个数的公约数和6105与2146的公

4、约数有什么关系？显然8251与6105的最大公约数也必是2146的约数，同样6105与2146的公约数也必是8251的约数，所以8251与6105的最大公约数也是6105与2146的最大公约数。思考2：又6105=2146×2+1813，同理，6105与2146的公约数和2146与1813的公约数相等.重复上述操作，你能得到8251与6105这两个数的最大公约数吗？1教师课时教案教学过程及方法问题与情境及教师活动学生活动思考3：上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法.一般地，

5、用辗转相除法求两个正整数m，n的最大公约数，可以用什么算法？其算法步骤如何设计？辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大公约数.思考4：你能否把辗转相除法编程？辗转相除法求两个数的最大公约数，其算法步骤可以描述如下：第一步，给定两个正整数m，n.第二步，求余数r：计算m除以n，将所得余数存放到变量r中.第三步，更新被除数和余数：m=n，n=r.第四步，判断余

6、数r是否为0.若余数为0，则输出结果；否则转向第二步继续循环执行.程序框图如下图：程序：INPUTm,nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND思考4：你能用当型循环结构构造算法，求两个正整数的最大公约数吗？试画出程序框图和程序.当型循环结构的程序框图如右图程序：2教师课时教案教学过程及方法问题与情境及教师活动学生活动INPUTm，nr=1WHILEr＞0r=mMODnm=nn=rWENDPRINTmEND探究二:更相减损术思考1：设两个正整数m>n，若m-n=k，则

7、m与n的最大公约数和n与k的最大公约数相等.反复利用这个原理，可求得98与63的最大公约数为多少？解：由于63不是偶数，把98和63以大数减小数，并辗转相减，如下图所示.所以，98和63的最大公约数等于7.思考2：上述求两个正整数的最大公约数的方法称为更相减损术.一般地，用更相减损术求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法？更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差和较小的INPUT“m，n=”；m，nWHILEm<>nIFm>nTHENｍ＝m-nEL

8、SEm=n-mENDIFWENDPRINTmEND数构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公约数.思考3：你能否把更相减损术编程？探究三：辗转相除法与更相减损术的区别（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数