13算法案例课.ppt

《13算法案例课.ppt》由会员分享，可在线阅读，更多相关《13算法案例课.ppt（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、（第一课（第一课时）时）1、求两个正整数的最大公约数、求两个正整数的最大公约数(短除法短除法)（1）求）求25和和35的最大公约数的最大公约数（2）求）求225和和135的最大公约数的最大公约数2、求、求8251和和6105的最大公约数的最大公约数 25（1） 55357所以，所以，25和和35的最大公约数为的最大公约数为5所以，所以，225和和135的最大公约数为的最大公约数为45辗转相除法（欧几里得算法）辗转相除法（欧几里得算法）观察用辗转相除法求观察用辗转相除法求8251和和6105的最大公约数的过程的最大公约数的过程 第一步第一步 用两数中较大的数除以较小的数，求得用两数中较大的数除以

2、较小的数，求得商商和和余数余数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+3

3、331813=3335+148333=1482+37148=374+0例例2 用辗转相除法求用辗转相除法求225和和135的最大公约数的最大公约数225=1351+90135=901+4590=452显然显然37是是148和和37的最大公约的最大公约数，也就是数，也就是8251和和6105的最的最大公约数大公约数 显然显然45是是90和和45的最大公约数，也就是的最大公约数，也就是225和和135的最大公约数的最大公约数 思考思考1：从上面的两个例子可以看出计：从上面的两个例子可以看出计算的规律是什么？算的规律是什么？ S1：用大数除以小数：用大数除以小数S2：除数变成被除数，余数变成除数：除

4、数变成被除数，余数变成除数S3：重复：重复S1，直到余数为，直到余数为0思考：思考：你能把辗转相除法求任意两个正整数你能把辗转相除法求任意两个正整数m,n(mn)的最大的最大公约数编成一个计算机程序吗？公约数编成一个计算机程序吗？写算法步骤：写算法步骤： 第一步，给定两个正整数第一步，给定两个正整数m,nm,n 第二步，计算第二步，计算mm除以除以n n的余数为的余数为r r 第三步，第三步，m=n,n=rm=n,n=r 第四步，若第四步，若r=0,r=0,则则m,nm,n的最大公约数等于的最大公约数等于m,m,否则，返回第二步。否则，返回第二步。 辗转相除法是一个反复执行直到余数等于辗转相除

5、法是一个反复执行直到余数等于0停止的步骤，停止的步骤，这实际上是一个循环结构。这实际上是一个循环结构。8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0m = n q r用程序框图表示出右边的过程用程序框图表示出右边的过程r=m MOD nm = nn = rr=0?是否INPUT m , nDO r=m mod n m=n n=rLOOP UNTIL r=0PRINT mEnd画程序框图画程序框图 关键：确定框图中所用到的结构 确定循环结构：确定循环结构：1，初始化条件：，初始化条件：

6、m,n2，确定循环体：，确定循环体：m=nq+r m=n,n=r3，设置循环控制条件：，设置循环控制条件：r=0 循环结构的类型选择：直到型或当型循环结构的类型选择：直到型或当型编制程序: 直到型： INPUT m,n DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m END当型结构：INPUT m,nr=1WHILE r 0 r=m MOD n m=n n=rWENDPRINT mEND只要只要r0都可以都可以九章算术九章算术更相减损术更相减损术 算理：算理：可半者半之，不可半者，副置分母、子之数，以少可半者半之，不可半者，副置分母、子之数，以少减多，更

7、相减损，求其等也，以等数约之。减多，更相减损，求其等也，以等数约之。第一步：第一步：任意给定两个正整数；判断他们是否都是偶数。任意给定两个正整数；判断他们是否都是偶数。若是，则用若是，则用2约简；若不是，则执行第二步。约简；若不是，则执行第二步。第二步：第二步：以以较大的数减较小的数较大的数减较小的数，接着把所得的差与较小的数，接着把所得的差与较小的数比较，并以比较，并以大数减小数大数减小数。继续这个操作，直到所得的。继续这个操作，直到所得的减数和差减数和差相等为止相等为止，则这个等数或这个等数与约简的数的乘积就是所求，则这个等数或这个等数与约简的数的乘积就是所求的最大公约数。的最大公约数。例

8、例3 用更相减损术求用更相减损术求 225 与与 135 的最大公约数的最大公约数解：由于两数不是偶数，把解：由于两数不是偶数，把225和和135以大数减小数，以大数减小数， 并辗转相减并辗转相减 225135901359045904545所以，所以，225和和135的最大公约数等于的最大公约数等于45INPUT a,bWHILE ab IF ab THEN a=a-b ELSE b=b-a END IFWENDPRINT aEND九章算术九章算术更相减损术的算法程序语句：更相减损术的算法程序语句： 练习：练习：用辗转相除法求用辗转相除法求 294 与与84的最大公约数，再的最大公约数，再用更相减损术验证。用更相减损术验证。思考：求三个数：思考：求三个数：168，54，264的最大公约数。的最大公约数。