koorio.com
海量文库 文档专家
当前位置:首页 >> 数学 >>

湖南师大附中高中数学新人教A版必修3课件: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.


推荐相关:

湖南师大附中高中数学新人教A版必修3课件:1.3.1辗转相....ppt

湖南师大附中高中数学新人教A版必修3课件:1.3.1辗转相除法与更相减损术 -


...A版数学必修3课件:1.3.1辗转相除法与更相减损术、秦....ppt

高中人教A版数学必修3课件:1.3.1辗转相除法与更相减损术、秦九韶算法 - 1


...A版数学必修3课件1.3.1 辗转相除法与更相减损术、秦....ppt

高中人教A版数学必修3课件1.3.1 辗转相除法与更相减损术、秦九韶算法_高三数学_数学_高中教育_教育专区。1.3 算法案例 -1- 第1课时 辗转相除法与更相减损...


...1.3.1 辗转相除法与更相减损术、秦九韶算法课件_图....ppt

高中数学新人教A版必修3 1.3.1 辗转相除法与更相减损术、秦九韶算法课件_高一数学_数学_高中教育_教育专区。高中数学新人教A版必修3 1.3.1 辗转相除法与更...


...数学必修三课件高一:1.3.1辗转相除法与更相减损术、....ppt

人教A版高中数学必修三课件高一:1.3.1辗转相除法与更相减损术、秦九韶算法.pptx - 高中数学课件 (金戈铁骑 整理制作) 1.3 算法案例 -2- 第1课时 辗转相...


...数学必修三课件《1-3-1辗转相除法与更相减损术、秦....ppt

人教A版高中数学必修三课件1-3-1辗转相除法与更相减损术、秦九韶算法》 - 高中数学课件 (金戈铁骑 整理制作) 成才之路数学 人教A版必修3 路漫漫其修远...


高中数学 1.3-1辗转相除法与更相减损术课件 新人教A版....ppt

高中数学 1.3-1辗转相除法与更相减损术课件 新人教A版必修3_数学_高中教育_教育专区。1.3 算法案例第一课时 问题提出 ? 1 ? 5730 p?? ? ?2? t 1....


...人教A版)必修3课件:1-3-1 辗转相除法与更相减损术、....ppt

必修3章 第1课时 辗转相除法与 更相减损术、秦九韶算法 第章 算法初步 成才之路 高中新课程 学习指导 人教A版 数学 必修3 课前自主...


【高中数学必修三】1.3.1辗转相除法与更相减损术_图文.ppt

高中数学必修三】1.3.1辗转相除法与更相减损术_数学_高中教育_教育专区。高中数学人教A版必修三课件 1.3.1 案例1、辗转相除法与更相减损术 复习引入回顾...


湖南师大附中高中数学新人教A版必修3课件:1.3.2秦九邵....ppt

湖南师大附中高中数学新人教A版必修3课件:1.3.2秦九邵算法 - 1.3 算法案例 第二课时 问题提出 1.辗转相除法和更相减损术,是求 两个正整数的最大公约数的...


...版高中数学必修三:1.3.1《辗转相除法与更相减损术》....ppt

最新审定人教A版高中数学必修三:1.3.1辗转相除法与更相减损术》ppt(名校课件)_高二数学_数学_高中教育_教育专区。最新审定人教A版高中数学必修三优秀课件 辗转...


...第1课时辗转相除法与更相减损术、秦九韶算法_图文.ppt

2015-2016学年高中数学(人教A版)必修三课件:1.31课时辗转相除法与更相减损术、秦九韶算法 - 成才之路 数学 人教A版 必修3 路漫漫其修远兮 吾将...


...版A必修3课件:1.3算法案例 第1课时 辗转相除法与更相减损术、....ppt

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


湖南师大附中高中数学新人教A版必修3课件:1.3.3K进制化....ppt

湖南师大附中高中数学新人教A版必修3课件:1.3.3K进制化十进制 - 1.3 算法案例 第三课时 问题提出 1.辗转相除法和更相减损术,是求两 个正整数的最大公约数...


...必修三同步课件1.3第1课时辗转相除法与更相减损术、....ppt

【成才之路】2014-2015学年高中数学(人教A版)必修三同步课件1.31课时辗转相除法与更相减损术、秦九韶算 - 【成才之路】2014-2015学年高中数学(人教A版)...


高中数学1.3第1课时辗转相除法与更相减损术、秦九韶算....ppt

高中数学1.31课时辗转相除法与更相减损术、秦九韶算法课件新人教A必修3 - 成才之路 数学 人教A版 必修3 路漫漫其修远兮 吾将上下而求索 第一章 算法...


高中数学人教A版必修三课件1.3.2 辗转相除法与更相减损术.ppt

高中数学人教A版必修三课件1.3.2 辗转相除法与更相减损术 隐藏>> 1.3 算法案例第二课时主讲教师 申东 高中新课程数学必修③ 知识探究( 知识探究():辗转相...


...人教A版)必修3课件:1-3-1 辗转相除法与更相减损术、....ppt

2014《成才之路》高一数学(人教A版)必修3课件:1-3-1 辗转相除法与更相减损术、秦九韶算法_数学_高中教育_教育专区。文档均来自网络,如有侵权请联系我删除文档...


...学年度高中数学 1.3.1 辗转相除法与更相减损术同步....ppt

【金版学案】2013-2014学年度高中数学 1.3.1 辗转相除法与更相减损术同步辅导与检测课件 新人教A版必修3_数学_高中教育_教育专区。算法初步 1 .3 算法案例 ...


...课件:1.3 第1课时 辗转相除法与更相减损术 _图文.ppt

数学人教A必修三新一线同步课件:1.31课时 辗转相除法与更相减损术 _英语_高中教育_教育专区。第一章 算法初步 1.3 算法案例第 1 课时 辗转相除法与更相...

网站首页 | 网站地图
All rights reserved Powered by 酷我资料网 koorio.com
copyright ©right 2014-2019。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com