算法案例.ppt

算法案例唐万树算法案例辗转相除法和更相减损术 1、求两个正整数的最大公约数(1)求 18 和 30 的最大公约数 18 和 30 的最大公约数为 6 记: ( 18 , 30 )=6 求公因数的方法:先用两个数公有的质因数连续去除,一直除到所得的商是互质数为止,然后把所有的除数连乘起来. 2 、求 8251 和 6105 的最大公约数 ( 8251 ,6105 )=? 辗转相除法(欧几里得算法) 观察用辗转相除法求 8251 和 6105 的最大公约数的过程第一步用两数中较大的数除以较小的数,求得商和余数 8251=6105 × 1+2146 结论: 8251 和 6105 的公约数就是 6105 和 2146 的公约数,求 8251 和 6105 的最大公约数,只要求出 6105 和 2146 的公约数就可以了。 (8251 , 6105 )=(6105 , 2146 ) 第二步对 6105 和 2146 重复第一步的做法 6105=2146 × 2 + 1813 同理 6105 和 2146 的最大公约数也是 2146 和 1813 的最大公约数。(8251 , 6105 )=(6105 , 2146 ) =(2146 ,1813) 完整的过程 333=148 × 2+37 148=37 × 4+0 8251=6105 × 1+2146 6105=2146 × 2+1813 2146=1813 × 1+333 1813=333 × 5+148 显然 37 是 148 和 37 的最大公约数,也就是 8251 和 6105 的最大公约数例 2 用辗转相除法求 225 和 135 的最大公约数思考 1:从上面的两个例子可以概括出计算的规则? S1 :用大数除以小数 S3 :重复 S1 ,直到余数为 0 S2 :除数变成被除数,余数变成除数 225=135 × 1+90 135=90 × 1+45 90=45 × 2+0 显然 45 是 90 和 45 的最大公约数,也就是 225 和 135 的最大公约数辗转相除法是一个反复执行直到余数等于 0停止的步骤,这实际上是一个循环结构。 m = n × q + r 用程序框图表示出右边的过程否 r=m MOD n m = n n = r r=0? 是辗转相除法的程序框图开始输入 m,n r=m MOD n m=n n=r r=0? 输出 m结束是否 INPUT “输入 m,n ”; m,n DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT “最大公约数是: ”;m END 《九章算术》——更相减损术算理: 可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也,以等数约之。第一步: 任意给定两个正整数;判断他们是否都是偶数。若是,则用 2约简;若不是则执行第二步。第二步: 以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等为止,则这个等数就是所求的最大公约数。例 3 用更相减损术求 98 与 63 的最大公约数解:由于 63 不是偶数,把 98 和 63 以大数减小数,并辗转相减 98 - 63 = 35 63 - 35 = 28 35 - 28 =7 28 -7= 21 21 -7= 14 14 -7=7所以, 98 和 63 的最大公约数等于 7 练习 2:用更相减损术求两个正数 84与72的最大公约数。(12) : (1)都是求最大公约数的方法,计算上辗转相除法以除法为主,更相减损术以减法为主; 计算次数上辗转相除法计算次数相对较少,特别当两个数字大小区别较大时计算次数的区别较明显。(2)从结果体现形式来看,辗转相除法体现结果是以相除余数为 0则得到,而更相减损术则以减数与差相等而得到.