13算法案例一.ppt

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

1、Page 1Page 2复习回顾复习回顾1 1、在程序框图中算法的基本逻辑结构有哪几种？在程序设计中基在程序框图中算法的基本逻辑结构有哪几种？在程序设计中基本的算法语句有哪几种？本的算法语句有哪几种？2 2、什么是公约数？什么是最大公约数？什么是公约数？什么是最大公约数？公约数公约数,就是就是能同时整除几个整数的整数能同时整除几个整数的整数Page 3思考：思考：18与与30的最大公约数是多少？你是怎样得到的？的最大公约数是多少？你是怎样得到的？先用两个数公有的质因数连续去除，一直除到所得的商是互先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来即为最大公约

2、数质数为止，然后把所有的除数连乘起来即为最大公约数.18302915335用公有质因数用公有质因数2除除用公有质因数用公有质因数3除除3和和5互质，不除了互质，不除了得：得：18和和24最大公约数是：最大公约数是：236 思考：思考：如果两个数共有的质因数较大时，如如果两个数共有的质因数较大时，如8251与与6105，又如何求，又如何求最大公约数？最大公约数？辗转相除法辗转相除法（欧几里得法）（欧几里得法）更相减损术更相减损术Page 4辗转相除法辗转相除法 如果求如果求8251与与6105的最大公约数？的最大公约数？第一步第一步 用两数中较大的数除以较小的数，求得商和余数用两数中较大的数除以

3、较小的数，求得商和余数这时，这时，8251和和6105的公约数就是的公约数就是6105和和2146的公约数的公约数第二步第二步 对对6105和和2146重复第一步的做法重复第一步的做法6105=21462+1813，2146=18131+333，1813=3335+148，333=1482+37，148=374+0.8251=61051+2146 显然，显然，37是是148和和37的最大公约数，的最大公约数，也就是也就是8251和和6105的最大公约数的最大公约数 Page 5练习练习：用辗转相除法求：用辗转相除法求225和和135的最大公约数的最大公约数225=1351+90，135=901

4、+45，90=452+0.显然，显然，45是是90和和45的最大公约数，也就是的最大公约数，也就是225和和135的最大公约数的最大公约数 思考思考：从上面的两个例子可以看出计算的规律是什么？：从上面的两个例子可以看出计算的规律是什么？S1：用大数除以小数：用大数除以小数S2：除数变成被除数，余数变成除数：除数变成被除数，余数变成除数S3：重复：重复S1，直到余数为，直到余数为0Page 6 辗转相除法是一个反复执行直到余数等于辗转相除法是一个反复执行直到余数等于0停止的步骤，停止的步骤，这实际上是一个循环结构这实际上是一个循环结构.辗转相除法求两个数的最大公约数，其算法可以描述如下：辗转相除

5、法求两个数的最大公约数，其算法可以描述如下：一、给定两个正整数一、给定两个正整数m和和n.二、计算二、计算m除以除以n的余数的余数r.三、三、m=n，n=r.四、若四、若r=0,则则m，n的最大公约数等于的最大公约数等于m；否则返回第二步；否则返回第二步.Page 7开始开始输入输入m,n r=mMODn m=nn=rr=0？辗转相除除法的程序框图与程序辗转相除除法的程序框图与程序输出输出m结束结束是是否否INPUT m,nDO r=mMODn m=n n=rLOOP UNTIL r=0PRINT mENDPage 8更相减损术更相减损术算理：算理：可半者半之，不可半者，副置分母、子之数，以少

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

7、简的数的乘积就是所 求的最大公约数求的最大公约数。Page 9例例1 1、用更相减损术求、用更相减损术求98与与63的最大公约数的最大公约数解：由于解：由于63不是偶数，把不是偶数，把98和和63以大数减小数，并辗转相减。以大数减小数，并辗转相减。98-63=3563-35=2835-28=728-7=2121-7=1414-7=7所以，所以，98和和63的最大公约数等于的最大公约数等于7。Page 10例例2 2、求、求325，130，270三个数的最大公约数三个数的最大公约数 因为因为325=1302+65，130=652，所以，所以325与与130的最大公约数的最大公约数是是65.因为因

8、为270=654+10，65=106+5，10=52，所以，所以65与与270最大公最大公约数是约数是5.故故325，130，270三个数的最大公约数是三个数的最大公约数是5.Page 11练习练习：用更相减损术和辗转相除法求下列两数的最大公约数：用更相减损术和辗转相除法求下列两数的最大公约数：1 1）225和和1352 2）98和和1963 3）72和和1684 4）153和和11945982417Page 12小结小结辗转相除法与更相减损术的区别：辗转相除法与更相减损术的区别：1 1、都是求最大公约数的方法，计算上辗转相除法以除法为主，更、都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。特别当两个数字大小区别较大时计算次数的区别较明显。2 2、从结果体现形式来看，辗转相除法体现结果是以相除余数为、从结果体现形式来看，辗转相除法体现结果是以相除余数为0 0而而得到，而更相减损术则以减数与差相等而得到的。得到，而更相减损术则以减数与差相等而得到的。