高中数学 算法案例(辗转相除法)课件 新人教A版必修3 课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,算 法 案 例 辗转相除法,(,第一课时,),1,、求两个正整数的最大公约数,（,1,）求,25,和,35,的最大公约数,（,2,）求,49,和,63,的最大公约数,2,、求,8251,和,6105,的最大公约数,25,（,1,）,5,5,35,7,49,（,2,）,7,7,63,9,所以，,25,和,35,的最大公约数为,5,所以，,49,和,63,的最大公约数为,7,辗转相除法（欧几里得算法）,观察求,8251,和,6105,的最大公约数的过程,第一步,用两数中较大的数除以较小的数，求得商和余数,8251=61051+2146,结论：,8251,和,6105,的公约数就是,6105,和,2146,的公约数，求,8251,和,6105,的最大公约数，只要求出,6105,和,2146,的公约数就可以了。,第二步,对,6105,和,2146,重复第一步的做法,6105=21462+1813,同理,6105,和,2146,的最大公约数也是,2146,和,1813,的最大公约数。,为什么呢？,思考：从上述的过程你体会到了什么？,完整的过程,8251=61051+2146,6105=21462+1813,2146=18131+333,1813=3335+148,333=1482+37,148=374+0,例,2,用辗转相除法求,225,和,135,的最大公约数,225=1351+90,135=901+45,90=452,显然,37,是,148,和,37,的最大公约数，也就是,8251,和,6105,的最大公约数,显然,45,是,90,和,45,的最大公约数，也就是,225,和,135,的最大公约数,思考,1,：从上面的两个例子可以看出计算的规律是什么？,S1,：,用大数除以小数,S2,：,除数变成被除数，余数变成除数,S3,：,重复,S1,，,直到余数为,0,利用辗转相除法求两数,4081,与,20723,的最大公约数,思考：你能把辗转相除法编成程序吗？,算法,2,：,第一步：任意给定两个正整数，大的数记为,m,，,小的记为,n,；,第二步：用,m,除以,n,，,求得余数,r,；,第三步：判断,r,是否为,0,，若,r=0,，,则输出,n,，,若,r,0,，,则令,m=n,，,n=r,，,再返回第二步,.,算法,1,：,第一步：任意给定两个正整数；,第二步：用两数中较大那个除以较小那个，求得,商和余数；,第三步：比较上一步的余数与除数的大小关系，,继续用较大数除以较小数，并一直重复,上述步骤直到余数为,0,，则此时的除数即,为所求,.,辗转相除法是一个反复执行直到余数等于,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?,是,否,思考2：辗转相除法中的关键步骤是哪种逻辑结构？,开始,输入,m,n,r=m MOD n,m=n,n=r,r=0?,否,是,输出,m,结束,程序：,INUPU m,n,DO,r=m MOD n,m=n,n=r,LOOP UNTIL r=0,PRINT m,END,算法,2,：,开始,输入,m,n,mn?,x=m,m=n,n=x,否,是,r=m MOD n,m=n,n=r,r=0?,否,是,输出,m,结束,程序：,INUPU m,n,IF mn THEN,x=m,m=n,n=x,END IF,DO,r=m MOD n,m=n,n=r,LOOP UNTIL r=0,PRINT m,END,算法,1,：,