课题:§1.3辗转相除法与更相减损术
一.教学任务分析:
(1)在理解了算法的三种不同表示方式的基础上,结合算法案例----辗转相除法与更相减损术,让学生经历设计算法解决问题的过程,体验算法在解决问题中的作用.
(2)通过对具体实例的算法分析,画程序框图,编制程序,上机验证的方法理解掌握辗转相除法与更相减损术.
(3)通过转相除法与更相减损术所蕴涵的算法思想,培养学生利用算法解决问题的意识.提高逻辑思维能力.发展有条理的思考与数学表达的能力.
二.教学重点与难点:
教学重点:理解辗转相除法与更相减损术求最大公约数的方法.
教学难点:把辗转相除法与更相减损术的方法转换成程序框图与程序语言.
三.教学基本流程:
复习求最大公约数的知识,求两个整数的最大公约数,体会所蕴涵的算法 ↓
辗转相除法 ↓
辗转相除法的算法分析---程序框图及程序语言 ↓
更相减损术 ↓
巩固练习,小结、作业 四.教学情境设计:
1.创设情景,揭示课题
1.在小学,初中,我们已经学过求最大公约数的知识,你能求出18与30的公约数吗?
所以,18和30的最大公约数是2×3=6.
2.当公约数比较大(比如求8251与6105的最大公约数?),我们利用上述方法求解就比较困难,那么应该怎样求它们的最大公约数?这就是我们这一堂课所要探讨的内容.
2.辗转相除法
(1)例1:求两个正数8251和6105的最大公约数.
(分析:8251与6105两数都比较大,而且没有明显的公约数,如能把它们都变小一点,根据已有的知识即可求出最大公约数,可以考虑用两数中的较大的数除以较小的数求商和余数).
解:8251=6105×1+2146
显然6105与2146的公约数也必是8251与6105的公约数,反过来,8251与6105的公约数也是6105与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年左右首先提出的.欧几里德<原本>一书记录了这个算法.其算法的核心步骤是做带余除法.
练习:利用辗转相除法求两数4081与20723的最大公约数(答案:53)
(2)利用辗转相除法求最大公约数的算法步骤如下:
第一步:给定两个正整数m,n.
第二步:用较大的数m除以较小的数n所得余数r.
第三步:m=n,n=r.
第四步:若r=0,则m,n的最大公约数等于m;否则,返回到第二步.
……
依次计算直至rn=0,此时所得到的rn-1即为所求的最大公约数.
练习:利用辗转相除法求两数4081与20723的最大公约数(答案:53)
3.辗转相除法的程序框图及程序语言
利用辗转相除法的计算算法,我们可以设计出程序框图,并根据程序框图设计出程序语言在计算机上实现辗转相除法求最大公约数.
辗转相除法的程序框图及程序程序框图:
思考;你能用当型循环结构构造算法,求这两个正整数的最大公约数?
4.更相减损术
(1)<九章算术>是中国古代的数学专著,其中的“更相减损术”也可以用来求最大公约数,
其步骤如下:可半者半之,不可半者,副置分母,子之数,以少减多,更相减损,求其等也,以等数约之.
即为:第一步:任意给出两个正数;判断它们是否都是偶数.若是,用2约简;若不是,执行第二步.
第二步:以较大的数减去较小的数,接着把较小的数与所得的差比较,并以大数减小数.继续这个操作,直到所得的数相等为止,则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.
(2)例2:用更相减损术求196与126的最大公约数.
解:(1)由于196和126是偶数,用2约之,得98和63。
(2)把98和63以大数减小数,并辗转相减,
即:98-63=35
63-35=28
35-28=7
28-7=21
21-7=14
14-7=7
所以,98与63的最大公约数是7.而196与126的最大公约数是2×7=14。
练习:用更相减损术求两个正数84与72的最大公约数.(答案:12)
(3)辗转相除法与更相减损术的区别
①都是求最大公约数的方法,计算上辗转相除法以除法为主,更相减损术以减法为主,计算次数上辗转相除法计算次数相对较少,特别当两个数字大小区别较大时计算次数的区别较明显.
②从结果体现形式来看,辗转相除法体现结果是以相除余数为0则得到,而更相减损术则以减数与差相等而得到.
5.课堂练习
用辗转相除法求下列各组数的最大公约数:
(1)225;135(2)98;196(3)72;168(4)153;119
6.小结:
辗转相除法与更相减损术求最大公约数的计算方法及完整算法程序的编写.
7.作业:
<随堂导练>P13-14.
欢迎访问http://www.k12zy.com
学而思教育·学习改变命运思考成就未来!高考网www.gaokao.com
学而思教育·学习改变命运思考成就未来!高考网www.gaokao.com
结束
输出m
n=r
输入m,n
r=mMODn
i+1
开始
是
m=n
r=0?
否
INPUTm,n
DO
r=mMODn
m=n
n=r
LOOPUNTILr=0
PRINTm
END
|
|