《辗转相除法和更相减损术导学案.doc》由会员分享，可在线阅读，更多相关《辗转相除法和更相减损术导学案.doc（4页珍藏版）》请在金锄头文库上搜索。
1、第一章 算法初步 1.3 算法案例辗转相除法和更相减损术 制作人：计琳【我们的任务】1、阅读并体会辗转相除法和更相减损术的操作原理；2、会用辗转相除法和更相减损术求两个数的最大公约数；3、能根据辗转相除法和更相减损术设计完整的程序框图并写出算法程序。【重点】自然语言、程序框图和算法语句表达辗转相除法和更相减损术。【难点】辗转相除法和更相减损术的原理。【自主导学与探究】阅读教材P34P37的有关内容，自主完成教材例1，思考并回答下列问题：（一）辗转相除法（1）辗转相除法，又叫欧几里得法，是一种求两个正整数的的古老而有效的算法。（2）辗转相除法是指对于给定的两个数，用 除以 ，若余数不为零，则将余
2、数和 构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时 就是原来两个数的最大公约数。试一试：用辗转相除法求225和135的最大公约数问题一：辗转相除法的关键步骤是做带余除法：被除数除数商余数。其中被除数，除数和除数、余数有相同的最大公约数，即gcd（被除数，除数）gcd（除数，余数）（gcd是greatest common divisor即最大公约数的缩写），为什么呢？（可以通过多媒体技术查询资料）问题二：辗转相除法中，这样的带余除法进行到什么时候为止呢？为什么？（3）辗转相除法的算法步骤：第一步，给定 ；第二步,计算 ；第三步,；第四步,若r=0,则m,n的最大公约数等于 ；否则返
3、回。(4)程序框图：程序：开始输入m，n求m除以n的余数r输出m结束否是问题三：如果使用当型循环结构该如何制作程序框图及相应的程序？（二）更相减损术（1）更相减损术是我国古代数学专著九章算术中介绍的一种求的算法.（2）其基本过程是:第一步，任意给定两个正整数,判定它们是否都是，若是， ；若不是，执行第二步,以的数减去 的数，接着把所得的差与 的数比较，并以大数减小数，继续这个操作，直到所得的数 为止，则这个数（等数）或这个数与约简的数的乘积就是所求的最大公约数。试一试：用更相减损术求80和36的最大公约数（三）辗转相除法与更相减损术的区别（1）都是求最大公约数的方法，计算上辗转相除法以 为主，
4、更相减损术以 为主，计算次数上辗转相除法计算次数相对 ，特别当两个数字大小区别较大时计算次数的区别较明显。（2）从结果体现形式来看，辗转相除法体现结果是 则得到，而更相减损术则以 相等而得到。问题四：你能根据更相减损术设计程序，求两个正整数的最大公约数吗？算法步骤：第一步，给定两个正整数m,n，不妨设mn第二步，若m,n都是 ，则 ，使 ， 后的两个数仍记为m,n第三部，d=m-n第四步，判断 是否成立，若是，则将n,d中的较大者记为m，较小者记为n，返回第三步；否则， 为所求的最大公约数。否否是是是否开 始输入m,n(mn)K=0m,n均为偶数？d=m-nd=m-nn=dm=nm=d结束程序框图：程序：【自主测评】分别用辗转相除法和更相减损术求两个正整数282和470的最大公约数.
