- 1、本文档共4页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
秦九韶算法与排序
教案纸
课 题
§1.3 辗转相除法与更相减损术
课型
新课
主备人
赵辉
上课教师
赵辉
上课时间
45 分钟
1 理解辗转相除法与更相减损术中蕴含的数学原理,并能根据这
学习目标
些原理进行算法分析。 2 基本能根据算法语句与程序框图的知
识设计完整的程序框图并写出算法程序。
教学重点
理解辗转相除法与更相减损术求最大公约数的方法。
把辗转相除法与更相减损术的方法转换成程序框图与程序语言。
教学难点
教师准备
多媒体
教学过程
集备修正
提出问题:在小学,我们已经学过求最大公约数的知
识,如口算求出 12 与 20 的公约数。
分析:我们都是利用找公约数的方法来求最大公约数,如果公约数比较大而且根据我们的观察又不能得到一些公约数,我们又应该怎样求它们的最大公约数?比如求 8251 与 6105 的最大公约数?这就是我们这一堂课所要探讨的内容。
辗转相除法
例 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 第 1 页第 1 页
秦九韶算法与排序
的最大公约数。
以上我们求最大公约数的方法就是辗转相除法。也叫欧几里德算法,它是由欧几里德在公元前 300 年左右首先提出的。利用辗转相除法求最大公约数的步骤如下:
(1):用较大的数 m 除以较小的数 n 得到一个商 S0
和一个余数 R0 ;(2):若 R0 =0,则 n 为 m,n 的最
大公约数;若 R0 ≠0,则用除数 n 除以余数 R0 得到一
个商 S1 和一个余数 R1 ;(3):若 R1 =0,则 R1 为 m,
的最大公约数;若 R1 ≠0,则用除数 R0 除以余数 R1
得到一个商 S2 和一个余数 R2 ;…… 依次计算
直至 Rn =0,此时所得到的 Rn?1 即为所求的最大公约
数。
更相减损术
我国早期也有求最大公约数问题的算法,就是更相减损术。在《九章算术》中有更相减损术求最大公约数的步骤:可半者半之,不可半者,副置分母?子之数,以少减多,更相减损,求其等也,以等数约之。
翻译为:(1):任意给出两个正数;判断它们是否都是偶数。若是,用 2 约简;若不是,执行第二步。(2):以较大的数减去较小的数,接着把较小的数与所得的差比较,并以大数减小数。继续这个操作,直到所得的数相等为止,则这个数(等数)就是所求的最大公约数。
例 2 用更相减损术求 98 与 63 的最大公约数.
分析:(略)
辗转相除法与更相减损术的区别:
(1)都是求最大公约数的方法,计算上辗转相除法以除法为主,更相减损术以减法为主,计算次数上辗转相除法计算次数相对较少,特别当两个数字
第 2 页第 2 页
秦九韶算法与排序
大小区别较大时计算次数的区别较明显。
(2)从结果体现形式来看,辗转相除法体现结果是以相除余数为 0 则得到,而更相减损术则以减数与差相等而得到
小结:对比分析辗转相除法与更相减损术求最大公约数的计算方法及完整算法程序。作业 步步高
板
书
课
后
反
思
第 3 页第 3 页
秦九韶算法与排序
第 4 页第 4 页
文档评论(0)