算法案例
图片预览
文档简介
课件24张PPT。1.3 算 法 案 例案例1 辗转相除法与更相减损术1. 思考： 小学学过的求两个数最大公约数的方法？ 先用两个公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来.问题情境 求18和30的最大公约数 结论18和30的最大公约数为618和30的最小公倍数为90 (牢记方法!)1、求两个正整数的最大公约数（1）求25和35的最大公约数
（2）求49和63的最大公约数所以，25和35的最大公约数为5所以，49和63的最大公约数为72、除了用这种方法外还有没有其它方法？算出8256和6105的最大公约数. 辗转相除法 算法案例之求最大公约数求以下几组正整数的最大公约数。
(注：若整数m和n满足n整除m，则（m,n）=n。用（m,n）来表示
m和n的最大公约数。)
（1）（18，30） （2）（24，16）
（3）（63，63） （4）（72，8）
（5）（301，133 ）想一想，如何求8251与6105的最大公约数？ 例、求18与24的最大公约数：6；8；63；8；7；短除法定理： 已知m,n,r为正整数，若m=nq+r（0≤r r=m-nq …… ②例1、求8251和6105的最大公约数。148=37 ×4=378251=6105×1+2146 （8251，6105）
=（6105，2146）6105=2146 ×2+1813=（2146，1813）2146=1813 ×1+333=（1813，333）1813=333 ×5+148=（333，148）333=148 ×2+37=（148，37）解：练习：用辗转相除法求下列两数的最大公约数：
（1）（225，135） （2）（98，196）
（3）（72，168） （4）（153，119）459824178251和6105的最大公约数解：
8251=6105×1+2146
6105=2146 ×2+1813
2146=1813 ×1+333
1813=333 ×5+148
333=148 ×2+37
148=37 ×4（8251，6105）
=（6105，2146）
=（2146，1813）
=（1813，333）
=（333，148）
=（148，37）
=37关系式m=np+r中m,n,r得取值变化情况82516105214661052146214618131813333181333314814833337148370辗转相除法求两个数的最大公约数，其算法可以描述如下：辗转相除法是一个反复执行直到余数等于0停止的步骤，
这实际上是一个循环结构 思考：辗转相除直到何时结束？主要运用的是哪种算法结构？如此循环，直到得到结果。① 输入两个正整数m和n；② 求余数r：计算m除以n，将所得余数存放到变量r中；③更新被除数和余数：m=n，n=r。④判断余数r是否为0：若余数为0则输出结果，否则转
向第②步继续循环执行。程序： INPUT “m，n=”;m,n DO
r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m END 练 阅读下列程序：若输入的两个数m=428，n=284，求计算机输出的数.4更相减损术《九章算术》——更相减损术 算理：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。第一步：任意给定两个正整数；判断他们是否都是偶数。若是，则用2约简；若不是则执行第二步。第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数就是所求的最大公约数。2、更相减损术（1）算理：所谓更相减损术，就是对于给定的两个数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，再用较大的数减去较小的数，反复执行此步骤直到差数和较小的数相等，此时相等的两数便为原来两个数的最大公约数。更相减损是一个反复执行直到减数等于差时
停止的步骤，这实际也是一个循环结构 思考：更相减损直到何时结束？
运用的是哪种算法结构？（2）算法步骤第一步：输入两个正整数a,b(a>b);
第二步：若a不等于b ,则执行第三步；否则转到第五步；
第三步：把a-b的差赋予r;
第四步：如果b>r, 那么把b赋给a,把r赋给b;否则把r赋给a，执行第二步；
第五步：输出最大公约数b.（3）程序框图（4）程序INPUT “a,b=“;a,b
WHILE a<>b
r=a-b
IF b>r THEN
a=b
b=r
ELSE
a=r
END IF
WEND
PRINT b
END输入a,b是否 b=ra=br=a-ba=r否是例3 用更相减损术求98与63的最大公约数解：由于63不是偶数，把98和63以大数减小数，并辗转相减 98－63＝35 63－35＝28 35－28＝7 28－7＝21
21－7＝21
14－7＝7所以，98和63的最大公约数等于7 先约简，再求21与18的最大公约数,然后乘以两次约简的质因数4练习：用更相减损术求下列两数的最大公约数：
（1）（225，135） （2）（98，196）
（3）（72，168） （4）（153，119）45982417例3、求324、243、135这三个数的最大公约数。思路分析：求三个数的最大公约数可以先求出两个数的最大公约数，第三个数与前两个数的最大公约数的最大公约数即为所求。比较辗转相除法与更相减损术的区别
（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。
（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到小结再见
（2）求49和63的最大公约数所以，25和35的最大公约数为5所以，49和63的最大公约数为72、除了用这种方法外还有没有其它方法？算出8256和6105的最大公约数. 辗转相除法 算法案例之求最大公约数求以下几组正整数的最大公约数。
(注：若整数m和n满足n整除m，则（m,n）=n。用（m,n）来表示
m和n的最大公约数。)
（1）（18，30） （2）（24，16）
（3）（63，63） （4）（72，8）
（5）（301，133 ）想一想，如何求8251与6105的最大公约数？ 例、求18与24的最大公约数：6；8；63；8；7；短除法定理： 已知m,n,r为正整数，若m=nq+r（0≤r
=（6105，2146）6105=2146 ×2+1813=（2146，1813）2146=1813 ×1+333=（1813，333）1813=333 ×5+148=（333，148）333=148 ×2+37=（148，37）解：练习：用辗转相除法求下列两数的最大公约数：
（1）（225，135） （2）（98，196）
（3）（72，168） （4）（153，119）459824178251和6105的最大公约数解：
8251=6105×1+2146
6105=2146 ×2+1813
2146=1813 ×1+333
1813=333 ×5+148
333=148 ×2+37
148=37 ×4（8251，6105）
=（6105，2146）
=（2146，1813）
=（1813，333）
=（333，148）
=（148，37）
=37关系式m=np+r中m,n,r得取值变化情况82516105214661052146214618131813333181333314814833337148370辗转相除法求两个数的最大公约数，其算法可以描述如下：辗转相除法是一个反复执行直到余数等于0停止的步骤，
这实际上是一个循环结构 思考：辗转相除直到何时结束？主要运用的是哪种算法结构？如此循环，直到得到结果。① 输入两个正整数m和n；② 求余数r：计算m除以n，将所得余数存放到变量r中；③更新被除数和余数：m=n，n=r。④判断余数r是否为0：若余数为0则输出结果，否则转
向第②步继续循环执行。程序： INPUT “m，n=”;m,n DO
r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m END 练 阅读下列程序：若输入的两个数m=428，n=284，求计算机输出的数.4更相减损术《九章算术》——更相减损术 算理：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。第一步：任意给定两个正整数；判断他们是否都是偶数。若是，则用2约简；若不是则执行第二步。第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数就是所求的最大公约数。2、更相减损术（1）算理：所谓更相减损术，就是对于给定的两个数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，再用较大的数减去较小的数，反复执行此步骤直到差数和较小的数相等，此时相等的两数便为原来两个数的最大公约数。更相减损是一个反复执行直到减数等于差时
停止的步骤，这实际也是一个循环结构 思考：更相减损直到何时结束？
运用的是哪种算法结构？（2）算法步骤第一步：输入两个正整数a,b(a>b);
第二步：若a不等于b ,则执行第三步；否则转到第五步；
第三步：把a-b的差赋予r;
第四步：如果b>r, 那么把b赋给a,把r赋给b;否则把r赋给a，执行第二步；
第五步：输出最大公约数b.（3）程序框图（4）程序INPUT “a,b=“;a,b
WHILE a<>b
r=a-b
IF b>r THEN
a=b
b=r
ELSE
a=r
END IF
WEND
PRINT b
END输入a,b是否 b=ra=br=a-ba=r否是例3 用更相减损术求98与63的最大公约数解：由于63不是偶数，把98和63以大数减小数，并辗转相减 98－63＝35 63－35＝28 35－28＝7 28－7＝21
21－7＝21
14－7＝7所以，98和63的最大公约数等于7 先约简，再求21与18的最大公约数,然后乘以两次约简的质因数4练习：用更相减损术求下列两数的最大公约数：
（1）（225，135） （2）（98，196）
（3）（72，168） （4）（153，119）45982417例3、求324、243、135这三个数的最大公约数。思路分析：求三个数的最大公约数可以先求出两个数的最大公约数，第三个数与前两个数的最大公约数的最大公约数即为所求。比较辗转相除法与更相减损术的区别
（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。
（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到小结再见