(用)高一数学必修3辗转相除法与更相减损术pp(精)

1、1.3算法案例问题提出1.研究一个实际问题的算法，主要从 算法步骤、程序框图和编写程序三方面 展开.在程序框图中算法的基本逻辑结构 有哪几种？在程序设计中基本的算法语 句有哪几种？2.“求两个正整数的最大公约数” 是数学中的一个基础性问题，它有各种 解决办法，我们以此为案例，对该问题 的算法作一些探究.知识探究（一）：辗转相除法思考1:18与30的最大公约数是多少？你 是怎样得到的？先用两个数公有的质因数连续去除, 一直除到所得的商是互质数为止，然 后把所有的除数连乘起来即为最大公 约数.例.求30和75的最大公约数3| 30 755严2525所以，30和35的最大 公约数为15思考2:对于8

2、251与6105这两个数，由于 其公有的质因数较大，利用上述方法求 最大公约数就比较困难注意到8251=6105X1+2146,那么8251与6105这 两个数的公约数和6105与2146的公约数 有什么关系？148=37X4+0思考3:又6105=2146X2+1813,同理,6105与2146的公约数和2146与1813的公约数相等重复上述操作，你能得到8251与6105这两个数的最大公约数吗?8251=6105X1+2146, 6105=2146X2+1813,2146=1813X1+333, 1813=333X5+148,333=148X2+,148=X4+0.舉蓉相除法中狗羌健步瞬是

3、哪种逻辑辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是 一个循环结构。8251=6105X1+21466105=2146X2+18132146=1813X1+3331813=333X5+148用程333=48 X 2+思考5:上述求两个正整数的最大公约数 的方法称为辗转相除法或欧几里得算法. 一般地，用辗转相除法求两个正整数m, n的最大公约数，可以用什么逻辑结构来 构造算法？其算法步骤如何设计？ 第一步，给定两个正整数m, n (mn).第二步，计算m除以n所得的余数工第三步，m=n, n=r.第四步，若r=0,则m, n的最大公约数等于m;否则，返回第二步.思考5:该算法的程

4、序框图如何表示?结束思考6:该程序框图对应的程序如何表述?INPUT m, nDOr=m MODnm=n n=rLOOP UNTIL r=0 PRINT mEND思考7:如果用当型循环结构构造算法，则用辗转相除法求两个正整数m,n的最 大公约数的程序框图和程序分别如何表 示？求m除以m=n否INPUT m, nWHILE n0 r=mMODn m=nn=rWENDPRINT m END练习1：利用辗转相除法求两数4081与20723的最大公约数.20723=4081X5+314081=318X12+265;/蕭出结束265=53X5+0.知识探究(二)：更相减损术思考1： 设两个正整数mn,若

5、m-n=k,贝!Jm与n的最大公约数和n与k的最大公约数相 等反复利用这个原理，可求得98与63的 最大公约数为多少？98-63=35,63-35=28，35-28=7,28-7=21,21-7=14,14-7=7.思考2:上述求两个正整数的最大公约数 的方法称为更相减损术一般地， 用更相 减损术求两个正整数叫n的最大公约数， 可以用什么逻辑结构来构造算法？其算 法步骤如何设计？第一步，给定两个正整数n (mn)第二步，计算m-n所得的差k.第三步，比较n与k的大小，其中大者用示，小者用n表示.第四步，若m=n,则m, n的最大公约数等于m;否则，返回第二步.INPUTm, nWHILEmon

6、k=m-nIF nkTHEN思思考4:该程序框图对应的程序如何表述?开始n=kELSE ,PRIN“更相减损术”在中国古代数学专著九章算术中记述为：可半者半之，不可半者，副置分母、子 之数，以少减多，更相减损，求其等也， 以等数约之.INPUTum,n=u;m,nWhile donIFmn thena=mm=dm=nELSEn=am=nEND IFn=dK=0End ifWHILE m MOD 2=0d=m-nAND n MOD 2=0Wendm=m/2d=2Ak*dn=n/2PRINT dk=k+1EndWENDd=m- n理论迁移例1分别用辗转相除法和更相减损 术求168与93的最大公约数

7、.辗转相除法：168=93X1+75, 93=75X1+18,75=18X4+3,18=3X6.更相减损术:168-93=75,93-75=18,75-18=57,57-18=39,39-18=21,21-18=3,18-3=15,15-3=12,12-3=9,9-3=6,例2求325, 130, 270三个数的最大 公约数.因为325=130X2+65, 130=65X2,所以325与130的最大公约数是65.因为270=65X4+10, 65=10X6+5,10二5X2,所以65与270最大公约数是5.故325, 130, 270三个数的最大公约 数是5.小结作业1辗转相除法，就是对于给定的两个正整 数，用较大的数除以较小的数，若余数不为 零，则将余数和较小的数构成新的一对数， 继续上面的除法，直到大数被小数除尽为止， 这时的较小的数即为原来两个数的最大公约 数.2.更相减损术，就是对于给定的两个正 整数，用较大的数减去较小的数，然后将差 和较小的数构成新的一对数，继续上面的减 法，直到差和较小的数相等，此时相等的两 数即为原来两个数的最大公约数.小结比较辗转相除法与更相减损术的区别(1)都是求最大公约数的方法，计算上辗转相除 法以除法为主，更相减损术以减法为主，