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

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高中数学 1.3.1算法案例辗转相除法与更相减损术教...
2016-2017学年新人教A版必修3高中数学 1.3.1算法案例辗转相除法与更相减损术教案(精品)_数学_高中教育_教育专区。高中数学 1.3.1 算法案例辗转相除法与更相...
...高一数学备课教案:1.3.3《辗转相除法与更相减损术》...
2015-2016学年湖北十堰郧阳中学高一数学备课教案:1.3.3《辗转相除法与更相减损术》(新人教B版必修3)_高中教育_教育专区。§1.3 辗转相除法与更相减损术教学...
...版必修三)第一章 1.3.1 辗转相除法与更相减损术(含...
高中数学课时训练(人教版必修三)第一章 1.3.1 辗转相除法与更相减损术(含答案)_数学_高中教育_教育专区。高中数学人教A版必修三课时训练(含答案) ...
...市郧阳中学高中数学 1.3辗转相除法与更相减损术教案...
湖北省十堰市郧阳中学高中数学 1.3辗转相除法与更相减损术教案 新人教B版必修3_数学_高中教育_教育专区。§1.3 辗转相除法与更相减损术教学目标:1 理解辗转相...
1.3第1课时 辗转相除法与更相减损术、秦九韶算法《云师...
1.31课时 辗转相除法与更相减损术、秦九韶算法《云师大“1+1”专业数学辅导》_数学_高中教育_教育专区。辗转相除法与更相减损术、秦九韶算法 (教师用书...
1.3.1 辗转相除法与更相减损术 教案2
让更多的孩子得到更好的教育 1.3.1 算法案例---辗转相除法与更相减损术 教学要求: 理解辗转相除法与更相减损术中蕴含的数学原理, 并能根据这些原理进行算法分...
...三教案:§1.3算法案例(辗转相除法与更相减损术)
人教A版数学必修三教案:§1.3算法案例(辗转相除法与更相减损术)_数学_高中教育_教育专区。备课大师:免费备课第一站! §1.3 算法案例一、教材分析在学生学习了...
§1.3.1辗转相除法与更相减损术学案
习活动内容 §1.3.1 辗转相除法与更相减损术 年级: 使用学生: 高一年级 课时: 使用时间: 1 课时 日 数学 蒋继荣 年月 2.辗转相除法:古希腊求两个正整数...
高中数学 1.3辗转相除法与更相减损术教案 新人教B版必...
高中数学 1.3辗转相除法与更相减损术教案 新人教B版必修3 有效,简洁有效,简洁隐藏>> §1.3 辗转相除法与更相减损术教学目标:1 理解辗转相除法与更相减损术...
...1.3 算法案例 第一课时 辗转相除法与更相减损术学案...
河南省确山县第二高级中学高中数学 1.3 算法案例 第一课时 辗转相除法与更相减损术学案 新人教A版必修3_高二数学_数学_高中教育_教育专区。河南省确山县第二高...
更多相关标签: