1.3.1《算法案例--辗转相除法与更相减损术》
文档属性
| 名称 | 1.3.1《算法案例--辗转相除法与更相减损术》 |  | |
| 格式 | zip | ||
| 文件大小 | 340.2KB | ||
| 资源类型 | 教案 | ||
| 版本资源 | 人教新课标A版 | ||
| 科目 | 数学 | ||
| 更新时间 | 2013-02-21 18:09:50 | ||
图片预览
文档简介
课件23张PPT。2019/1/27案例1 辗转相除法与更相减损术1.3算法案例（第一课时） 湖南省耒阳市振兴学校 高中数学老师欧阳文丰制作2019/1/27教学目标 1.理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析；
2.能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序.
教学重点 ：理解辗转相除法与更相减损术求最大公约数的方法
教学难点 ：转相除法与更相减损术的方法转换成程序框图与程序语言。2019/1/27问题提出 1.研究一个实际问题的算法，主要从算法步骤、程序框图和编写程序三方面展开.在程序框图中算法的基本逻辑结构有哪几种？在程序设计中基本的算法语句有哪几种？ 2.“求两个正整数的最大公约数”是数学中的一个基础性问题，它有各种解决办法，我们以此为案例，对该问题的算法作一些探究.2019/1/273 59 15[问题1]：在小学，我们已经学过求最大公约数的知识，你能求出18与30的最大公约数吗？〖创设情景，揭示课题〗18 3023∴18和30的最大公约数是2×3=6.先用两个数公有的质因数连续去除,一直除到所得的商是互质数为止,然后把所有的除数连乘起来.[问题2]:我们都是利用找公约数的方法来求最大公约数，如果公约数比较大而且根据我们的观察又不能得到一些公约数，我们又应该怎样求它们的最大公约数？比如求8251与6105的最大公约数? 2019/1/27〖研探新知〗一.辗转相除法:例1 求两个正数8251和6105的最大公约数。 分析：8251与6105两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根据已有的知识即可求出最大公约数.解：8251＝6105×1＋2146 显然8251与6105的最大公约数也必是2146的约数，同样6105与2146的公约数也必是8251的约数，所以8251与6105的最大公约数也是6105与2146的最大公约数。2019/1/27〖研探新知〗一.辗转相除法:例1 求两个正数8251和6105的最大公约数。解：8251＝6105×1＋2146;6105＝2146×2＋1813;
2146＝1813×1＋333;
1813＝333×5＋148;
333＝148×2＋37;
148＝37×4＋0.则37为8251与6105的最大公约数。 以上我们求最大公约数的方法就是辗转相除法。也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的。 2019/1/271、辗转相除法（欧几里得算法） 所谓辗转相除法,就是对于给定的两个数,用较大的数除以较小的数.若余数不为零,则将余数和较小的数构成新的一对数,继续上面的除法,直到大数被小数除尽,则这时较小的数就是原来两个数的最大公约数.例.用辗转相除法求168与93的最大公约数.168=1×93＋75
93=1 ×75＋18
75=4×18＋3
18=6×3＋0所以，168与93的最大公约数为3。新 课讲授其辗转相除法的竖式如右图。2019/1/272、辗转相除法的原理：如果q和r是m除以n的商及余数, 即 m=nq+r,则gcd(m,n)=gcd(n,r).证明: 设 a=gcd(m,n),b=gcd(n,r) 则有a|m 及a|n,因此a|(m-nq), 即 a|r及a|n,所以a|b又 b|r及b|n,所以b|(nq+r),
即b|m及b|n,所以b|a
因为a|b并且b|a,所以a=b,即gcd(m,n)=gcd(n,r). 如计算 gcd(546, 429)
546=1×429+117,
429=3×117+78,
117=1×78+39,
78=2×39．附:gcd(m,n)表示m与n的最大公约数; lcm(m,n)表示m与n的最小
公倍数。2019/1/27辗转相除法的重要引申:由辗转相除法也可以推出，两数的最大公约数可以用两数的整数倍相加来表示，如3 = 5 × 168 + (?9） × 93。这个重要的等式叫做贝祖等式。
进而由贝祖等式就可以求解二元一次不定方程的通解。2019/1/273、利用辗转相除法求最大公约数的步骤如下： 第一步：用较大的数m除以较小的数n得到一个商q0和一个余数r0；(m=n×q0+r0)
第二步：若r0＝0，则n为m，n的最大公约数；若r0≠0，则用除数n除以余数r0得到一个商q1和一个余数r1；(n=r0×q1+r1)
第三步：若r1＝0，则r0为m，n的最大公约数；若r1≠0，则用除数r0除以余数r1得到一个商q2和一个余数r2；(r0=r1×q2+r2)
……
依次计算直至rn＝0，此时所得到的rn-1 即为所求的最大公约数。2019/1/27第一步,给定两个正数m,n
第二步,计算m除以n所得到余数r
第三步,m=n,n=r
第四步,若r=0,则m,n的最大公约数等于m;
否则返回第二步4、辗转相除法求最大公约数算法：2019/1/27思考1:该算法的程序框图和算法程序如何表述？INPUT m，nDOr=m MODnm=nn=rLOOP UNTIL r=0PRINT mEND2019/1/27思考2:如果用当型循环结构构造算法，则用辗转相除法求两个正整数m，n的最大公约数的程序框图和程序分别如何表示？2019/1/27INPUT m，nWHILE n>0r=m MODnm=nn=rWENDPRINT mEND2019/1/27随堂练习1：利用辗转相除法求两数4081与20723的最大公约数. (53)20723=4081×5+318;
4081=318×12+265;
318=265×1+53;
265=53×5+0.
其辗转相除法竖式如右图。2019/1/27二、《九章算术》——更相减损术 算理：“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。”第一步：任意给定两个正整数；判断他们是否都是偶数。若是，则用2约简；若不是则执行第二步。第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个数或这个数与约简数的乘积就是所求的最大公约数。2019/1/27思考:更相减损术的程序框图和算法语言如何表述？INPUT m，nWHILE m<>nk=m-nIF n>k THENm=nn=kELSEm=kEND IFWENDPRINT mEND2019/1/27例2 分别用更相减损术和辗转相除法求98
与63的最大公约数。解：由于63不是偶数，把98和63以大数减小数，
并辗转相减 98－63＝35 63－35＝28 35－28＝7 28－7＝21
21－7＝14
14－7＝7所以，98和63的最大
公约数等于7 。2019/1/27即：42－36＝6;
36－6＝30;
30－6＝24;
24－6＝18;
18－6＝12;
12－6＝6.例3：用更相减损术求两个正数84与72的最大公约数。 84与72的最大公约数
就是:6×2=12。解: 84÷2=42,72÷2=36. 先约简，再求21与18的最大公约数,然后乘以两次约简的质因数4。2019/1/27 例4 求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.2019/1/27 1.辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大公约数. 小结作业 2. 更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公约数.2019/1/27比较辗转相除法与更相减损术的区别
（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。
（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到。小结附:gcd(m,n)表示m与n的最大公约数; lcm(m,n)表示m与n的最小
公倍数。int(x)表示不超过x的最大整数。2019/1/27课后作业：
P45练习：1.
P48习题1.3A组：1.
2.能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序.
教学重点 ：理解辗转相除法与更相减损术求最大公约数的方法
教学难点 ：转相除法与更相减损术的方法转换成程序框图与程序语言。2019/1/27问题提出 1.研究一个实际问题的算法，主要从算法步骤、程序框图和编写程序三方面展开.在程序框图中算法的基本逻辑结构有哪几种？在程序设计中基本的算法语句有哪几种？ 2.“求两个正整数的最大公约数”是数学中的一个基础性问题，它有各种解决办法，我们以此为案例，对该问题的算法作一些探究.2019/1/273 59 15[问题1]：在小学，我们已经学过求最大公约数的知识，你能求出18与30的最大公约数吗？〖创设情景，揭示课题〗18 3023∴18和30的最大公约数是2×3=6.先用两个数公有的质因数连续去除,一直除到所得的商是互质数为止,然后把所有的除数连乘起来.[问题2]:我们都是利用找公约数的方法来求最大公约数，如果公约数比较大而且根据我们的观察又不能得到一些公约数，我们又应该怎样求它们的最大公约数？比如求8251与6105的最大公约数? 2019/1/27〖研探新知〗一.辗转相除法:例1 求两个正数8251和6105的最大公约数。 分析：8251与6105两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根据已有的知识即可求出最大公约数.解：8251＝6105×1＋2146 显然8251与6105的最大公约数也必是2146的约数，同样6105与2146的公约数也必是8251的约数，所以8251与6105的最大公约数也是6105与2146的最大公约数。2019/1/27〖研探新知〗一.辗转相除法:例1 求两个正数8251和6105的最大公约数。解：8251＝6105×1＋2146;6105＝2146×2＋1813;
2146＝1813×1＋333;
1813＝333×5＋148;
333＝148×2＋37;
148＝37×4＋0.则37为8251与6105的最大公约数。 以上我们求最大公约数的方法就是辗转相除法。也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的。 2019/1/271、辗转相除法（欧几里得算法） 所谓辗转相除法,就是对于给定的两个数,用较大的数除以较小的数.若余数不为零,则将余数和较小的数构成新的一对数,继续上面的除法,直到大数被小数除尽,则这时较小的数就是原来两个数的最大公约数.例.用辗转相除法求168与93的最大公约数.168=1×93＋75
93=1 ×75＋18
75=4×18＋3
18=6×3＋0所以，168与93的最大公约数为3。新 课讲授其辗转相除法的竖式如右图。2019/1/272、辗转相除法的原理：如果q和r是m除以n的商及余数, 即 m=nq+r,则gcd(m,n)=gcd(n,r).证明: 设 a=gcd(m,n),b=gcd(n,r) 则有a|m 及a|n,因此a|(m-nq), 即 a|r及a|n,所以a|b又 b|r及b|n,所以b|(nq+r),
即b|m及b|n,所以b|a
因为a|b并且b|a,所以a=b,即gcd(m,n)=gcd(n,r). 如计算 gcd(546, 429)
546=1×429+117,
429=3×117+78,
117=1×78+39,
78=2×39．附:gcd(m,n)表示m与n的最大公约数; lcm(m,n)表示m与n的最小
公倍数。2019/1/27辗转相除法的重要引申:由辗转相除法也可以推出，两数的最大公约数可以用两数的整数倍相加来表示，如3 = 5 × 168 + (?9） × 93。这个重要的等式叫做贝祖等式。
进而由贝祖等式就可以求解二元一次不定方程的通解。2019/1/273、利用辗转相除法求最大公约数的步骤如下： 第一步：用较大的数m除以较小的数n得到一个商q0和一个余数r0；(m=n×q0+r0)
第二步：若r0＝0，则n为m，n的最大公约数；若r0≠0，则用除数n除以余数r0得到一个商q1和一个余数r1；(n=r0×q1+r1)
第三步：若r1＝0，则r0为m，n的最大公约数；若r1≠0，则用除数r0除以余数r1得到一个商q2和一个余数r2；(r0=r1×q2+r2)
……
依次计算直至rn＝0，此时所得到的rn-1 即为所求的最大公约数。2019/1/27第一步,给定两个正数m,n
第二步,计算m除以n所得到余数r
第三步,m=n,n=r
第四步,若r=0,则m,n的最大公约数等于m;
否则返回第二步4、辗转相除法求最大公约数算法：2019/1/27思考1:该算法的程序框图和算法程序如何表述？INPUT m，nDOr=m MODnm=nn=rLOOP UNTIL r=0PRINT mEND2019/1/27思考2:如果用当型循环结构构造算法，则用辗转相除法求两个正整数m，n的最大公约数的程序框图和程序分别如何表示？2019/1/27INPUT m，nWHILE n>0r=m MODnm=nn=rWENDPRINT mEND2019/1/27随堂练习1：利用辗转相除法求两数4081与20723的最大公约数. (53)20723=4081×5+318;
4081=318×12+265;
318=265×1+53;
265=53×5+0.
其辗转相除法竖式如右图。2019/1/27二、《九章算术》——更相减损术 算理：“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。”第一步：任意给定两个正整数；判断他们是否都是偶数。若是，则用2约简；若不是则执行第二步。第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个数或这个数与约简数的乘积就是所求的最大公约数。2019/1/27思考:更相减损术的程序框图和算法语言如何表述？INPUT m，nWHILE m<>nk=m-nIF n>k THENm=nn=kELSEm=kEND IFWENDPRINT mEND2019/1/27例2 分别用更相减损术和辗转相除法求98
与63的最大公约数。解：由于63不是偶数，把98和63以大数减小数，
并辗转相减 98－63＝35 63－35＝28 35－28＝7 28－7＝21
21－7＝14
14－7＝7所以，98和63的最大
公约数等于7 。2019/1/27即：42－36＝6;
36－6＝30;
30－6＝24;
24－6＝18;
18－6＝12;
12－6＝6.例3：用更相减损术求两个正数84与72的最大公约数。 84与72的最大公约数
就是:6×2=12。解: 84÷2=42,72÷2=36. 先约简，再求21与18的最大公约数,然后乘以两次约简的质因数4。2019/1/27 例4 求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.2019/1/27 1.辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大公约数. 小结作业 2. 更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公约数.2019/1/27比较辗转相除法与更相减损术的区别
（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。
（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到。小结附:gcd(m,n)表示m与n的最大公约数; lcm(m,n)表示m与n的最小
公倍数。int(x)表示不超过x的最大整数。2019/1/27课后作业：
P45练习：1.
P48习题1.3A组：1.