高中数学必修三1.3.1辗转相除法与更相减损术省名师优质课赛课获奖课件市赛课一等奖课件

1.3.1案例1、辗转相除法与更相减损术第1页回顾算法三种表示方法：（1）、自然语言（2）、程序框图（3）、程序语言（三种逻辑结构）（五种基本语句）复习引入第2页思索：小学学过求两个数最大条约数方法？先用两个公有质因数连续去除，一直除到所得商是互为质数为止，然后把全部除数连乘起来.解：21824用公有质因数2除，3912用公有质因数3除，343和4互质不除了。得：18和24最大条约数是：2×3＝6

问题：怎样求8251与6105最大条约数？(8251,6105)=?

例、求18与24最大条约数：第3页用辗转相除法求8251和6105最大条约数过程第一步用两数中较大数除以较小数，求得商和余数

8251=6105×1+2146结论：8251和6105条约数就是6105和2146条约数，求8251和6105最大条约数，只要求出6105和2146条约数就能够了。

(8251,6105)=(6105,2146)

第二步对6105和2146重复第一步做法

6105=2146×2+1813〖辗转相除法（欧几里得算法）

〗同理6105和2146最大条约数也是2146和1813最大条约数。(8251,6105)=(6105,2146)=(2146,1813)以这类推第4页完整过程8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0例2用辗转相除法求225和135最大条约数225=135×1+90135=90×1+4590=45×2显然37是148和37最大条约数，也就是8251和6105最大条约数显然45是90和45最大条约数，也就是225和135最大条约数思索1：从上面两个例子能够看出计算规律是什么？第一步：用大数除以小数第二步：除数变成被除数，余数变成除数第三步：重复第一步，直到余数为0时

除数即为最大条约数第5页辗转相除法（欧几里得算法）所谓辗转相除法,就是对于给定两个数,用较大数除以较小数.若余数不为零,则将除数变成被除数，余数变成除数,继续上面除法,直到余数为0,则这时除数就是原来两个数最大条约数.练习：利用辗转相除法求两数4081与20723最大条约数（答案：53）第6页

辗转相除法是一个重复执行直到余数等于0停顿步骤，这实际上是一个循环结构。8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0m=n×q＋r用程序框图表示出右边过程r=mMODnm=nn=rr=0?是否思考2：辗转相除法中的关键步骤是哪种逻辑结构？第7页思索3：你能把辗转相除法编成一个计算机程序吗？算法步骤：第一步：输入两个正整数m,n(m>n).第二步：计算m除以n所得余数r.第三步：m=n,n=r.第四步：若r＝0,则m,n最大条约数等于m；不然转到第二步.第五步：输出最大条约数m.r=mMODnm=n是否n=r开始输入m,nr=0?输出m结束程序框图：INPUTm,nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND程序：第8页课后必做作业：

请同学们课后阅读教材，了解并掌握辗转相除法程序设计第9页〖更相减损术〗我国早期也有处理求最大条约数问题算法，就是更相减损术。更相减损术求最大条约数步骤以下：

可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。翻译出来为：第一步：任意给出两个正数；判断它们是否都是偶数。若是，用2约简；若不是，执行第二步。第二步：以较大数减去较小数，接着把所得差与较小数比较，并以大数减小数。继续这个操作，直到所得数相等为止，则这个数（等数）或这个数与约简数乘积就是所求最大条约数。第10页〖更相减损术〗第一步：任意给出两个正数；判断它们是否都是偶数。若是，用2约简；若不是，执行第二步。第二步：以较大数减去较小数，接着把所得差与较小数比较，并以大数减小数。继续这个操作，直到所得数相等为止，则这个数（等数）或这个数与约简数乘积就是所求最大条约数。例用更相减损术求98与63最大条约数解：因为两个数不都是偶数，把98和63以大数减小数，并辗转相减14－7＝7所以，98和63最大条约数等于7练习：用更相减损术求两个正数84与72最大条约数。（答案：12）98－63＝3563－35＝2835－28＝728－7＝2121－7＝14第11页（1）都是求最大条约数方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，尤其当两个数比较大时更适适用辗转相除法。（2）从结果表达形式来看，辗转相除法表达结果是以相除余数为0而得到，而更相减损术则以减数与差相等而得到。〖辗转相除法与更相减损术区分〗第12页用更相减损术求两个正整数m，n最大条约数算法步骤(1)输入两个整数m，n(2)若m≠n,转到(3),不然转到(4)(3)若m>n,则m=m-n,不然n=n-m,转到(2)(4)输出最大条约数n．第13页用更相减损术求两个正整数m，n最大条约数程序框图输入m,n开始m≠n？m>n？m=m-nn=n-m输出n结束NYYN算法步骤(1)输入两个整数m，n(2)若m≠n,转到(3),不然转到(4)(3)若m>n,则m=m-n,不然n=n-m,转到(2)(4)输出最大条约数n．第14页更相减损术算法程序：INPUT“m,n=”;m,nWHILEm<>nIFm>nTHENm=m-nELSEn=n-mENDIFWENDPRINTnEND程序程序框图输入m,n开始m≠n？m>n？m=m-nn=n-m输出n结束NYYN算法步骤(1)输入两个整数m，n(2)若m≠n,转到(3),不然转到(4)(3)若m>n,则m=m-n,不然n=n-m,转到(2)(4)输出最大条约数n．第15页（1）