《杜红全《算法案例》辗转相除法与更相减损术课件 新人教A版必修3》由会员分享，可在线阅读，更多相关《杜红全《算法案例》辗转相除法与更相减损术课件 新人教A版必修3（22页珍藏版）》请在金锄头文库上搜索。
1、1.3 算法案例 第一课时 康县一中 杜红全1.研究一个实际问题的算法，主要从 算法步骤、程序框图和编写程序三方面 展开.在程序框图中算法的基本逻辑结构 有哪几种？在程序设计中基本的算法语 句有哪几种？2.“求两个正整数的最大公约数” 是数学中的一个基础性问题，它有各种 解决办法，我们以此为案例，对该问题 的算法作一些探究.问题提出辗转相除法 与更相减损术思考1:18与30的最大公约数是多少？你 是怎样得到的？先用两个数公有的质因数连续去除 ，一直除到所得的商是互质数为止， 然后把所有的除数连乘起来即为最大 公约数. 知识探究（一）:辗转相除法思考2:对于8251与6105这两个数，由于 其公
2、有的质因数较大，利用上述方法求 最大公约数就比较困难.注意到 8251=61051+2146，那么8251与6105这 两个数的公约数和6105与2146的公约数 有什么关系？ 思考3:又6105=21462+1813，同理， 6105与2146的公约数和2146与1813的公 约数相等.重复上述操作，你能得到8251 与6105这两个数的最大公约数吗？2146=18131+333，148=374+0.333=1482+37，1813=3335+148，8251=61051+2146， 6105=21462+1813，思考4:上述求两个正整数的最大公约数 的方法称为辗转相除法或欧几里得算法.
3、一般地，用辗转相除法求两个正整数m， n的最大公约数，可以用什么逻辑结构来 构造算法？其算法步骤如何设计？ 第一步，给定两个正整数m，n(mn). 第二步，计算m除以n所得的余数r. 第三步，m=n，n=r. 第四步，若r=0，则m，n的最大公约数等于m；否则，返回第二步. 思考5:该算法的程序框图如何表示？ 开始输入m，n求m除以n的余数rm=nn=rr=0？ 是 输出m结束否思考6:该程序框图对应的程序如何表述？INPUT m，n DO r=m MODn m=n n=r LOOP UNTIL r=0 PRINT m END开始输入m，n求m除以n的余数rm=nn=rr=0？ 是 输出m结束
4、否思考7:如果用当型循环结构构造算法， 则用辗转相除法求两个正整数m，n的最 大公约数的程序框图和程序分别如何表 示？开始输入m，n求m除以n的余数rm=nn0？否 输出m结束是n=rINPUT m，n WHILE n0 r=m MODn m=n n=r WEND PRINT m END思考1:设两个正整数mn，若m-n=k，则m 与n的最大公约数和n与k的最大公约数相 等.反复利用这个原理，可求得98与63的 最大公约数为多少？ 98-63=35，14-7=7.21-7=14，28-7=21，35-28=7，63-35=28，知识探究（二）:更相减损术思考2:上述求两个正整数的最大公约数 的
5、方法称为更相减损术.一般地，用更相 减损术求两个正整数m，n的最大公约数 ，可以用什么逻辑结构来构造算法？其 算法步骤如何设计？ 第一步，给定两个正整数m，n(mn). 第二步，计算m-n所得的差k. 第三步，比较n与k的大小，其中大者用m表示，小者用n表示. 第四步，若m=n，则m，n的最大公约数等于m；否则，返回第二步. 思考3:该算法的程序框图如何表示？开始输入m，nnk？m=n是输出m结束mn？k=m-n是否n=km=k否思考4:该程序框图对应的程序如何表述？ INPUT m，n WHILE mk THENm=n n=k ELSEm=kEND IF WEND PRINT m END开始
6、输入m，nnk？m=n是输出m结束mn？k=m-n是否n=km=k否“更相减损术”在中国古代数学专著 九章算术中记述为： 可 半者半之，不可半者，副置分母、子之 数，以少减多，更相减损，求其等也， 以等数约之. 比较辗转相除法与更相减损术的区别 （1）都是求最大公约数的方法，计算上辗 转相除法以除法为主，更相减损术以减法为 主，计算次数上辗转相除法计算次数相对较 少，特别当两个数字大小区别较大时计算次数的区别较明显。 （2）从结果体现形式来看，辗转相除法体 现结果是以相除余数为0则得到，而更相减损 术则以减数与差相等而得到小结理论迁移例1 分别用辗转相除法和更相减损 术求168与93的最大公约
7、数. 辗转相除法：168=931+75， 93=751+18， 75=184+3， 18=36.更相减损术:168-93=75，93-75=18，75-18=57，57-18=39，39-18=21，21-18=3，18-3=15，15-3=12，12-3=9，9-3=6，6-3=3.例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.辗转相除法，就是对于给定的两个正整 数，用较大的数除以较小的数，若余数不为 零，则将余数和较小的数构成新的一对数， 继续上面的除法，直到大数被小数除尽为止 ，这时的较小的数即为原来两个数的最大公 约数. 小结作业2. 更相减损术，就是对于给定的两个正 整数，用较大的数减去较小的数，然后将差 和较小的数构成新的一对数，继续上面的减 法，直到差和较小的数相等，此时相等的两 数即为原来两个数的最大公约数.作业： P45练习：1. P48习题1.3A组：1.
