131辗转相除法与更相减损术

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,辗转相除法与,更相减损术,知识探究（一）,:,辗转相除法,思考,1:,18,与,30,的最大公约数是多少？你是怎样得到的？,先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来即为最大公约数,.,思考,2:,对于,8251,与,6105,这两个数，由于其公有的质因数较大，利用上述方法求最大公约数就比较困难,.,注意到,8251=6105,1+2146,，那么,8251,与,6105,这两个数的公约数和,6105,与,2146,的公约数有什么关系？,思考,3:,又,6105=2146,2+1813,，同理，,6105,与,2146,的公约数和,2146,与,1813,的公约数相等,.,重复上述操作，你能得到,8251,与,6105,这两个数的最大公约数吗？,2146,=,1813,1+,333,，,148,=,37,4+0.,333,=,148,2+,37,，,1813,=,333,5+,148,，,8251=,6105,1+,2146,，,6105,=,2146,2+,1813,，,辗转相除法是一个反复执行直到余数等于,0,停止的步骤，这实际上是一个循环结构。,8251=61051+2146,6105=21462+1813,2146=18131+333,1813=3335+148,333=1482+37,148=374+0,m=n q,r,用程序框图表示出右边的过程,r=m MOD n,m=n,n=r,r=0?,是,否,思考4：辗转相除法中的关键步骤是哪种逻辑结构？,思考,5:,上述求两个正整数的最大公约数的方法称为,辗转相除法,或,欧几里得算法,.,一般地，用辗转相除法求两个正整数,m,，,n,的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？,第一步，给定两个正整数,m,，,n(m,n).,第二步，计算,m,除以,n,所得的余数,r.,第三步，,m=n,，,n=r.,第四步，若,r=0,，则,m,，,n,的最大公约数等 于,m,；否则，返回第二步,.,思考,6:,该程序框图对应的程序如何表述？,INPUT m,，,n,DO,r=m,MODn,m=n,n=r,LOOP UNTIL,r=0,PRINT m,END,开始,输入,m,，,n,求,m,除以,n,的余数,r,m=n,n=r,r=0,？,是,输出,m,结束,否,ys,开始,输入,m,，,n,求,m,除以,n,的余数,r,m=n,n0,？,否,输出,m,结束,是,n=r,INPUT m,，,n,WHILE,n,0,r=m,MODn,m=n,n=r,WEND,PRINT m,END,知识探究（二）,:,更相减损术,思考,1:,设两个正整数,m,n,，若,m-n,=k,，则,m,与,n,的最大公约数和,n,与,k,的最大公约数相等,.,反复利用这个原理，可求得,98,与,63,的最大公约数为多少？,98-63=35,，,14-7=7.,21-7=14,，,28-7=21,，,35-28=7,，,63-35=28,，,思考,2:,上述求两个正整数的最大公约数的方法称为,更相减损术,.,一般地，用更相减损术求两个正整数,m,，,n,的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？,第一步，给定两个正整数,m,，,n(m,n).,第二步，计算,m-n,所得的差,k.,第三步，比较,n,与,k,的大小，其中大者用,m,表 示，小者用,n,表示,.,第四步，若,m=n,，则,m,，,n,的最大公约数等于,m,；否则，返回第二步,.,“,更相减损术,”,在中国古代数学专著,九章算术,中记述为：,可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之,.,INPUT “,m,n,=“;,m,n,IF mn then,m=d,ELSE,m=n,n=d,End if,d=,m-n,Wend,d=2k*d,PRINT d,End,