人教版高中·高一数学必修三《算法案例·算法初步》(第1.3课时)PPT课件

讲解人：XXX时间：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=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】用辗转相除法求下面两数的最大公约数，并用更相减损术检验你的结果：(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为止；更相减损术进行的是减法运算，即辗转相减，直到减数和差相等为止.辗转相除法与更相减损法的比较：新知探究讲解人：XXX时间：2020.6.1MENTALHEALTHCOUNSELINGPPT感谢你的聆听第1章算法初步人教版高中数学必修3