人教必修三《1.3.1辗转相除法与更相减损术》.ppt

1.3算法案例

辗转相除法与更相减损术1.3算法案例

韩信是秦末汉初的著名军事家.据说有一次汉高祖刘邦在卫士的簇拥下来到练兵场,刘邦问韩信有什么方法,不要逐个报数,就能知道场上的士兵的人数,韩信先令士兵排成3列纵队,结果有2人多余,接着下令排成5列纵队,结果又多出3人,随后他又下令改为7列纵队,这次又剩下2人无法成整行.在场的人都哈哈大笑,以为韩信不能清点出准确的人数,不料笑声刚落,韩信高声报告共有士兵2333人.众人听了一楞,不知道韩信用什么方法这么快就能得到正确的结果的.今天,我们将以这些古典案例的思想,设计出适宜计算机的运行程序,提高我们对基本算法结构和算法语句在实际中的运用能力.情境创设

探究一：辗转相除法思考一：在小学里我们是如何救出两个正整数的最大公约数的？算法案例之求最大公约数解：２１８２４用公有质因数２除３９１２用公有质因数３除３４３和４互质，不除了得：１８和２４的最大公约数：２x３＝６短除法例：求１８与24的最大公约数

想一想，如何求8251与6105的最大公约数？思考2:对于8251与6105这两个数，它们的最大公约数是多少？你是怎样得到的？由于它们公有的质因数较大，利用上述方法求最大公约数就比较困难.有没有其它的方法可以较简单的找出它们的最大公约数呢？思考3：注意到8251=6105×1+2146，那么8251与6105这两个数的公约数和6105与2146的公约数有什么关系？我们发现6105=2146×2+1813，同理，6105与2146的公约数和2146与1813的公约数相等.思考4：重复上述操作，你能得到8251与6105这两个数的最大公约数吗？2146=1813×1+333，148=37×4+0.8251=6105×1+2146，6105=2146×2+1813，

定义:所谓的辗转相除法,就是对于给定的两个数,用较大的数除以较小的数,若余数不为零,则将余数和较小的数构成新的数对,继续上面的除法,直到大数被小数除尽,则这是较小的数就是原来两个数的最大公约数

例1观察用辗转相除法求8251和6105的最大公约数的过程第一步用两数中较大的数除以较小的数，求得商和余数

8251=6105×1+2146结论：8251和6105的公约数就是6105和2146的公约数，求8251和6105的最大公约数，只要求出6105和2146的公约数就可以了。第二步对6105和2146重复第一步的做法

6105=2146×2+1813

同理6105和2146的最大公约数也是2146和1813的最大公约数。完整的过程8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0显然37是148和37的最大公约数，也就是8251和6105的最大公约数

思考：辗转相除法中的关键步骤是哪种逻辑结构？辗转相除法中的关键步骤是哪种逻辑结构？辗转相除法是一个反复执行直到余数等于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?是否

思考5:该算法的程序框图如何表示？

思考6:该程序框图对应的程序如何表述？IN，nDOr=mMODnm=nn=rLOOPUNTILr=0END

开始m=nn0？结束是n=rIN，nWHILEn0r=mMODnm=nn=rWENDEND

知识探究（二）:更相减损术98-63=35，14-7=7.21-7=14，28-7=21，35-28=7，63-35=28，

思考3:该算法的程序框图如何表示？

IN，nWHILEmnk=m-nIFnkTHENm=nn=kELSEm=kENDIFWENDEND

理论迁移

思考：把更相减损术与辗转相除法比较，你有哪些发现？辗转相除法与更相减损术的算理相似，有异曲同工之妙主要区别:辗转相除法进项的是除法运算，即辗转相除.而更相减损术进行的是减法运算，即辗转相减，但实质都是一个不断的递归过程。

小结作业