新高一数学《案例1辗转相除法与更相减损术》

《新高一数学《案例1辗转相除法与更相减损术》》由会员分享，可在线阅读，更多相关《新高一数学《案例1辗转相除法与更相减损术》（17页珍藏版）》请在文档大全上搜索。

1、广灵五中高一数学备课组广灵五中高一数学备课组 刘鸿英刘鸿英1. 1. 回顾算法的三种表述：回顾算法的三种表述：自然语言自然语言程序框图程序框图程序语言程序语言（三种逻辑结构）（三种逻辑结构）（五种基本语句）（五种基本语句）2. 2. 思考：思考： 小学学过的求两个数最大公约数的方法？小学学过的求两个数最大公约数的方法？ 先用两个公有的质因数连续去除，一直除到所得的商是先用两个公有的质因数连续去除，一直除到所得的商是互为质数为止，然后把所有的除数连乘起来互为质数为止，然后把所有的除数连乘起来. .复复 习回顾习回顾所以，所以，7575和和105105的最的最大公约数为大公约数为15152 2、除

2、了用这种方法外还有没有其它方法？、除了用这种方法外还有没有其它方法？如求如求82518251和和61056105的最大公约数的最大公约数. . 1 1、求两个正整数的最大公约数、求两个正整数的最大公约数求求7575和和105105的最大公约数的最大公约数75755 5151510510521215 57 73 31 1、辗转相除法、辗转相除法: :此算法是欧几里得在公元前此算法是欧几里得在公元前300300左右左右首先提出的首先提出的 （欧几里得算法）（欧几里得算法） 所谓辗转相除法所谓辗转相除法, ,就是对于给定的两个数就是对于给定的两个数, ,用较大用较大的数除以较小的数的数除以较小的数.

3、 .若余数不为零若余数不为零, ,则将余数和较小的则将余数和较小的数构成新的一对数数构成新的一对数, ,继续上面的除法继续上面的除法, ,直到大数被小数直到大数被小数除尽除尽, ,则这时较小的数就是原来两个数的最大公约数则这时较小的数就是原来两个数的最大公约数. .例例1.用辗转相除法求用辗转相除法求161与与63的最大公约数的最大公约数.161=2633563=1 352835=1 28728=4 70所以，所以，161与与63的最大公约数为的最大公约数为7 7新新 课课82518251= =610561051+1+21462146 61056105= =214621462+2+181318

4、13 21462146= =181318131+1+33333318131813= =3333335+5+148148333333= =1481482+2+3737148148= =37374 4所以所以3737是是82518251和和61056105的最大公约数的最大公约数 例例2 2、求、求82518251和和61056105的最大公的最大公约数约数. . P P4545) )练习练习1(1)1(1)用辗转相除法用辗转相除法求求225225和和135135的最大公约数的最大公约数225225= =1351351+1+9090135135= =90901+1+45459090= =45452

5、 2所以所以4545是是225225和和135135的最大公约数的最大公约数 思考：从上面的两个例子可思考：从上面的两个例子可以看出计算的规律是什么？以看出计算的规律是什么？ S1S1：用大数除以小数：用大数除以小数S2S2：除数变成被除数，余数变成除数：除数变成被除数，余数变成除数S3S3：重复：重复S1S1，直到余数为，直到余数为0 0 辗转相除法是一个反复执行直到余数等于辗转相除法是一个反复执行直到余数等于0 0停止的步骤停止的步骤, ,这实际上是这实际上是一个循环结构一个循环结构m=nm=nq qr r算法步骤算法步骤第一步：输入两个正整数第一步：输入两个正整数m,n(mm,n(mn)

6、.n).第二步：计算第二步：计算m m除以除以n n所得的余数所得的余数r.r.第三步：第三步：m=n,nm=n,n=r.=r.第四步：若第四步：若r r0,0,则则m,nm,n的最大公约数等于的最大公约数等于m;m;否则转到第二步否则转到第二步. . 第五步：输出最大公约数第五步：输出最大公约数m.m.程序框图程序框图程程 序序r=m MOD nr=m MOD nm=nm=n是是否否n=rn=r开始开始输入输入m,nm,nr=0?r=0? 输出输出m m结束结束INPUT “m,n=“;m,nDOLOOP UNTIL r = m MOD nm = nn = rr=0PRINT mEND程序框