算法案例1-辗转相除法与相减损术市公开课一等奖省赛课微课金奖课件

1.3算法案例第1页1.3.4十进制化K进制1.3.1辗转相除法和更相减损术1.3.2秦九韶算法1.3.3K进制化十进制1.3算法案例第2页1.3.1辗除法和更相减损术第3页一、辗转相除法

思索1:18与30最大条约数是多少？你是怎样得到？

先用两个数公有质因数连续去除，一直除到所得商是互质数为止，然后把全部除数连乘起来即为最大条约数.第4页

思索2:对于8251与6105这两个数，它们最大条约数是多少？你是怎样得到？

因为它们公有质因数较大，利用上述方法求最大条约数就比较困难.有没有其它方法能够较简单找出它们最大条约数呢？第5页

思索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.333=148×2+37，1813=333×5+148，8251=6105×1+2146，6105=2146×2+1813，第6页

上述求两个正整数最大条约数方法称为辗转相除法或欧几里得算法.第一步，给定两个正整数m，n(m>n).第二步，计算m除以n所得余数r.第三步，m=n，n=r.

第四步，若r=0，则m，n最大条约数等于m；不然，返回第二步.

思索5:你能把辗转相除法编成一个计算机程序吗？第7页程序框图开始输入m，n求m除以n余数rm=nn=rr=0？是输出m结束否INPUTm，nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND第8页

思索6:假如用当型循环结构结构算法，则用辗转相除法求两个正整数m、n最大条约数程序框图和程序分别怎样表示？第9页开始输入m，n求m除以n余数rm=nn>0？否输出m结束是n=rINPUTm，nWHILEn>0r=mMODnm=nn=rWENDPRINTmEND第10页二、更相减损术

《九章算术》是中国古代数学专著，其中“更相减损术”也能够用来求两个数最大条约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也.以等数约之.”意思是：

第一步：任意给定两个正整数，判断它们是否都是偶数.若是，用2约简；若不是，执行第二步.

第二步：以较大数减去较小数，接着把差与较小数比较，并以大数减小数.继续这个操作，直到所得数相等为止，则这个等数或这个数与约简数乘积就是所求最大条约数.第11页例1：用更相减损术求98与63最大条约数.98-63=35，14-7=7.21-7=14，28-7=21，35-28=7，63-35=28，因为63不是偶数，所以所以最大条约数是7.第12页

例2分别用辗转相除法和更相减损术求168与93最大条约数.168=93×1+75，93=75×1+18，75=18×4+3，18=3×6.辗转相除法：第13页更相减损术: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.第14页

练习:用更相减损术求两个正整数m，n最大条约数，能够用什么逻辑结构来结构算法？其算法步骤怎样设计？

第一步，给定两个正整数m，n(m>n).

第二步，计算m-n所得差k.

第三步，比较n与k大小，其中大者用m表示，小者用n表示.

第四步，若m=n，则m，n最大条约数等于m；不然，返回第二步.

讨论:该算法程序框图怎样表示？第15页开始输入m，nn>k？m=n是输出m结束m≠n？k=m-n是否n=km=k否

讨论:该程序框图对应程序怎样表述？第16页INPUTm，nWHILEm≠nk=m-nIFn>kTHENm=nn=kELSEm=kENDIFWENDPRINTmEND开始输入m，nn>k？m=n是输出m结束m≠n