当前位置:首页 >> 数学 >>

§1[1].3


§1.3 辗转相除法与更相减损术
教学目标: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 的最大公约数。 以上我们求最大公约数的方法就是辗转相除法。也叫欧几里德算法,它是由欧几里德在公元前 300 年左 右首先提出的。利用辗转相除法求最大公约数的步骤如下: (1) :用较大的数 m 除以较小的数 n 得到一个商 S0 和一个余数 R0 ; ( 2) :若 R0 =0,则 n 为 m,n 的最大 公约数;若 R0 ≠0,则用除数 n 除以余数 R0 得到一个商 S1 和一个余数 R1 ; (3) :若 R1 =0,则 R1 为 m,n 的最大公约数;若 R1 ≠0,则用除数 R0 除以余数 R1 得到一个商 S2 和一个余数 R2 ;…… 直至 Rn =0,此时所得到的 Rn?1 即为所求的最大公约数。 更相减损术 我国早期也有求最大公约数问题的算法,就是更相减损术。在《九章算术》中有更相减损术求最大公约 数的步骤:可半者半之,不可半者,副置分母?子之数,以少减多,更相减损,求其等也,以等数约之。 翻译为: (1) :任意给出两个正数;判断它们是否都是偶数。若是,用 2 约简;若不是,执行第二步。 (2) : 以较大的数减去较小的数,接着把较小的数与所得的差比较,并以大数减小数。继续这个操作,直到所 得的数相等为止,则这个数(等数)就是所求的最大公约数。 例 2 用更相减损术求 98 与 63 的最大公约数. 分析: (略) 辗转相除法与更相减损术的区别: (1)都是求最大公约数的方法,计算上辗转相除法以除法为主,更相减损术以减法为主,计算次数上辗 转相除法计算次数相对较少,特别当两个数字大小区别较大时计算次数的区别较明显。 (2)从结果体现形式来看,辗转相除法体现结果是以相除余数为 0 则得到,而更相减损术则以减数与差 相等而得到 小结:对比分析辗转相除法与更相减损术求最大公约数的计算方法及完整算法程序。 依次计算


赞助商链接
相关文章:
文科数学一轮复习§1.3 简单的逻辑联结词、全称量词与...
文科数学一轮复习§1.3 简单的逻辑联结词、全称量词与存在量词_数学_高中教育_...x∈[0,1],a≥ex”;命题 q:“ ? x∈R,使得 x2+4x +a=0”. 若命题...
线性代数 §1.1 二阶、三阶行列式
线性代数 §1.1 二阶、三阶行列式_数学_自然科学_专业资料。线性代数 §1.1...[1 ? 0 ? 6 ? 2 ? 5 ? ( ? 1) ? 3 ? 4 ? 0] ? [ ? 1 ?...
§1.3震击与震压造型机_图文
§1.3 震击与震压造型机阀门司气 司气方式 活塞司气 断进气 非膨胀式 不断进气 膨胀式 、震击循环--断进气膨胀式(图 2-2) 行程符号 进气 Se 膨胀 ...
§3—1 合金及其组织
河源市高级技工学校理论课教案教师 李晓红 科目 金属材料与热处理 13模具数控班 授课日期 7周 星期2 第 56 节 课题 §31合金及其组织 1、掌握合金的有关...
§1.3.1(3)正弦函数的定义域、值域
[0, ] 的值域是( ) 6 2 B.[- ? A.[- 3 1 , ] 2 2 1 3 , ] 2 2 C.[ 3 ,1] 2 D.[ 1 ,1] 2 5.若 sinx=a-1,x∈R 有意义,则...
§1.3整除的进一步性质及与最小公倍数
§3 整除的进一步性质与最小公倍数 一、整除的进一步性质 1、定理:设 a, b 为任意的正整数,则 k ?1 Qk a ? P rk k b ? (?1) k ? 1, 2, ,...
§25[1][1].3解直角三角形(1)
§25[1][1].3解直角三角形(1)_数学_初中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 §25[1][1].3解直角三角形(1)_数学_初中教育_教育专区。...
§1.3.1算法案例3 导学案
导学案 §1.3.1 算 法案例 3(进位制)【学习目标】 1、 了解各种进位制与十进制之间转化的规律, 用类比的思想方法掌握将 k 进制转化为 十进制的算法。 2...
§1.3正弦型函数.
§1.3正弦型函数._数学_高中教育_教育专区。§1.3 正弦型函数 在工程技术中,常借助正弦型函数来解决实际问题. 一般地,形如 y ? Asin ??x ? ? ? , ?...
§1.3.1直线的极坐标方程(第1课时)
§1.3.1 圆的极坐标方程(第 1 课时) 【考纲解读】 1.会写过极点的直线方程和圆心在极点的圆的方程. 极点且圆心在极轴或在(ρ,θ)处的圆的极坐标方程. ...
更多相关标签: