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

20080306高一数学(1.3-1辗转相除法与更相减损术)


1.3

算法案例
第一课时

问题提出

? 1 ? 5730 p?? ? ?2?

t

1.研究一个实际问题的算法,主要从 算法步骤、程序框图和编写程序三方面 展开.在程序框图中算法的基本逻辑结构 有哪几种?在程序设计中基本的算法语 句有哪几种? 2.“求两个正整

数的最大公约数” 是数学中的一个基础性问题,它有各种 解决办法,我们以此为案例,对该问题 的算法作一些探究.

知识探究(一):辗转相除法

思考1:18与30的最大公约数是多少?你 是怎样得到的?

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

思考2:对于8251与6105这两个数,由于 其公有的质因数较大,利用上述方法求 最大公约数就比较困难.注意到 8251=6105×1+2146,那么8251与6105这 两个数的公约数和6105与2146的公约数 有什么关系?

思考3:又6105=2146×2+1813,同理, 6105与2146的公约数和2146与1813的公 约数相等.重复上述操作,你能得到8251 与6105这两个数的最大公约数吗? 8251=6105×1+2146, 6105=2146×2+1813, 2146=1813×1+333, 1813=333×5+148, 333=148×2+37, 148=37×4+0.

思考4:上述求两个正整数的最大公约数 的方法称为辗转相除法或欧几里得算法. 一般地,用辗转相除法求两个正整数m, n的最大公约数,可以用什么逻辑结构来 构造算法?其算法步骤如何设计? 第一步,给定两个正整数m,n(m>n). 第二步,计算m除以n所得的余数r. 第三步,m=n,n=r. 第四步,若r=0,则m,n的最大公约数等 于m;否则,返回第二步.

思考5:该算法的程序框图如何表示?
开始
输入m,n

求m除以n的余数r
m=n n=r r=0? 是



输出m 结束

思考6:该程序框图对应的程序如何表述?
开始 输入m,n 求m除以n的余数r

m=n
n=r r=0? 是 输出m 结束 否

INPUT m,n DO r=m MODn m=n n=r LOOP UNTIL r=0 PRINT m END

思考7:如果用当型循环结构构造算法, 则用辗转相除法求两个正整数m,n的最 大公约数的程序框图和程序分别如何表 示?

开始
输入m,n

n=r
m=n 求m除以n的余数r n>0? 否 输出m 结束



INPUT m,n WHILE n>0 r=m MODn m=n n=r WEND PRINT m END

知识探究(二):更相减损术

思考1:设两个正整数m>n,若m-n=k,则m 与n的最大公约数和n与k的最大公约数相 等.反复利用这个原理,可求得98与63的 最大公约数为多少? 98-63=35, 63-35=28, 35-28=7, 28-7=21, 21-7=14, 14-7=7.

思考2:上述求两个正整数的最大公约数 的方法称为更相减损术.一般地,用更相 减损术求两个正整数m,n的最大公约数, 可以用什么逻辑结构来构造算法?其算 法步骤如何设计?
第一步,给定两个正整数m,n(m>n). 第二步,计算m-n所得的差k. 第三步,比较n与k的大小,其中大者用m表 示,小者用n表示. 第四步,若m=n,则m,n的最大公约数等于 m;否则,返回第二步.

思考3:该算法的程序框图如何表示?
开始 输入m,n m≠n? m=k




是 k=m-n n>k? 是 m=n n=k 输出m 结束

思考4:该程序框图对应的程序如何表述? 开始 INPUT m,n WHILE m<>n 输入m,n k=m-n IF n>k THEN 否 m≠n? m=n 是 n=k k=m-n m=k ELSE m=k 否 输出m n>k? END IF 是 WEND 结束 m=n PRINT m n=k END

“更相减损术”在中国古代数学专著 《九章算术》中记述为: 可半者半之,不可半者,副置分母、子 之数,以少减多,更相减损,求其等也, 以等数约之.

理论迁移

例1 分别用辗转相除法和更相减损 术求168与93的最大公约数. 辗转相除法:168=93×1+75, 93=75×1+18, 75=18×4+3, 18=3×6.

更相减损术:168-93=75, 93-75=18, 75-18=57, 57-18=39, 39-18=21, 21-18=3, 18-3=15, 15-3=12, 12-3=9, 9-3=6, 6-3=3.

例2 求325,130,270三个数的最大 公约数. 因为325=130×2+65,130=65×2, 所以325与130的最大公约数是65. 因为270=65×4+10,65=10×6+5, 10=5×2,所以65与270最大公约数是5. 故325,130,270三个数的最大公约 数是5.

小结作业 1.辗转相除法,就是对于给定的两个正整 数,用较大的数除以较小的数,若余数不为 零,则将余数和较小的数构成新的一对数, 继续上面的除法,直到大数被小数除尽为止, 这时的较小的数即为原来两个数的最大公约 数. 2. 更相减损术,就是对于给定的两个正 整数,用较大的数减去较小的数,然后将差 和较小的数构成新的一对数,继续上面的减 法,直到差和较小的数相等,此时相等的两 数即为原来两个数的最大公约数.

作业: P45练习:1. P48习题1.3A组:1.


相关文章:
高二数学必修3第一章算法初步知识点:辗转相除法与更相减损术
高二数学对于知识点的掌握的要求是比较高的。小编准备了高二数学必修 3 第一章算法初步 知识点,希望能帮助到大家。1.3.1 辗转相除法与更相减损术 1、辗转相...
2015-2016学年高中数学 1.3.1辗转相除法与更相减损术、秦九韶算法课后作业 新人教A版必修3
2015-2016学年高中数学 1.3.1辗转相除法与更相减损术、秦九韶算法课后作业 新人教A版必修3_数学_高中教育_教育专区。第一课时 1.3 算法案例 辗转相除法与更...
1.3算法案例第一课时辗转相除法与更相减损术
1.3算法案例第一课时辗转相除法与更相减损术_其它课程_高中教育_教育专区。1.3 算法案例学习目标导航 1.课标要求: (1)理解辗转相除法与更相减损术中蕴含的数学...
1.3第1课时 辗转相除法与更相减损术、秦九韶算法《云师大“1+1”专业数学辅导》
1.31课时 辗转相除法与更相减损术、秦九韶算法《云师大“1+1”专业数学辅导》_数学_高中教育_教育专区。辗转相除法与更相减损术、秦九韶算法 (教师用书...
辗转相除法与更相减损术同步练习
辗转相除法与更相减损术同步练习_军事/政治_人文社科_专业资料。辗转相除法与更...1/2 相关文档推荐 高一数学必修3同步练习:... 8页 4下载券 同步练习:(七)...
人教A版数学必修三教案:§1.3算法案例(辗转相除法与更相减损术)
人教A版数学必修三教案:§1.3算法案例(辗转相除法与更相减损术)_数学_高中教育_教育专区。备课大师:免费备课第一站! §1.3 算法案例一、教材分析在学生学习了...
辗转相除法与更相减损术
掌握必备的数学知识,从 而达到知识与技能,过程与方法,情感与态度三位一体的统一...比较辗转相除法与更相减损术的区别 3.比较辗转相除法与更相减损术的区别 (1)...
辗转相除法与更相减损数
辗转相除法与更相减损数_理化生_高中教育_教育专区。1. 3.1 辗转相除法与更相减损术 学习目标:理解辗转相除法与更相减损术的含义和运算. 知识梳理: 1.辗转相...
人教版高中数学必修3案例辗转相除法、更相减损术和秦九韶算法(第1课时)教案
人教版高中数学必修3案例辗转相除法更相减损术和秦九韶算法(第1课时)教案_数学_高中教育_教育专区。1.3 算法案例:辗转相除法更相减损术和秦九韶算法 (第...
更多相关标签:
辗转相除法 | 辗转相除法原理 | 辗转相除法c语言 | 最大公约数辗转相除法 | 多项式辗转相除法 | 欧几里得辗转相除法 | 辗转相除法证明 | 辗转相除法的算法步骤 |