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

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课时)
1.3 算法案例(第一课时)平塘民族中学高二年级 周金顺 学习目标: 1、理解辗转相除法与更相减损术中蕴含的数学原理,并能根据这些原理进行算法分析; 2、了解秦九...
1.3算法案例教案
1.3算法案例教案_数学_高中教育_教育专区。算法案例 (第一课时) 教学目标 掌握求最大公约数的方法:辗转相除法、更相减损术 教学重点 辗转相除法、更相减损术 ...
1.3.1算法案例学案(一)教师版
第 周 总第 期 高一数学 1.3 算法案例(一) 导学案 装 订 课前演练: 1. 辗转相除法是用于求 的一种方法.这种算法由欧几里得在公元 前 300 年左右首先...
1.3算法案例(教、学案)
1.3.1 算法案例学案(一)教... 2页 1财富值 必修1详细教案+导学案 4页 1财富值 高中数学新课程必修三第一... 12页 5财富值如要投诉违规内容,请到百度文...
1.3算法案例(第1课时)
宜昌市第十八中学数学教学案学习课题:1.3 算法案例(第 1 课时) 学习目标:1.了解什么是辗转相除法与更相减损术,并学会编写辗转相除法的程 序框图及程序;2. 了...
高中数学必修3《1.3算法案例)》教案设计
高中数学必修3《1.3算法案例)》教案设计_数学_高中教育_教育专区。www.xkb1.com 新课标第一网系列资料 www.xkb1.com 新课标第一网不用注册,免费下载! 1.3...
1.3算法案例教案
1.3算法案例教案_数学_高中教育_教育专区。考试指南报——课堂网(www.k45.cn) 算法案例一. 【课标要求】通过阅读中国古代数学中的算法案例,体会中国古代数学对...
《1.3 算法案例》第一课时
数学必修三,第一章算法,分课时习题数学必修三,第一章算法,分课时习题隐藏>> 必修3 数学(适用新课标人教版) 1.3 算法案例一、选择题 1、把88化为五进制数是...
1.3_算法案例
课时安排 3 课时 教学过程 第 1 课时 案例 1 辗转相除法与更相减损术 导入...辗转相除法求两个数的最大公约数,其算法步骤可以描述如下: 1 第一步,给定两...
更多相关标签:
1.3算法案例 | 1.3算法案例教案 | 1.3算法案例ppt | 算法案例ppt | 智能算法30个案例分析 | 算法案例 | pagerank算法应用案例 | 算法的概念和案例 |