- 419.00 KB
- 2021-06-24 发布
- 1、本文档由用户上传,淘文库整理发布,可阅读全部内容。
- 2、本文档内容版权归属内容提供方,所产生的收益全部归内容提供方所有。如果您对本文有版权争议,请立即联系网站客服。
- 3、本文档由用户上传,本站不保证质量和数量令人满意,可能有诸多瑕疵,付费之前,请仔细阅读内容确认后进行付费下载。
- 网站客服QQ:403074932
授课题目
辗转相除法与更相减损术
拟 1 课时
第 1课时
明确目标
1.理解辗转相除法与更相减损术中蕴含的数学原理,并能根据这些原理进行算法分析。
2.基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序。
重点难点
重点:理解辗转相除法与更相减损术求最大公约数的方法。
难点:把辗转相除法与更相减损术的方法转换成程序框图与程序语言。
课型
□讲授 □习题 □复习 □讨论 □其它
教 学 内 容 与 教 师 活 动 设 计
学生活动过程
一、先学后讲
(一)创设情景,揭示课题
1.教师首先提出问题:在初中,我们已经学过求最大公约数的知识,你能求出18与30的公约数吗?
2.接着教师进一步提出问题,我们都是利用找公约数的方法来求最大公约数,如果公约数比较大而且根据我们的观察又不能得到一些公约数,我们又应该怎样求它们的最大公约数?比如求8251与6105的最大公约数?这就是我们这一堂课所要探讨的内容。
(二)研探新知
1.辗转相除法
例1 求两个正数8251和6105的最大公约数。
(分析:8251与6105两数都比较大,而且没有明显的公约数,如能把它们都变小一点,根据已有的知识即可求出最大公约数)
解:8251=6105×1+2146
显然8251的最大公约数也必是2146的约数,同样6105与2146的公约数也必是8251的约数,所以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年左右首先提出的。利用辗转相除法求最大公约数的步骤如下:
第一步:用较大的数m除以较小的数n得到一个商q0和一个余数r0;
第二步:若r0=0,则n为m,n的最大公约数;若r0≠0,则用除数n除以余数r0得到一个商q1和一个余数r1;
第三步:若r1=0,则r1为m,n的最大公约数;若r1≠0,则用除数r0除以余数r1得到一个商q2和一个余数r2; ……
依次计算直至rn=0,此时所得到的rn-1即为所求的最大公约数。
练习:利用辗转相除法求两数4081与20723的最大公约数(答案:53)
2.更相减损术
我国早期也有解决求最大公约数问题的算法,就是更相减损术。
更相减损术求最大公约数的步骤如下:可半者半之,不可半者,副置分母·子之数,以少减多,更相减损,求其等也,以等数约之。
翻译出来为:
第一步:任意给出两个正数;判断它们是否都是偶数。若是,用2约简;若不是,执行第二步。
第二步:以较大的数减去较小的数,接着把较小的数与所得的差比较,并以大数减小数。继续这个操作,直到所得的数相等为止,则这个数(等数)就是所求的最大公约数。
例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。
练习:用更相减损术求两个正数84与72的最大公约数。(答案:12)
教师分析后,学生独立或合作完成后,教师点评
3.比较辗转相除法与更相减损术的区别
(1)都是求最大公约数的方法,计算上辗转相除法以除法为主,更相减损术以减法为主,计算次数上辗转相除法计算次数相对较少,特别当两个数字大小区别较大时计算次数的区别较明显。
(2)从结果体现形式来看,辗转相除法体现结果是以相除余数为0则得到,而更相减损术则以减数与差相等而得到
4. 辗转相除法与更相减损术计算的程序框图及程序
利用辗转相除法与更相减损术的计算算法,我们可以设计出程序框图以及BSAIC程序来在计算机上实现辗转相除法与更相减损术求最大公约数,辗转相除法的程序框图(请参看课本)
二、总结提升
1、本节课你主要学习了
三、问题过关:参看学案。
学生独立完成
补充内容:
教学后记: