（算法案例）人教版高中数学必修三教学课件（第1.3课时）

1、讲解人：精品课件 时间：2020.6.1MENTAL HEALTH COUNSELING PPT1.3算法案例第1章 算法初步人教版高中数学必修3第一页，共二十页。3 29 6问题1：在小学，我们已经学过求最大公约数的知识，你能求出45与30的最大公约数吗？45 305345和30的最大公约数是53=15.先用两个数公有的质因数连续去除,一直除到所得的商是互质数为止,然后把所有的除数连乘起来.创设情景，揭示课题第二页，共二十页。例1：求下面两个正整数的最大公约数：（1）求25和35的最大公约数;（2）求49和63的最大公约数.25（1）5535749（2）77639所以，25和35的最大公约数

2、为5；所以，49和63的最大公约数为7.解答：问题：求8251和6105的最大公约数 新知探究第三页，共二十页。辗转相除法欧几里得又名“欧几里得算法”，是已知的求最大公约数的最古老的算法，可追溯到3000年。最早出现于欧几里得的几何原本，而在中国可以追溯到东汉出现的九章算术。新知探究第四页，共二十页。第一步 用两数中较大的数除以较小的数，求得商和余数 8251=61051+2146问题：求8251和6105的最大公约数 被除数除数余数商分析：6105和2146的公约数就是8215和6105的公约数,除数和余数的公约数就是被除数和除数的公约数。因此，求8251和6105的最大公约数，只需求出61

3、05和2146的公约数即可。新知探究第五页，共二十页。辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是一个循环结构。8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0a =b q r思考：辗转相除法用哪种逻辑结构书写？新知探究第六页，共二十页。练习1：利用辗转相除法求两数4081与20723的最大公约数. (53)20723=40815+318;4081=31812+265;318=2651+53;265=535+0.新知探究第七页，共二十页。练习：用辗转相除法求下列两数的最

4、大公约数：（1）（225，135） （2）（98，196）（3）（72，168） （4）（153，119）45982417新知探究第八页，共二十页。 例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.思路分析：求三个数的最大公约数可以先求出两个数的最大公约数，第三个数与前两个数的最大公约数的最大公约数即为所求。新知探究第九页，共二十页。例1：用辗转相除法求378和90的最大

5、公约数例2：用辗转相除法求1734，816和1343的最大公约数1817新知探究第十页，共二十页。简介更相减损术是出自九章算术的一种求最大公约数的算法，它原本是为约分而设计的。 但它适用于任何需要求最大公约数的场合。更相减损术新知探究第十一页，共二十页。更相减损术 九章算术算理：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。翻译如下： 第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。 第二步：用较大的数减较小的数，接着把所得的差与较小的数比较，再用大数减小数。继续这个操作，直到所得的减数和差相等为止。 则第一步中约掉的

6、若干个2与第二步中等数的乘积就是所求的最大公约数。 新知探究第十二页，共二十页。例2：求98与63的最大公约数9863=356335283528728721217141477所以，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+21466105=21462+18132146=18131+3331813=3335+148333=1482+37148=374+0更相减损术：9863=356335283528728721217141477区别？新知探究第十五页，共二十页。【例 1】 用辗转相除法求下面两数的最大公约数，并用更相减损术检验你的结果：(1)80,36；(2)294,84.思维突破：辗转相除法的结束条件是余数为 0，更相减损术的结束条件是差与减数相等.新知探究第十六页，共二十页。解：(1)803628，36844，8420，即 80 与 36 的最大公约数是 4.验证：803644，44

8、368,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为止；更相减损术进行的是减法运算，即