高中数学(算法案例——辗转相除法与更相减损术)课件2 北师大版必修3 课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,2026/2/23 周一,1.3,算法案例,第一课时,2026/2/23 周一,问题提出,1.,研究一个实际问题的算法，主要从算法步骤、程序框图和编写程序三方面展开,.,在程序框图中算法的基本逻辑结构有哪几种？在程序设计中基本的算法语句有哪几种？,2.,“,求两个正整数的最大公约数,”,是数学中的一个基础性问题，它有各种解决办法，我们以此为案例，对该问题的算法作一些探究,.,2026/2/23 周一,辗转相除法与,更相减损术,2026/2/23 周一,知识探究（一）,:,辗转相除法,思考,1:,18,与,30,的最大公约数是多少？你是怎样得到的？,先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来即为最大公约数,.,2026/2/23 周一,思考,2:,对于,8251,与,6105,这两个数，由于其公有的质因数较大，利用上述方法求最大公约数就比较困难,.,注意到,8251=6105,1+2146,，那么,8251,与,6105,这两个数的公约数和,6105,与,2146,的公约数有什么关系？,2026/2/23 周一,思考,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,，,2026/2/23 周一,思考,4:,上述求两个正整数的最大公约数的方法称为,辗转相除法,或,欧几里得算法,.,一般地，用辗转相除法求两个正整数,m,，,n,的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？,第一步，给定两个正整数,m,，,n(m,n).,第二步，计算,m,除以,n,所得的余数,r.,第三步，,m=n,，,n=r.,第四步，若,r=0,，则,m,，,n,的最大公约数等 于,m,；否则，返回第二步,.,2026/2/23 周一,思考,5:,该算法的程序框图如何表示？,开始,输入,m,，,n,求,m,除以,n,的余数,r,m=n,n=r,r=0,？,是,输出,m,结束,否,2026/2/23 周一,思考,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,结束,否,2026/2/23 周一,思考,7:,如果用当型循环结构构造算法，则用辗转相除法求两个正整数,m,，,n,的最大公约数的程序框图和程序分别如何表示？,2026/2/23 周一,开始,输入,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,2026/2/23 周一,知识探究（二）,:,更相减损术,思考,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,，,2026/2/23 周一,思考,2:,上述求两个正整数的最大公约数的方法称为,更相减损术,.,一般地，用更相减损术求两个正整数,m,，,n,的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？,第一步，给定两个正整数,m,，,n(mn).,第二步，计算,m-n,所得的差,k.,第三步，比较,n,与,k,的大小，其中大者用,m,表 示，小者用,n,表示,.,第四步，若,m=n,，则,m,，,n,的最大公约数等于,m,；否则，返回第二步,.,2026/2/23 周一,思考,3:,该算法的程序框图如何表示？,开始,输入,m,，,n,nk,？,m=n,是,输出,m,结束,mn,？,k=m,-,n,是,否,n=k,m=k,否,2026/2/23 周一,思考,4:,该程序框图对应的程序如何表述？,INPUT m,，,n,WHILE,m,n,k=m-n,IF n,k THEN,m=n,n=k,ELSE,m=k,END IF,WEND,PRINT m,END,开始,输入,m,，,n,nk,？,m=n,是,输出,m,结束,mn,？,k=m,-,n,是,否,n=k,m=k,否,2026/2/23 周一,“,更相减损术,”,在中国古代数学专著,九章算术,中记述为：,可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之,.,2026/2/23 周一,理论迁移,例,1,分别用辗转相除法和更相减损术求,168,与,93,的最大公约数,.,辗转相除法：,168=93,1+75,，,93=75,1+18,，,75=18,4+3,，,18=3,6.,2026/2/23 周一,更相减损术,: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,，,6-3=3.,2026/2/23 周一,例,2,求,325,，,130,，,270,三个数的最大公约数,.,因为,325=130,2+65,，,130=65,2,，,所以,325,与,130,的最大公约数是,65.,因为,270=65,4+10,，,65=10,6+5,，,10=5,2,，,所以,65,与,270,最大公约数是,5.,故,325,，,130,，,270,三个数的最大公约数是,5.,2026/2/23 周一,1.,辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大公约数,.,小结作业,2.,更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公约数,.,2026/2/23 周一,作业：,P45,练习：,1.,P48,习题,1.3A,组：,1.,