kl800.com省心范文网

算法案例1——辗转相除法与更相减损术


1. 回顾算法的三种表述:
自然语言 程序框图 (三种逻辑结构) 程序语言 (五种基本语句) 2. 思考:

小学学过的求两个数的最大公约数的方法? 先用两个公有的质因数连续去除,一直 除到所得的商是互质数为止,然后把所有的 除数连乘起来.

例:求下面两个正整数的最大公约数:

(1)求25和35的最大公约

数 (2)求49和63的最大公约数
(1) 5

25
5

35
7

(2) 7

49

63

7

9

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

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

例:如何算出8251和6105的最大公约数? 思考:除了用这种方法外还有没有其它方法?

(13分钟)

(9分钟)

讨论1:辗转相除法与更相减损法之间有什么区别与联系 呢? 讨论2:应用辗转相除法与更相减损法求最大公约数要注 意什么呢?

要求: 组长负责全员参与,分工协作。 先比对答案,然后探讨解题思路,总结解题规律 方法。

(8分钟)

要求:

大声,规范,清晰,迅速(在2—3分钟内书写完)
组长负责核对答案和讲解,然后回答其他同学的提问和质疑

(9分钟)

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

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

完整的过程
8251=6105×1+2146 6105=2146×2+1813 2146=1813×1+333

例: 用辗转相除法求225和135的最大公约数 225=135×1+90 135=90×1+45 90=45×2 显然45是90和45的最大公约数,也就是 225和135的最大公约数 思考:从上面的两个例子中可以看出计 算的规律是什么?

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

S1:用大数除以小数

显然37是148和37的最大公约数, S2:除数变成被除数,余数变成除数 也就是8251和6105的最大公约 S3:重复S1,直到余数为0 数

辗转相除法是一个反复执行直到余数等于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)、算法步骤: 第一步:输入两个正整数m,n(m>n). 第二步:计算m除以n所得的余数r.

第三步:m=n,n=r.
第四步:若r=0,则m,n的最大公约数等于m; 否则转到第二步. 第五步:输出最大公约数m.

(2)、程序框图:
开始 输入m,n r=m MOD n m=n n=r 否 r=0? 是 输出m 结束

(3)、程序:
INPUT “m,n=“;m,n DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m

END

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

2、定义:

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

3、方法: 例: 用更相减损术求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

小结

比较辗转相除法与更相减损术的区别
(1)都是求最大公约数的方法,计算上辗转相除

法以除法为主,更相减损术以减法为主,计算次数

上辗转相除法计算次数相对较少,特别当两个数字
大小区别较大时计算次数的区别较明显。 (2)从结果体现形式来看,辗转相除法体现结果 是以相除余数为0则得到,而更相减损术则以减数与 差相等而得到。

1、用更相减损术求两个正数84与72的最大公约数. 思路分析:先约简,再求21与18的最大公约数, 然后乘以两次约简的质因数4。 2、求324、243、135这三个数的最大公约数。 思路分析:求三个数的最大公约数可以先求出两个 数的最大公约数,第三个数与前两个数的最大公约 数的最大公约数即为所求。

(3)、程序
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

思考:你能根据更相减损术设计程序,求两个 正整数的最大公约数吗?

(1)、算法步骤 第一步:输入两个正整数a,b(a>b); 第二步:若a不等于b ,则执行第三步;否则转 到第五步; 第三步:把a-b的差赋予r; 第四步:如果b>r, 那么把b赋给a,把r赋给b;否 则把r赋给a,执行第二步;

第五步:输出最大公约数b.

(2)、程序框图
开始
输入a,b a≠b? 是 r=a-b a=r 否 r<b? 是 a=b b=r 输出b



结束


第8课时-§1.3算法案例——辗转相除法与更相减损术

北京师范大学(珠海)附属高级中学 2011 级 高二年级第二学期(理科数学)备课组教案课题:§1.3 算法案例——辗转相除法与更相减损术 教学目标: 知识与能力:理解...

1.3算法案例第一课时辗转相除法与更相减损术

1.3算法案例第一课时辗转相除法与更相减损术_其它课程_高中教育_教育专区。1.3 算法案例学习目标导航 1.课标要求: (1)理解辗转相除法与更相减损术中蕴含的数学...

人教A版数学必修三教案:§1.3算法案例(辗转相除法与更相减损术)

二、教学目标 1、知识与技能 (1)理解辗转相除法与更相减损术中蕴含的数学原理,并能根据这些原理进行算法分 析。 (2)基本能根据算法语句与程序框图的知识设计...

1.3第1课时 辗转相除法与更相减损术、秦九韶算法《云师大“1+1”专业数学辅导》

(见学生用书第 22 页) 课标解读 2.理解辗转相除法更相减损术、秦九韶算法 的原理.(重点) 3.三种算法的框图及程序应用.(难点) 1.通过案例,进一步体会算法...

人教版高中数学必修3案例辗转相除法、更相减损术和秦九韶算法(第1课时)教案

人教版高中数学必修3案例辗转相除法更相减损术和秦九韶算法(第1课时)教案_数学_高中教育_教育专区。1.3 算法案例:辗转相除法更相减损术和秦九韶算法 (第...

高一数学必修3同步练习:1-3-1辗转相除法与更相减损术、秦九韶算法

高一数学必修3同步练习:1-3-1辗转相除法与更相减损术、秦九韶算法_高一数学_数学_高中教育_教育专区。高一数学必修3全册同步1-3-1 辗转相除法与更相减损术、...

2015-2016学年高中数学 1.3.1辗转相除法与更相减损术、秦九韶算法课后作业 新人教A版必修3

2015-2016学年高中数学 1.3.1辗转相除法与更相减损术、秦九韶算法课后作业 新人教A版必修3_数学_高中教育_教育专区。第一课时 1.3 算法案例 辗转相除法与更...

高二数学必修3第一章算法初步知识点:辗转相除法与更相减损术

小编准备了高二数学必修 3 第算法初步 知识点,希望能帮助到大家。1.3.1 辗转相除法与更相减损术 1、辗转相除法。也叫欧几里德 算法,用辗转相除法求最...

辗转相除法和更相减损术

今天我说课的内容是人教版必修三第一章《算法初步》第三节《算法案例》第一...4. 教学重点和难点: (1) 重点:探索辗转相除法和更相减损术求最大公约数的...

辗转相除法的算法步骤 | 辗转相除法算法 | 辗转相除法的算法 | 更相减损术算法 | 算法案例ppt | 智能算法30个案例分析 | 算法案例 | pagerank算法应用案例 |