1、第12课时5.4 算法案例重点难点重点：通过案例分析理解辗转相除法与更相减损术求最大公约数的方法，体会算法思想. 难点：把辗转相除法与更相减损术的方法转换成程序框图与程序语言.学习要求 1理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析. 2基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序.【课堂互动】问题：写出求两个正整数a,b(ab)的最大公约数的一个算法。1.辗转相除法公元前3世纪，欧几里得介绍了求两个正整数a,b(ab)的最大公约数的方法，求出一列数：，这列数从第三项开始，每一项都是前两项相除所得的余数（即），余数等于0的前一项，即是a和b的最
2、大公约数，这种方法称为“欧几里得辗转相除法”。例1 求两个正数8 251和6 105的最大公约数（分析：8 251与6 105两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根据已有的知识即可求出最大公约数）【解】8 2516 10512 146显然8 251和的2 146最大公约数也必是2 146的约数，同样6 105与2 146的公约数也必是8 251的约数，所以8 251与6 105的最大公约数也是6 105与2 146的最大公约数6 1052146218132 146181313331 81333351483331482371483740则37为8 251与6 105的最大公
3、约数【小结】以上我们求最大公约数的方法就是欧几里得辗转相除法其求最大公约数的步骤如下：第一步：用较大的数除以较小的数,得到一个商和一个余数；第二步：若，则为的最大公约数；若，则用除数除以余数,得到一个商和一个余数；第三步：若，则为的最大公约数；若，则用除数除以余数得到一个商和一个余数；依次计算直至，此时所得到的即为所求的最大公约数.【练习】求a=204，b=85的最大公约数，步骤为：S1 20485的余数为34，S2 8534的余数为17，S3 3417的余数为0。所以它们的最大公约数为17。算法描述：计算出ab的余数r，若r=0，则b为a，b的最大公约数；若r0，则把前面的除数b作为新的被除
4、数，把余数r作为新的除数（a，b要重新赋值，ab，br），继续进行上述运算，直到余数为0(用While循环语句，循环的执行条件是r0，当r=0时，循环终止)，此时的除数即为所求的最大公约数。算法如下:S1 输入两个正整数a,b(ab)；开始brYN结束输入a，babrMod(a,b)Mod(a,b) 0输出bS2 若Mod(a，b)=0，则转S3；否则，rMod(a,b)， ab，br，转S2。S3 输出最大公约数b. 【流程图】【伪代码】Read a,bWhile Mod(a,b)0 rMod(a,b) ab brEnd WhilePrint b2. 更相减损法我国早期也有解决求最大公约数问
5、题的算法，就是更相减损术更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母之数，以少减多，更相减损，求其等也，以等数约之翻译出来为：第一步：任意给出两个正数,判断它们是否都是偶数若是，用2约简；若不是，执行第二步第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数再从这个角度看一下“求a=204，b=85的最大公约数”的问题，S1步可以等价为等式：。S2步可以等价为等式：。这两步从减法的角度可以理解为：204-85，所得的差与减式中的较小数比较，再用大的数减小的数，循环执行以上步骤,直
6、到结果为0。此时减数就是a和b的最大公约数。这一算法根据它的特点，也可以用循环语句完成。参考代码： /a放较大的数，b放较小的数If a r Then a b b r Else a r End If r a b /确保相减后仍用较大的数减去较小的数End WhilePrint b用“更相减损法”求多于两个数的最大公约数就可以显示出其优越性【小结】比较辗转相除法与更相减损术的区别（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显（2）从结果体现形式来看，辗转相除法体现结果是以相除余
7、数为0则得到，而更相减损术则以减数与差相等而得到【追踪训练】1.分析下面一段代码的目的： Read m,n While m/nInt(m/n) cm- Int(m/n)n mn nc End While Print n(Int(x)表示不超过x的最大整数)【解】 求m，n的最大公约数 。2.用辗转相除法求下列各组数的最大公约数。（1）225,135; （2）98,196.3.用更相减损法求下列各组数的最大公约数。 （31）72,168; （2）153,119.4. 现有长度为360cm和780cm两种规格的钢筋若干.要焊接一批正方形模型.问:怎样才能保证正方体体积最大且不浪费?思路点拨: 正方体的所有棱长都相等,故必须将钢筋剪裁成长度相等的钢筋条;又必须不浪费,这就说明必须剪后无剩余.于是为了保证正方体的体积最大,故剪的钢筋的最大长度为360cm和780cm的最大公约数,可用更相减损术求最大公约数.
