1.4.1算法案例.ppt

1、1.3 算法案例 沈伍合,1理解辗转相除法与更相减损术中的数学原理，并能根 据这些原理进行算法分析。 2了解十进制转换为各种进位制的除k取余法，以及各种进 位制与十进制之间转换的规律，并理解其中的数学规律. 3. 对简单的案例能设计程序框图并写出算法程序,教学目的：,重点：1、理解辗转相除法与更相减损术求最大公约数的方法。 2、各进位制表示数的方法及各进位制之间的转换。 难点：把辗转相除法与更相减损术的方法、各 进位制转换成程序框 图与程序语言。,教学重难点：,问题1：在小学，我们已经学过求最大公约数的知识，你能求 出18与30的最大公约数吗？,3 5,9 15,18和30的最大公约数是23=

2、6.,2 18 30,3,先用两个数公有的质因数连续去除,一直除到所得的商是互质数 为止,然后把所有的除数连乘起来.,问题2:我们都是利用找公约数的方法来求最大公约数，如果 两个数比较大而且根据我们的观察又不能得到一些公 约数，我们又应该怎样求它们的最大公约数？比如求 8251与6105的最大公约数?,创设情境：,1、定义 所谓辗转相除法，就是对于给定的两个数，用较大的 数除以较小的数。若余数不为零，则将余数和较小的 数构成新的一对数，继续上面的除法，直到大数被小 数除尽，则这时较小的数就是原来两个数的最大公约数。,2、步骤,一、辗转相除法（欧几里得算法）：,第一步,给定两个正数m,n 第二步

3、,计算m除以n所得到余数r 第三步,m=n,n=r 第四步,若r=0,则m,n的最大公约数等于m;否则返回第二步,否,开始,输入两个正数m,n,r=m MOD n,r=0?,输出m,结束,m=n,n=r,是,INPUT “m,n=”;m,n DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m END,3、程序框图：,4、程序：,5、例题：,例1 求两个正数8251和6105的最大公约数。,解：,r=m MOD n,m = n,n = r,r=0?,是,否,37为8251与6105的最大公约数。,m = n q r,1、定义 我国早期解决求最大公约数问题的算法

4、，就是对于给 定的两个数，可半者半之， 不可半者，副置分母、 子 之数，以少减多，更相减损，求其等也，以等数约之。,第一步 任意给出两个正数；判断它们是否都是偶数。若是， 用2约简；若不是，执行第二步。,二、更相减损术：,第二步 以较大的数减去较小的数，接着把较小的数与所得的 差比较，并以大数减小数。继续这个操作，直到所得 的数相等为止，则这个数（等数）就是所求的最大公 约数。,2、步骤,INPUT m，n WHILE mn kmn IF nk THEN mn nk ELSE mk END IF WEND PRINT m END,3、程序框图：,4、程序：,例2 用更相减损术求98与63的最大

5、公约数。,解：由于63不是偶数，把98和63以大数减小数，并辗转相减。,即：986335; 633528; 35287; 28721; 21714; 1477.,98与63的最大公约数是7。,5、例题：,3192611(余58),261584(余29),58292(余0),319与261的最大公约数为29,更相减损术：,31926158,26158203,20358145,1455887,875829,582929,29290,319与261的最大公约数是29,例3 分别用辗转相除法和更相减损术求261和319的最大公约数,解：,辗转相除法：,辗转相除法与更相减损术的比较：,（1）都是求最大公约数的方法，计算上辗转相除法以除法为主， 更相减损术以减法为主;计算次数上辗转相除法计算次数相 对较少，特别当两个数字大小区别较大时计算次数的区别 较明显。 （2）从结果体现形式来看，辗转相除法体现结果是以相除余数 为0则得到，而更相减损术则以减数与差相等而得到。,小结：,1辗转相除法，就是对于给定的两个正整数，用较大的数除以 较小的数，若余数不为零，则将余数和较小的数构成新的一 对数，继续上面的除法，直到大数被小数除尽为止，这时的 较小的数即为原来两个数的最大公约数。,2更相减损术，就是对于给定的两个正整数，用较