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

1.3.1算法案例(第一课时)


1.3算 法 案 例

1. 回顾算法的三种表述:

自然语言 程序框图(三种逻辑结构)
程序语言(五种基本语句)

2. 思考: 小学学过的求两个数最大公约数的方法?

先用两个公有的质因数连续去除, 一直除到所得的商是互质数为止,然 后把所有的除数连乘起来.

1、求两个正整数的最大公约数 (1)求25和35的最大公约数 (2)求63和63的最大公约数 (3)求72和8的最大公约数
( 1) 5 25 5 35 7 (2) 63 63 1 63 1

所以,25和35的最大公 约数为5

所以,63和63的最大公 约数为63

2、除了用这种方法外还有没有其它方法? 算出8256和6105的最大公约数.

辗转相除法(欧几里得算法) 观察用辗转相除法求8251和6105的最大公约数的过程

第一步 用两数中较大的数除以较小的数,求得商和余数 8251=6105×1+2146 结论: 8251和6105的公约数就是6105和2146的公约数, 求8251和6105的最大公约数,只要求出6105和2146的公 约数就可以了。 第二步 对6105和2146重复第一步的做法 6105=2146×2+1813 同理6105和2146的最大公约数也是2146和1813的最大公 约数。

例2 用辗转相除法求225和135的最大公 完整的过程 约数【P45练习1】 225=135×1+90 8251=6105×1+2146 6105=2146×2+1813 2146=1813×1+333 1813=333×5+148 333=148×2+37 135=90×1+45 90=45×2 显然45是90和45的最大公约数,也 就是225和135的最大公约数 思考1:从上面的两个例子可以看 出计算的规律是什么? S1:用大数除以小数 S2:除数变成被除数,余数变成 除数 S3:重复S1,直到余数为0

148=37×4+0
显然37是148和37的最大 公约数,也就是8251和 6105的最大公约数

辗转相除法是一个反复执行直到余数等于0停止的步骤, 这实际上是一个循环结构。 m=n×q+r
用程序框图表示出右边的过程 8251=6105×1+2146 6105=2146×2+1813 2146=1813×1+333

r=m MOD n

m=n
n=r r=0? 否

1813=333×5+148
333=148×2+37 148=37×4+0



1、辗转相除法(欧几里得算法) (1)算理:所谓辗转相除法,就是对于给定 的两个数,用较大的数除以较小的数。若余 数不为零,则将余数和较小的数构成新的一 对数,继续上面的除法,直到大数被小数除 尽,则这时较小的数就是原来两个数的最大 公约数。

(3)程序框图
(4)程序
INPUT “m,n=“;m,n
DO r=m MOD n m=n n=r

开始 输入m,n

r=m MOD n
m=n n=r

LOOP UNTIL r=0
PRINT m END

r=0?
是 输出m 结束



《九章算术》——更相减损术 算理:可半者半之,不可半者,副置分母、子 之数,以少减多,更相减损,求其等也,以等 数约之。
第一步:任意给定两个正整数;判断他们是否都是 偶数。若是,则用2约简;若不是则执行第二步。
第二步:以较大的数减较小的数,接着把所得的差 与较小的数比较,并以大数减小数。继续这个操作, 直到所得的减数和差相等为止,则这个等数就是所 求的最大公约数。

例3 用更相减损术求98与63的最大公约数
解:由于63不是偶数,把98和63以大数减小数, 并辗转相减 98-63=35 63-35=28 35-28=7 28-7=21 21-7=21 14-7=7 所以,98和63的最大公约数等于7 练习: 用更相减损术求两个正数84与72的最大公约数.
先约简,再求21与18的最大公约数,然后乘 以两次约简的质因数4

2、更相减损术 (1)算理:所谓更相减损术,就是对于给 定的两个数,用较大的数减去较小的数,然 后将差和较小的数构成新的一对数,再用较 大的数减去较小的数,反复执行此步骤直到 差数和较小的数相等,此时相等的两数便为 原来两个数的最大公约数。

(3)程序框图 (4)程序
INPUT “a,b=“;a,b WHILE a<>b r=a-b IF b>r THEN a=b b=r ELSE a=r END IF WEND PRINT b END

开始
输入a,b a≠b? 是 r=a-b a=r 否 r<b? 是 a=b b=r 否

输出b
结束

例3、求324、243、135这三个数的最大 公约数。
思路分析:求三个数的最大公约数可以先求出两个 数的最大公约数,第三个数与前两个数的最大公约 数的最大公约数即为所求。

324与243,即81 81与135,即27

小结

比较辗转相除法与更相减损术的区别
辗转相除法 除法 余数为0 最后一步中的除数 步骤较少,运算复杂 更相减损术 减法 减数与差相等 最后一步中的减数 步骤较多,运算简单

两种方法 计算法则 终止条件 最大公约数的 选取 计算次数 相同点

同为求两个正整数最大公约数的方法,都是 递归过程


相关文章:
1.3算法案例(一)
1.3算法案例(一)_数学_高中教育_教育专区。高二数学教学设计教师 刘艳娟、...1.3.1 算法案例学案(一)... 2页 1下载券 1.3算法案例(第一课时) 8页...
1.3算法案例
1.3算法案例_金融/投资_经管营销_专业资料。1.3 算法案例一、学习目标 1. 会用辗转相除法与更相减损术求最大公约数的方法。 2. 会利用秦九韶算法求多项式...
1.3算法案例(第1课时)
宜昌市第十八中学数学教学案学习课题:1.3 算法案例(第 1 课时) 学习目标:1.了解什么是辗转相除法与更相减损术,并学会编写辗转相除法的程 序框图及程序;2. 了...
人教必修三1.3算法案例
人教必修三1.3算法案例_高一数学_数学_高中教育_教育专区。§1.3 算法案例(第一课时)——辗转相除法与更相减损术【学习目标】 1. 了解辗转相除法、更相减损术...
1.3.1算法案例学案(一)教师版
第 周 总第 期 高一数学 1.3 算法案例(一) 导学案 装 订 课前演练: 1. 辗转相除法是用于求 的一种方法.这种算法由欧几里得在公元 前 300 年左右首先...
§1.3 算法案例(1)
§1.3 算法案例(1)授课 时间 学习 目标 重点 难点 第周 星期 第 8 节 ...1.辗转相除法与更相减损术 (1)辗转相除法:又叫欧几里得算法,是一种求两个正...
1.3算法案例学案(完美版)_图文
河北衡水重点中学高一数学学案 1.3 算法案例 辗转相除法与更相减损术 教学目标...2、其基本过程是: 第一步,任意给定两个正整数,判断他们是否都是偶数,若是 _...
1.3算法案例(1)
1.3 算法案例(1) 数学组: 时间: 课型:新授课 教学目标 1.知识目标 2....翻译为现代语言如下: 第一步,任意给定两个正整数,判断它们是否都是偶数,若是...
高一 导学案 1.3.1算法案例(一)
必修三 第一章 课题1.3.1 一、预习与质疑(课前完成)(一)预习内容:预习课本34-37页。 (二)预习目标: 算法案例(一) 1.知道辗转相除法与更相减损术中蕴含...
1.3算法案例(一)
《1.3 算法案例》第一课时 3页 免费 1.3.1算法案例(第一课时) 10页 免费...基础教育课程改革实验学科教案教学 内容 教学 目标 1.3.1 辗转相除法与更相减...
更多相关标签: