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

讲解人：办公资源时间：2020.6.1MENTALHEALTHCOUNSELINGPPT1.3算法案例第1章算法初步人教版高中数学必修33296[问题1]：在小学，我们已经学过求最大公约数的知识，你能求出45与30的最大公约数吗？453053∴45和30的最大公约数是5×3=15.先用两个数公有的质因数连续去除,一直除到所得的商是互质数为止,然后把所有的除数连乘起来.创设情景，揭示课题例1：求下面两个正整数的最大公约数：（1）求25和35的最大公约数;（2）求49和63的最大公约数.25（1）5535749（2）77639所以，25和35的最大公约数为5；所以，49和63的最大公约数为7.解答：问题：求8251和6105的最大公约数新知探究辗转相除法欧几里得——又名“欧几里得算法”，是已知的求最大公约数的最古老的算法，可追溯到3000年。最早出现于欧几里得的《几何原本》，而在中国可以追溯到东汉出现的《九章算术》。新知探究第一步用两数中较大的数除以较小的数，求得商和余数8251=6105×1+2146问题：求8251和6105的最大公约数被除数除数余数商分析：6105和2146的公约数就是8215和6105的公约数,除数和余数的公约数就是被除数和除数的公约数。因此，求8251和6105的最大公约数，只需求出6105和2146的公约数即可。新知探究辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是一个循环结构。8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0a=b×q＋r思考：辗转相除法用哪种逻辑结构书写？新知探究练习1：利用辗转相除法求两数4081与20723的最大公约数.(53)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）45982417新知探究例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的最大公约数1817新知探究简介更相减损术是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的。但它适用于任何需要求最大公约数的场合。更相减损术新知探究更相减损术——《九章算术》算理：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。翻译如下：第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用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=3939-26=1326-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】用辗转相除法求下面两数的最大公约数，并用更相减损术检验你的结果：(1)80,36；(2)294,84.思维突破：辗转相除法的结束条件是余数为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为止；更相减损术进行的是减法运算，即辗转相减，直到减数和差相等为止.辗转相除法与更相减损法的比较：新知探究感谢您下载68素材平台上提供的PPT作品，为了您和68素材以及原创作者的利益，请勿复制、传播、销售；素材均来源于网络用户分享，故68素材不具备充分的监控能力来审查图片是否存在侵权等情节。68素材不拥有此类图片的版权，本站所有资源仅供学习与交流，不得用于任何商业用途的范围，用户应自觉遵守著作权法及其他相关法律的规定，不得侵犯本网站及权利人的合法权利，给68素材和任何第三方造成损失的，侵权用户应负全部责任。版权声明讲解人：办公资源时间：2020.6.1MENTALHEALTHCOUNSELINGPPT感谢你的聆听第1章算法初步人教版高中数学必修3