高中数学第12课时5.4算法案例学案新人教A版必修3

1、第 12 课时 5.4 算法案例重点难点重点：通过案例分析理解辗转相除法与更相减损术求最大公约数的方法，体会算法思想。难点：把辗转相除法与更相减损术的方法转换成程序框图与程序语言.学习要求1理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析。2基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序.【课堂互动】问题：写出求两个正整数a,b(ab) 的最大公约数的一个算法。1. 辗转相除法公元前 3 世纪，欧几里得介绍了求两个正整数a,b(ab) 的最大公约数的方法，求出一列数：0,121nnrrrrba，这列数从第三项开始，每一项都是前两项相除所得的余数（即)

2、,(12nnnrrmodr） ，余数等于0 的前一项nr，即是 a 和 b 的最大公约数，这种方法称为“欧几里得辗转相除法”。例 1 求两个正数8251 和 6105 的最大公约数（分析： 8251 与 6105 两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根据已有的知识即可求出最大公约数）【解】 8251610512146 显然 8251 和 2146 的最大公约数也必是2146 的约数，同样6105 与 2146 的公约数也必是 8251 的约数，所以8251 与 6105 的最大公约数也是6105 与 2146 的最大公约数6105214621813 21461813133

3、3 18133335 148 333148237 1483740 则 37 为 8251 与 6105 的最大公约数【小结】 以上我们求最大公约数的方法就是欧几里得辗转相除法其求最大公约数的步骤如下：第一步：用较大的数m除以较小的数n得到一个商0q和一个余数0r；第二步：若00r，则n为,m n的最大公约数；若00r，则用除数n除以余数0r得到一个商1q和一个余数1r；第三步：若10r，则1r为,m n的最大公约数；若10r，则用除数0r除以余数1r得到一个商2q和一个余数2r；依次计算直至0nr，此时所得到的1nr即为所求的最大公约数. 【练习】求a=204，b=85 的最大公约数，步骤为：

4、s1 s2 s3 所以它们的最大公约数为。算法描述：计算出ab 的余数 r，若 r=0，则 b 为 a，b 的最大公约数；若r0，则把前面的除数b 作为新的被除数，把余数r 作为新的除数（a，b 要重新赋值， ab，b r） ，继续进行上述运算，直到余数为0(用 while 循环语句，循环的执行条件是r0，当 r=0 时，循环终止 )，此时的除数即为所求的最大公约数。算法如下 :s1 输入两个正整数a,b(ab) ；s2 若 mod(a，b)=0 ，则转 s3；否则， r mod(a,b)， ab，br，转 s2。s3 输出最大公约数b；【流程图】开始b r 输入 a，b ab rmod(a,

5、b) 【伪代码】2.更相减损法我国早期也有解决求最大公约数问题的算法，就是更相减损术更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母之数，以少减多，更相减损，求其等也，以等数约之翻译出来为：第一步：任意给出两个正数；判断它们是否都是偶数若是，用2 约简；若不是，执行第二步第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数再从这个角度看一下“求a=204，b=85 的最大公约数”的问题，s1 步可以等价为等式：34285204。 s2 步可以等价为等式：1723485。这两步从减法的

6、角度可以理解为：204-85 ，所得的差与减式中的较小数比较，再用大的数减小的数，循环执行以上步骤,read a,b while mod(a,b) 0 r mod(a,b) ab br 直到结果为0。此时减数就是a 和 b 的最大公约数。这一算法根据它的特点，也可以用循环语句完成。参考代码： /a放较大的数，b 放较小的数if a r then a b b r else a r end if r a b / 确保相减后仍用较大的数减去较小的数end while print b 用“更相减损法”求多于两个数的最大公约数就可以显示出其优越性【小结】比较辗转相除法与更相减损术的区别（1）都是求最大公

7、约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0 则得到，而更相减损术则以减数与差相等而得到【追踪训练】1.分析下面一段代码的目的：read m,n while m/n int(m/n) cm- int(m/n) n m n nc end while print n (int(x)表示不超过x 的最大整数 ) 【解】。2.用辗转相除法求下列各组数的最大公约数。（ 1）225；135 （2）98；196 3.用更相减损法求下列各组数的最大公约数。（ 31）72；168 （2）153；1194. 现有长度为360cm 和 780cm 两种规格的钢筋若干.要焊接一批正方形模型.问怎样才能保证正方体体积最大且不浪费? 思路点拨