人教版高中数学 1.3算法案例1课件 新人教A必修3.ppt

《人教版高中数学 1.3算法案例1课件 新人教A必修3.ppt》由会员分享，可在线阅读，更多相关《人教版高中数学 1.3算法案例1课件 新人教A必修3.ppt（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1.3算法案例(1)辗转相除法与更相减相除法与更相减损术高中数学人教版必修三第一章算法初步2021/8/9 星期一1表示算法的三种方式：表示算法的三种方式：算法步骤（自然语言）算法步骤（自然语言）程序框图（图形语言）程序框图（图形语言）算法语句算法语句（程序语言）（程序语言）复习引入复习引入2021/8/9 星期一23 159 45 问题问题11：在小学，我们已经学过求最大公约数：在小学，我们已经学过求最大公约数的知识，你能求出的知识，你能求出1212与与1616、1818与与9090的最大公约的最大公约数吗？数吗？18 90231818和和9090的最大公约的最大公约数是数是233=18.2

2、33=18.先用两个数公有的先用两个数公有的质因数质因数连续去除连续去除,一直除到所得一直除到所得的商是互质数为止的商是互质数为止,然后然后把所有的除数连乘起来把所有的除数连乘起来.问题问题2:2:求求8251与与6105的最大公约数的最大公约数?新课讲解新课讲解1 532021/8/9 星期一3辗转相除法（欧几里得算法）辗转相除法（欧几里得算法）观察用辗转相除法求观察用辗转相除法求8251和和6105的最大公约数的过程的最大公约数的过程 第一步第一步 用两数中较大的数除以较小的数，求得商和余数用两数中较大的数除以较小的数，求得商和余数8251=61051+2146结论：结论：8251和和61

3、05的公约数就是的公约数就是6105和和2146的公约数，求的公约数，求8251和和6105的最大公约数，只要求出的最大公约数，只要求出6105和和2146的的最大最大公约数就可以了。公约数就可以了。第二步第二步 对对6105和和2146重复第一步的做法重复第一步的做法6105=21462+1813同理同理6105和和2146的最大公约数也是的最大公约数也是2146和和1813的最大公约数。的最大公约数。新课讲解新课讲解2021/8/9 星期一4完整的过程完整的过程8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=14

4、82+37148=374+0显然显然37是是148和和37的最大公约数，的最大公约数，也就是也就是8251和和6105的最大的最大公约公约数数 新课讲解新课讲解2021/8/9 星期一5一、辗转相除法（欧几里得算法）一、辗转相除法（欧几里得算法）1、定义：、定义：所谓辗转相除法，就是对于给定的两个所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数。若余数不为数，用较大的数除以较小的数。若余数不为零，则零，则将除数变被除数，余数变除数将除数变被除数，余数变除数，继续，继续上面的除法，直到大数被小数除尽，则这时上面的除法，直到大数被小数除尽，则这时最后的除数就是原来两个数的最大公约数。最

5、后的除数就是原来两个数的最大公约数。辗转相除法是一个反复执行直到余数等于辗转相除法是一个反复执行直到余数等于0停止的算法停止的算法 问题问题3你能把辗转相除法写成算法步骤吗？你能把辗转相除法写成算法步骤吗？研探新知研探新知2021/8/9 星期一6.第四步第四步,若若r=0,则则m,n的最大公约数等于的最大公约数等于m;否则，返回第二步否则，返回第二步辗转相除法求最大公约数算法步骤：辗转相除法求最大公约数算法步骤：第一步第一步,给定两个正数给定两个正数m,n(mn).第二步第二步,计算计算m除以除以n所得到所得到的的余数余数r.第三步第三步,m=n,n=r.研探新知研探新知 问题问题4:4:该

6、算法的程序框图如何表示？该算法的程序框图如何表示？2021/8/9 星期一7开始开始输入输入m，n求求m除以除以n的余数的余数rm=nn=rr=0？是是输出输出m结束结束否否新课讲解新课讲解问题问题5:5:该该程序框图程序框图对应的程对应的程序如何表序如何表述？述？2021/8/9 星期一8INPUT mINPUT m，n nDODOr=m MOD nr=m MOD nm=nm=nn=rn=rLOOP UNTIL r=0LOOP UNTIL r=0PRINT mPRINT mENDEND开始开始输入输入m，n求求m除以除以n的余数的余数rm=nn=rr=0？是是输出输出m结束结束否否新课讲解新

7、课讲解2021/8/9 星期一9问题问题6:6:如果用当型循环结构构造算法，如果用当型循环结构构造算法，求两个正整数求两个正整数m m，n n的最大公约数的程序的最大公约数的程序框图和程序分别如何表示？框图和程序分别如何表示？研探新知研探新知2021/8/9 星期一10开始开始输入输入m，n求求m除以除以n的余数的余数rm=nn0？否否输出输出m结束结束是是n=rINPUT mINPUT m，n nWHILEWHILE n n0 0r=m MODnr=m MODnm=nm=nn=rn=rWENDWENDPRINT mPRINT mENDEND2021/8/9 星期一11练习1.用辗转相除法求下

8、列两数的最大公约数：用辗转相除法求下列两数的最大公约数：（1）225,135；（2）98,196；（3）72,168；（4）153,119.（3）24.（2）98.（1）45.（4）17.2021/8/9 星期一12九章算术九章算术更相减损术更相减损术 算理：算理：可半者半之，不可半者，副置分母、子可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等之数，以少减多，更相减损，求其等也，以等数约之。数约之。第一步：第一步：任意给定两个正整数任意给定两个正整数，判断他们是否都是判断他们是否都是偶数偶数.若是，则用若是，则用2约简；若不是约简；若不是,执行第二步。执行第二步。第

9、二步：第二步：以较大的数减较小的数，接着把所得的差以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数与较小的数比较，并以大数减小数.继续这个操作，继续这个操作，直到所得的减数和差相等为止，则这个等数就是所直到所得的减数和差相等为止，则这个等数就是所求的最大公约数。求的最大公约数。研探新知研探新知2021/8/9 星期一132、更相减损术、更相减损术（1）定义定义：所谓更相减损术，就是对于给：所谓更相减损术，就是对于给定的两个数，用较大的数减去较小的数，然定的两个数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，再用较后将差和较小的数构成新的一对数，再用较大的数减去较

10、小的数，反复执行此步骤直到大的数减去较小的数，反复执行此步骤直到差数和较小的数相等，此时相等的两数便为差数和较小的数相等，此时相等的两数便为原来两个数的最大公约数原来两个数的最大公约数.研探新知研探新知2021/8/9 星期一14例例 用更相减损术求用更相减损术求9898与与6363的最大公约数的最大公约数.解：由于解：由于6363不是偶数，把不是偶数，把9898和和6363以大数以大数减小数，并辗转相减，减小数，并辗转相减，即：即：986335 633528 35287 28721 21714 1477所以，所以，9898与与6363的最大公约数是的最大公约数是7 7.练习：用更相减损术求两

11、个正数练习：用更相减损术求两个正数8484与与7272的最大的最大公约数公约数.(12)(12)研探新知研探新知2021/8/9 星期一15辗转相除法与更相减损术的比较辗转相除法与更相减损术的比较:（1 1）都是求最大公约数的方法，计算上辗）都是求最大公约数的方法，计算上辗转相除法以转相除法以除法除法为主，更相减损术以为主，更相减损术以减法减法为主为主;计算次数上辗转相除法计算次数上辗转相除法计算次数计算次数相对相对较少较少，特，特别当两个数字大小区别较大时计算次数的区别别当两个数字大小区别较大时计算次数的区别较明显较明显.（2 2）从结果体现形式来看，辗转相除法体）从结果体现形式来看，辗转相

12、除法体现结果是以现结果是以相除余数为相除余数为0 0则得到，而更相减损术则得到，而更相减损术则以则以减数与差相等减数与差相等而得到而得到.研探新知研探新知2021/8/9 星期一161：用辗转相除法求80和36的最大公约数，并用更相减损术检验所得结果分析：将80作为大数，36作为小数，执行辗转相除法和更相减损术的步骤即可解：用辗转相除法：803628，36844，8420.故80和36的最大公约数是4.课堂测试课堂测试80-36=4444-36=836-8=2828-8=2020-8=1212-8=48-4=42021/8/9 星期一172.求三个数175、100、75的最大公约数分析：求三个

13、数的最大公约数时，可以先求出其中两个数的最大公约数，用这个最大公约数再与第三个数求最大公约数，所得结果就是这三个数的最大公约数解：(辗转相除法)：先求175与100的最大公约数：175100175，10075125，75253.175与100的最大公约数是25.课堂测试课堂测试2021/8/9 星期一18以下再求25与75的最大公约数：7525325和75的最大公约数是25.故25是75和25的最大公约数，也就是175、100、75的最大公约数课堂测试课堂测试175-100=75100-75=2575-25=5050-25=2575-25=5050-25=252021/8/9 星期一191.用

14、辗转相除法计算60与48的最大公约数时，需要做的除法次数是()A1B2C3 D4解析：6048112,481240.仅需要两步运算答案：B随堂练习随堂练习2021/8/9 星期一202用辗转相除法求294和84的最大公约数时，需要做除法的次数是()A1B2C3 D4解析：29484342,84422.故需做2次除法答案：B随堂练习随堂练习2021/8/9 星期一213求378和90的最大公约数解：37890418,90185，378和90的最大公约数是18.随堂练习随堂练习2021/8/9 星期一224：求三个数324,243,108的最大公约数解：先求324与243的最大公约数，324243

15、181，243813，324与243的最大公约数为81.下面再求108与81的最大公约数：1088127，81273.108与81的最大公约数是27.故324,243,108的最大公约数为27.随堂练习随堂练习2021/8/9 星期一23 1.1.辗转相除法辗转相除法，就是对于给定的两个正整数，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数即为原直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大

16、公约数来两个数的最大公约数.2.2.更相减损术更相减损术，就是对于给定的两个正整数，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差和较小的数构用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较小的成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公数相等，此时相等的两数即为原来两个数的最大公约数约数.小结与作业小结与作业2021/8/9 星期一243 3、辗转相除法与更相减损术的、辗转相除法与更相减损术的区别区别（1 1）都是求最大公约数的方法，计算上辗转相除）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显大小区别较大时计算次数的区别较明显.（2 2）从结果体现形式来看，辗转相除法体现结果）从结果体现形式来看，辗转相除法体现结果是以相除余数为是以相除余数为0 0则得到，而更相减损术则以减数与则得到，而更相减损术则以减数与差相等而得到差相等而得到.小结与作业小结与作业课本课本P48页习页习题题1.3 A组组T1.2021/8/9 星期一25