算法案例—辗转相除、更相减损、秦九韶.pptVIP

第一步,给定两个正数m,n 第二步,计算m除以n所得到余数r 第三步,m=n,n=r 第四步,若r=0,则m,n的最大公约数等于m;否则返回第二步 算法案例 之 辗转相除法、更相减损术、 秦九韶算法 3 5 9 15 [问题1]：在小学，我们已经学过求最大公约数的知识，你能求出18与30的最大公约数吗？ 18 30 2 3 ∴18和30的最大公约数是2×3=6. 先用两个数公有的质因数连续去除,一直除到所得的商是互质数为止,然后把所有的除数连乘起来. 案例1 辗转相除法与更相减损术 〖创设情景，揭示课题〗 [问题2]:我们都是利用找公约数的方法来求 最大公约数，如果两个数比较大而且根据我 们的观察又不能得到一些公约数，我们又应 该怎样求它们的最大公约数？比如求8251与 6105的最大公约数? 1.辗转相除法: 例1 求两个正数8251和6105的最大公约数。 分析：8251与6105两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根据已有的知识即可求出最大公约数. 解：8251＝6105×1＋2146 显然8251与6105的最大公约数也必是2146的约数，同样6105与2146的公约数也必是8251的约数，所以8251与6105的最大公约数也是6105与2146的最大公约数。 完整的过程 8251=6105×1+2146 6105=2146×2+1813 2146=1813×1+333 1813=333×5+148 333=148×2+37 148=37×4+0 显然37是148和37的最大公约数，也就是8251和6105的最大公约数 思考：从上面的两个例子中可以看出计算的规律是什么？ S1：用大数除以小数 S2：除数变成被除数，余数变成除数 S3：重复S1，直到余数为0 练习1：利用辗转相除法求两数4081与20723的最大公约数. (53) 20723=4081×5+318; 4081=318×12+265; 318=265×1+53; 265=53×5+0. 运算了几次？？ 辗转相除法求最大公约数算法： 思考 ：需不需要比较m，n的大小？ 不需要 以上我们求最大公约数的方法就是辗转相除法。也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的。 否 开始 输入两个正数m,n r=m MOD n r=0? 输出m 结束 m=n n=r 是 程序框图 程序 例2 用更相减损术求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) 法一：84-72=12 72-12=60 60-12=48 48-12=24 24-12=12 法二：84÷2=42,72÷2=36 42÷2=21,36÷2=18 21÷3=7,18÷3=6 7-6=1 6-1=5 5-1=4 4-1=3 3-1=2 2-1=1 1×2×2×3=12 辗转相除法与更相减损术的比较: （1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主;计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。 （2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到. 秦九韶（1208年－1261年），南宋官员、数学家，与李冶、杨辉、朱世杰并称宋元数学四大家。 他是一位学识渊博、多才多艺的青年学者，时人说他“性极机巧，星象、音律、算术，以至营造等事，无不精究”。 历任琼州知府、司农丞。运用数学知识解决农民的实际问题. 秦九韶简介 秦九韶 在《九章算术》中，已经有求三角形公式“底乘高的一半”，在实际丈量土地面积时，由于土地的面积并不是的三角形，要找出它来并非易事。所以他们想到了三角形的三条边。如果这样做求三角形的面积也就方便多了。但是怎样根据三边的长度来求三角形的面积？直到南宋，我国著名的数学家秦九韶提出了“三斜求积术”.