杜红全《算法案例》辗转相除法与更相减损术-新人教A版必修3省公开课金奖全国赛课一等奖微课获奖课.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,1.3,算法案例,第一课时,康县一中 杜红全,1/22,1.,研究一个实际问题算法，主要从算法步骤、程序框图和编写程序三方面展开,.,在程序框图中算法基本逻辑结构有哪几个？在程序设计中基本算法语句有哪几个？,2.“,求两个正整数最大条约数”是数学中一个基础性问题，它有各种处理方法，我们以此为案例，对该问题算法作一些探究,.,问题提出,2/22,辗转相除法与更相减损术,3/22,思索,1:,18,与,30,最大条约数是多少？你是怎样得到？,先用两个数公有质因数连续去除，一直除到所得商是互质数为止，然后把全部除数连乘起来即为最大条约数,.,知识探究（一）,:,辗转相除法,4/22,思索,2:,对于,8251,与,6105,这两个数，因为其公有质因数较大，利用上述方法求最大条约数就比较困难,.,注意到,8251=61051+2146,，那么,8251,与,6105,这两个数条约数和,6105,与,2146,条约数有什么关系？,5/22,思索,3:,又,6105=21462+1813,，同理，,6105,与,2146,条约数和,2146,与,1813,条约数相等,.,重复上述操作，你能得到,8251,与,6105,这两个数最大条约数吗？,2146,=,1813,1+,333,，,148=,37,4+0.,333,=1482+,37,，,1813,=,333,5+148,，,8251=,6105,1+,2146,，,6105,=,2146,2+,1813,，,6/22,思索,4:,上述求两个正整数最大条约数方法称为,辗转相除法,或,欧几里得算法,.,普通地，用辗转相除法求两个正整数,m,，,n,最大条约数，能够用什么逻辑结构来结构算法？其算法步骤怎样设计？,第一步，给定两个正整数,m,，,n(m,n).,第二步，计算,m,除以,n,所得余数,r.,第三步，,m=n,，,n=r.,第四步，若,r=0,，则,m,，,n,最大条约数等 于,m,；不然，返回第二步,.,7/22,思索,5:,该算法程序框图怎样表示？,开始,输入,m,，,n,求,m,除以,n,余数,r,m=n,n=r,r=0,？,是,输出,m,结束,否,8/22,思索,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,结束,否,9/22,思索,7:,假如用当型循环结构结构算法，则用辗转相除法求两个正整数,m,，,n,最大条约数程序框图和程序分别怎样表示？,10/22,开始,输入,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,11/22,思索,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,，,知识探究（二）,:,更相减损术,12/22,思索,2:,上述求两个正整数最大条约数方法称为,更相减损术,.,普通地，用更相减损术求两个正整数,m,，,n,最大条约数，能够用什么逻辑结构来结构算法？其算法步骤怎样设计？,第一步，给定两个正整数,m,，,n(mn).,第二步，计算,m-n,所得差,k.,第三步，比较,n,与,k,大小，其中大者用,m,表 示，小者用,n,表示,.,第四步，若,m=n,，则,m,，,n,最大条约数等于,m,；不然，返回第二步,.,13/22,思索,3:,该算法程序框图怎样表示？,开始,输入,m,，,n,nk,？,m=n,是,输出,m,结束,mn,？,k=m,-,n,是,否,n=k,m=k,否,14/22,思索,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,否,15/22,“,更相减损术”在中国古代数学专著,九章算术,中记述为：,可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之,.,16/22,比较辗转相除法与更相减损术区分,（,1,）都是求最大条约数方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，尤其当两个数字大小区分较大时计算次数区分较显著。,（,2,）从结果表达形式来看，辗转相除法表达结果是以相除余数为,0,则得到，而更相减损术则以减数与差相等而得到,小结,17/22,理论迁移,例,1,分别用辗转相除法和更相减损术求,168,与,93,最大条约数,.,辗转相除法：,168=931+75,，,93=751+18,，,75=184+3,，,18=36.,18/22,更相减损术,: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.,19/22,例,2,求,325,，,130,，,270,三个数最大条约数,.,因为,325=1302+65,，,130=652,，,所以,325,与,130,最大条约数是,65.,因为,270=654+10,，,65=106+5,，,10=52,，,所以,65,与,270,最大条约数是,5.,故,325,，,130,，,270,三个数最大条约数是,5.,20/22,1.,辗转相除法，就是对于给定两个正整数，用较大数除以较小数，若余数不为零，则将余数和较小数组成新一对数，继续上面除法，直到大数被小数除尽为止，这时较小数即为原来两个数最大条约数,.,小结作业,2.,更相减损术，就是对于给定两个正整数，用较大数减去较小数，然后将差和较小数组成新一对数，继续上面减法，直到差和较小数相等，此时相等两数即为原来两个数最大条约数,.,21/22,作业：,P45,练习：,1.,P48,习题,1.3A,组：,1.,22/22,