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

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

2、有效性情感态度价值观在学习古代数学家解决数学问题的方法的过程中培养严谨的逻辑思维才能，在利用算法解决数学问题的过程中培养理性的精神和动手理论的才能。重点理解辗转相除法与更相减损术求最大公约数的方法。难点把辗转相除法与更相减损术的方法转换成程序框图与程序语言。教学过程及方法问题与情境及老师活动学生活动一复习引入考虑1：18与30的最大公约数是多少？你是怎样得到的？1短除法 求两个正整数的最大公约数的步骤：先用两个数公有的质因数连续去除，一直除到所得的商是两个互质数为止，然后把所有的除数连乘起来.2穷举法也叫枚举法 穷举法求两个正整数的最大公约数的解题步骤：从两个数中较小数开场由大到小列举，直到找

3、到公约数立即中断列举，得到的公约数便是最大公约数.考虑2：:对于8251与6105这两个数，由于其公有的质因数较大，利用上述方法求最大公约数就比较困难二研探新知探究一:辗转相除法考虑1：对于8251与6105这两个数，注意到8251=6105×1+2146，那么8251与6105这两个数的公约数和6105与2146的公约数有什么关系？ 显然8251与6105的最大公约数也必是2146的约数，同样6105与2146的公约数也必是8251的约数，所以8251与6105的最大公约数也是6105与2146的最大公约数。考虑2：又6105=2146×2+1813，同理，6105与21

4、46的公约数和2146与1813的公约数相等.重复上述操作，你能得到8251与6105这两个数的最大公约数吗？1河北武邑中学老师课时教案教学过程及方法问题与情境及老师活动学生活动考虑3：上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法.一般地，用辗转相除法求两个正整数m，n的最大公约数，可以用什么算法？其算法步骤如何设计？ 辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，假设余数不为零，那么将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大公约数. 考虑4：你能否把辗转相除法编程？辗转相除法求两个数的最大公约数

5、，其算法步骤可以描绘如下： 第一步，给定两个正整数m，n. 第二步，求余数r：计算m除以n，将所得余数存放到变量r中. 第三步，更新被除数和余数：m=n，n=r.第四步，判断余数r是否为0.假设余数为0，那么输出结果；否那么转向第二步继续循环执行.程序框图如以下图： 程序：INPUT m,nDO r=m MOD n m=n n=rLOOP UNTIL r=0PRINT mEND考虑4：你能用当型循环构造构造算法，求两个正整数的最大公约数吗？试画出程序框图和程序.当型循环构造的程序框图如右图程序：2河北武邑中学老师课时教案教学过程及方法问题与情境及老师活动学生活动INPUT m，nr=1WHIL

6、E r0 r=m MOD n m=n n=rWENDPRINT mEND探究二:更相减损术考虑1：设两个正整数m>n，假设m-n=k，那么m与 n的最大公约数和n与k的最大公约数相 等.反复利用这个原理，可求得98与63的最大公约数为多少？解：由于63不是偶数，把98和63以大数减小数， 并辗转相减，如以下图所示.所以，98和63的最大公约数等于7.考虑2：上述求两个正整数的最大公约数的方法称为更相减损术.一般地，用更相减损术求两个正整数m，n的最大公约数，可以用什么逻辑构造来构造算法？更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差和较小的INPUT “m，n=；m，nWHILE m<>nIF m>n THENm-nELSEm=n-mEND IFWENDPRINT mEND数构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公约数.考虑3：你能否把更相减损术编程？探究三：辗转相除法与更相减损术的区别1都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显