算法案例导学案

2017-2018-1大同一中高一年级数学（必修三）导学设计第一章算法初步§1.3算法案例——辗转相除法和更相减损术制作人：计琳【我们的任务】1、阅读并体会辗转相除法和更相减损术的操作原理；2、会用辗转相除法和更相减损术求两个数的最大公约数；3、能根据辗转相除法和更相减损术设计完整的程序框图并写出算法程序。【重点】自然语言、程序框图和算法语句表达辗转相除法和更相减损术。【难点】辗转相除法和更相减损术的原理。【自主导学与探究】阅读教材P34～P37的有关内容，自主完成教材例1，思考并回答下列问题：（一）辗转相除法（1）辗转相除法，又叫欧几里得法，是一种求两个正整数的的古老而有效的算法。（2）辗转相除法是指对于给定的两个数，用除以，若余数不为零，则将余数和构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时就是原来两个数的最大公约数。试一试：用辗转相除法求225和135的最大公约数．问题一：辗转相除法的关键步骤是做带余除法：被除数＝除数×商＋余数。其中被除数，除数和除数、余数有相同的最大公约数，即gcd（被除数，除数）＝gcd（除数，余数）（gcd是greatestcommondivisor即最大公约数的缩写），为什么呢？（可以通过多媒体技术查询资料）问题二：辗转相除法中，这样的带余除法进行到什么时候为止呢？为什么？（3）辗转相除法的算法步骤：第一步，给定；第二步,计算；第三步,；第四步,若r=0,则m,n的最大公约数等于；否则返回。2017-2018-1大同一中高一年级数学（必修三）导学设计(4)程序框图：程序：问题三：如果使用当型循环结构该如何制作程序框图及相应的程序？（二）更相减损术（1）更相减损术是我国古代数学专著《九章算术》中介绍的一种求的算法.（2）其基本过程是:第一步，任意给定两个正整数,判定它们是否都是，若是，；若不是，执行．第二步,以的数减去的数，接着把所得的差与的数比较，并以大数减小数，继续这个操作，直到所得的数为止，则这个数（等数）或这个数与约简的数的乘积就是所求的最大公约数。试一试②：用更相减损术求80和36的最大公约数．（三）辗转相除法与更相减损术的区别（1）都是求最大公约数的方法，计算上辗转相除法以为主，更相减损术以为主，计算次开始mnnr输入m，n求m除以n的余数r输出m结束0?r否是INPUT,DOMODLOOPUNTIL0PRTNTENDmnrmnmnnrrm2017-2018-1大同一中高一年级数学（必修三）导学设计数上辗转相除法计算次数相对，特别当两个数字大小区别较大时计算次数的区别较明显。（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=n?dnm=d结束2017-2018-1大同一中高一年级数学（必修三）导学设计程序：【自主测评】分别用辗转相除法和更相减损术求两个正整数282和470的最大公约数.