1、讲解人： 时间：2020.6.1 M E N T A L H E A L T H C O U N S E L I N G P P T 1 . 3 算 法 案 例算 法 案 例 第1章 算法初步 人 教 版 高 中 数 学 必 修 3 3 2 9 6 问题1：在小学，我们已经学过求最大公约数的知识，你能求出45与30的最大公约数吗？ 45 30 5 3 45和30的最大公约数是53=15. 先用两个数公有的质因数连续去除,一直除到所得 的商是互质数为止,然后把所有的除数连乘起来. 创设情景，揭示课题 例1：求下面两个正整数的最大公约数： （1）求25和35的最大公约数; （2）求49和63的最大
2、公约数. 25 （1） 5 5 35 7 49 （2） 7 7 63 9 所以，25和35的最大公约数为5； 所以，49和63的最大公约数为7. 解答： 问题：求8251和6105的最大公约数 新知探究 辗转相除法 欧几里得 又名“欧几里得算法”，是已知的求最大公约数的最古老的算法，可追溯到3000年。最早出现 于欧几里得的几何原本，而在中国可以追溯到东汉出现的九章算术。 新知探究 第一步 用两数中较大的数除以较小的数，求得商和余数 8251=61051+2146 问题：求8251和6105的最大公约数 被除数 除数 余数 商 分析：6105和2146的公约数就是8215和6105的公约数,除
3、数和余数的公约数就是被除数和除数 的公约数。 因此，求8251和6105的最大公约数，只需求出6105和2146的公约数即可。 新知探究 辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是一个循环结构。 8251=61051+2146 6105=21462+1813 2146=18131+333 1813=3335+148 333=1482+37 148=374+0 a =b q r 思考：辗转相除法用哪种逻辑结构书写？ 新知探究 练习1：利用辗转相除法求两数4081与20723的最大公约数. (53) 20723=40815+318; 4081=31812+265; 318=265
4、1+53; 265=535+0. 新知探究 练习：用辗转相除法求下列两数的最大公约数： （1）（225，135） （2）（98，196） （3）（72，168） （4）（153，119） 45 98 24 17 新知探究 例2 求325，130，270三个数的最大公约数. 因为325=1302+65，130=652，所以325与130的最大公约数是65. 因为270=654+10，65=106+5，10=52，所以65与270最大公约数是5. 故325，130，270三个数的最大公约数是5. 思路分析：求三个数的最大公约数可以先求出两个数的最大公约数，第三个数与前两个数的最大 公约数的最大公约
5、数即为所求。 新知探究 例1：用辗转相除法求378和90的最大公约数 例2：用辗转相除法求1734，816和1343的最大公约数 18 17 新知探究 简介 更相减损术是出自九章算术的一种求最大公 约数的算法，它原本是为约分而设计的为约分而设计的。 但但它适用于任何任何需要求最大公约数的场合。 更相减损术 新知探究 更相减损术 九章算术 算理：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。 翻译如下： 第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。 第二步：用较大的数减较小的数，接着把所得的差与较小的数比较，再用大数
6、减小数。继续这个 操作，直到所得的减数和差相等为止。 则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。 新知探究 例2：求98与63的最大公约数 9863=35 633528 35287 28721 21714 1477 所以，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的最大公约数为：2213=52. 思考：若a,b都是偶数，如何用更相减损术求
7、最大公约数？ 新知探究 辗转相除法： 8251=61051+2146 6105=21462+1813 2146=18131+333 1813=3335+148 333=1482+37 148=374+0 更相减损术： 9863=35 633528 35287 28721 21714 1477 新知探究 【例 1】 用辗转相除法求下面两数的最大公约数，并用更相减损术检验你的结果： (1)80,36； (2)294,84. 思维突破：辗转相除法的结束条件是余数为 0，更相减损术的结束条件是差与减 数相等. 新知探究 解：(1)803628， 36844， 8420， 即 80 与 36 的最大公约
8、数是 4. 验证：803644， 44368,36828,28820， 20812,1284,844， 80 与 36 的最大公约数是 4. 新知探究 (2)29484342,84422， 即 294 与 84 的最大公约数是 42. 验证：294 与 84 都是偶数可同时除以2，即取147 与42 的最大公约数后再乘 2. 14742105,1054263， 634221,422121， 294 与 84 的最大公约数为 21242. 辗转相除法求最大公约数的步骤较少，而更相减 损术运算简易，因此解题时要灵活运用. 新知探究 辗转相除法和更相减损法都是用来求两个数的最大公约数的. 区别： 辗转相除法进行的是除法运算，即辗转相除，直到余数为0为止； 更相减损术进行的是减法运算，即辗转相减，直到减数和差相等为止. 辗转相除法与更相减损法的比较： 新知探究 讲解人： 时间：2020.6.1 M E N T A L H E A L T H C O U N S E L I N G P P T 感谢你的聆听感谢你的聆听 第1章 算法初步 人 教 版 高 中 数 学 必 修 3