2020-2021学年1.3 算法与案例图片课件ppt

这是一份2020-2021学年1.3 算法与案例图片课件ppt，共20页。PPT课件主要包含了创设情景揭示课题，新知探究，辗转相除法，欧几里得，更相减损术等内容，欢迎下载使用。
[问题1]：在小学，我们已经学过求最大公约数的知识，你能求出45与30的最大公约数吗？
∴45和30的最大公约数是5×3=15.
先用两个数公有的质因数连续去除,一直除到所得的商是互质数为止,然后把所有的除数连乘起来.
例1：求下面两个正整数的最大公约数：
（1）求25和35的最大公约数;（2）求49和63的最大公约数.
所以，25和35的最大公约数为5；
所以，49和63的最大公约数为7.
问题：求8251和6105的最大公约数
——又名“欧几里得算法”，是已知的求最大公约数的最古老的算法，可追溯到3000年。最早出现于欧几里得的《几何原本》，而在中国可以追溯到东汉出现的《九章算术》。
第一步 用两数中较大的数除以较小的数，求得商和余数 8251=6105×1+2146
分析：6105和2146的公约数就是8215和6105的公约数,除数和余数的公约数就是被除数和除数的公约数。因此，求8251和6105的最大公约数，只需求出6105和2146的公约数即可。
辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是一个循环结构。
a =b× q ＋ r
思考：辗转相除法用哪种逻辑结构书写？
练习1：利用辗转相除法求两数4081与20723的最大公约数.
20723=4081×5+318;4081=318×12+265;318=265×1+53;265=53×5+0.
练习：用辗转相除法求下列两数的最大公约数：（1）（225，135） （2）（98，196）（3）（72，168） （4）（153，119）
例2 求325，130，270三个数的最大公约数.
因为325=130×2+65，130=65×2，所以325与130的最大公约数是65.
因为270=65×4+10，65=10×6+5，10=5×2，所以65与270最大公约数是5.
故325，130，270三个数的最大公约数是5.
思路分析：求三个数的最大公约数可以先求出两个数的最大公约数，第三个数与前两个数的最大公约数的最大公约数即为所求。
例1：用辗转相除法求378和90的最大公约数
例2：用辗转相除法求1734，816和1343的最大公约数
更相减损术是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的。 但它适用于任何需要求最大公约数的场合。
更相减损术 ——《九章算术》
算理：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。
翻译如下： 　　第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。 　第二步：用较大的数减较小的数，接着把所得的差与较小的数比较，再用大数减小数。继续这个操作，直到所得的减数和差相等为止。 　则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。 　　
例2：求98与63的最大公约数
98－63=3563－35＝2835－28＝728－7＝2121－7＝1414－7＝7
所以，98和63的最大公约数是7.
例3、用更相减损术求260和104的最大公约数。 　　解：由于260和104均为偶数，首先用2约简得到130和52，再用2约简得到65和26。 　　把65和26辗转相减： 　　 65-26=39 　 39-26=13 　 26-13=13 　所以，260与104的最大公约数为：2×2×13=52.
思考：若a,b都是偶数，如何用更相减损术求最大公约数？
辗转相除法：8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0
更相减损术：98－63=3563－35＝2835－28＝728－7＝2121－7＝1414－7＝7
【例 1】 用辗转相除法求下面两数的最大公约数，并用更相减损术检验你的结果：
思维突破：辗转相除法的结束条件是余数为 0，更相减损术的结束条件是差与减数相等.
解：(1)80＝36×2＋8，36＝8×4＋4，8＝4×2＋0，
即 80 与 36 的最大公约数是 4.验证：80－36＝44，
44－36＝8,36－8＝28,28－8＝20，20－8＝12,12－8＝4,8－4＝4，∴80 与 36 的最大公约数是 4.
(2)294＝84×3＋42,84＝42×2，即 294 与 84 的最大公约数是 42.
验证：∵294 与 84 都是偶数可同时除以2，即取147 与42
的最大公约数后再乘 2.
147－42＝105,105－42＝63，63－42＝21,42－21＝21，
∴294 与 84 的最大公约数为 21×2＝42.
辗转相除法求最大公约数的步骤较少，而更相减
损术运算简易，因此解题时要灵活运用.
辗转相除法和更相减损法都是用来求两个数的最大公约数的. 　区别：辗转相除法进行的是除法运算，即辗转相除，直到余数为0为止；更相减损术进行的是减法运算，即辗转相减，直到减数和差相等为止.
辗转相除法与更相减损法的比较：