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

【数学】1.3.1《算法案例——辗转相除法与更相减损术》课件(人教A版必修3)


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.

辗转相除法是一个反复执行直到余数等于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



思考5:上述求两个正整数的最大公约数 的方法称为辗转相除法或欧几里得算法. 一般地,用辗转相除法求两个正整数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:利用辗转相除法求两数4081与 20723的最大公约数. (53) 20723=4081×5+318;

4081=318×12+265;
318=265×1+53; 265=53×5+0.

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

思考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

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

INPUT “m,n=“;m,n IF m<n THEN a=m m=n n=a END IF K=0 WHILE m MOD 2=0 AND n MOD 2=0 m=m/2 n=n/2 k=k+1 WEND d=m- n

While d<>n IF d>n then m=d ELSE m=n n=d End if d=m-n Wend d=2^k*d PRINT d 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. 更相减损术,就是对于给定的两个正 整数,用较大的数减去较小的数,然后将差 和较小的数构成新的一对数,继续上面的减 法,直到差和较小的数相等,此时相等的两 数即为原来两个数的最大公约数.

小结

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

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

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

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


相关文章:
【数学】1.3.1《算法案例辗转相除法与更相减损术》....ppt
【数学】1.3.1《算法案例辗转相除法与更相减损术》课件(人教A版必修3) - 1.3 算法案例 第一课时 问题提出 ? 1 ? 5730 p?? ? ?2? t 1.研究一...
【数学】1.3.1《算法案例辗转相除法与更相减损术》....ppt
【数学】1.3.1《算法案例辗转相除法与更相减损术》课件(人教A版必修3)_数学_高中教育_教育专区。1.3 算法案例第一课时 小学学过的求两个正数的最大...
【数学】1.3.1《算法案例辗转相除法与更相减损术》....ppt
【数学】1.3.1《算法案例辗转相除法与更相减损术》课件(人教A版必修3) - 1.3 算法案例 第一课时 问题提出 ? 1 ? 5730 p=? ? ?2? t 1.研究一...
...辗转相除法与更相减损术》课件 新人教A版必修3_图....ppt
高考数学一轮复习 1.3.1《算法案例辗转相除法与更相减损术》课件人教A版必修3 - 1.3 算法案例 第一课时 问题提出 1.研究一个实际问题的算法,主要...
...辗转相除法与更相减损术》课件(1)(新人教A版必修3)_....ppt
数学:1.3.1《算法案例-辗转相除法与更相减损术》课件(1)(新人教A版必修3)_数学_高中教育_教育专区。 案例1 辗转相除法与更相减损术 〖创设情景,揭示课题〗...
2012高考数学一轮复习:1.3.1《算法案例辗转相除法....ppt
2012高考数学一轮复习:1.3.1《算法案例辗转相除法与更相减损术》课件(人教A版必修3) - 1.3 算法案例 第一课时 问题提出 1.研究一个实际问题的算法,...
1.3.1《算法案例-辗转相除法与更相减损术》课件(1)(新....ppt
1.3.1《算法案例-辗转相除法与更相减损术》课件(1)(新人教A版必修3)_数学_高中教育_教育专区。 案例1 辗转相除法与更相减损术 〖创设情景,揭示课题〗 [...
数学1.3.1《辗转相除法与更相减损术》课件(新人教A版必....ppt
数学1.3.1《辗转相除法与更相减损术》课件(人教A版必修3) - 1.3 算法案例 第一课时 问题提出 1.研究一个实际问题的算法,主要从 算法步骤、程序框图和...
公开课算法案例辗转相除法与更相减损术课件(人教A....ppt
公开课算法案例辗转相除法与更相减损术课件(人教A版必修3)_数学_高中教育_教育专区。非常精美 1.3 算法案例第一课时 我们是如何求两个正数的最大公约数的...
1.3.1《算法案例--辗转相除法与更相减损术》课件(1)(新....ppt
1.3.1《算法案例--辗转相除法与更相减损术》课件(1)(新人教A版必修3)_初一数学_数学_初中教育_教育专区。算法案例 第一课时 复习引入 1. 回顾算法的三种...
高中数学1.3算法案例--辗转相除法与更相减损术课件新人....ppt
高中数学1.3算法案例--辗转相除法与更相减损术课件人教A版必修3_教学案例/设计_教学研究_教育专区。算法案例 (课时) 1. 回顾算法的三种表述: 自然语言 ...
1.3.1《算法案例--辗转相除法与更相减损术》课件(1)(新....ppt
1.3.1《算法案例--辗转相除法与更相减损术》课件(1)(新人教A版必修3)_政...(2)、现代数学中的更相减损术: 第一步:任意给定两个正整数;判断他们是否都...
1.3.1《算法案例--辗转相除法与更相减损术》课件(1)(新....ppt
1.3.1《算法案例--辗转相除法与更相减损术》课件(1)(新人教A版必修3)_数学_高中教育_教育专区。算法案例 第一课时 复习引入 1. 回顾算法的三种表示方法: ...
高中数学 1.3-1辗转相除法与更相减损术课件 新人教A版....ppt
高中数学 1.3-1辗转相除法与更相减损术课件人教A版必修3_数学_高中教育_教育专区。1.3 算法案例课时 问题提出 ? 1 ? 5730 p?? ? ?2? t 1....
【数学】1.3 算法案例 课件1(人教A版必修3)_图文.ppt
【数学】1.3 算法案例 课件1(人教A版必修3) - 第一章 算法初步 1.3 算法案例 〖创设情景,揭示课题〗 案例1 辗转相除法与更相减损术 [问题1]:在小学,...
高一数学:1.3.1 辗转相除法与更相减损术、秦九韶算法1 ....ppt
1.3.1 辗转相除法与更相减损术、秦九韶算法1 课件(人教A版必修3)_数学_...【数学】1.3.1《算法案例... 25页 免费 1.3.1 辗转相除法与更相... ...
...必修三 1.3.1《算法案例辗转相除法与更相减损术》教....doc
人教A版高中数学必修三 1.3.1《算法案例辗转相除法与更相减损术》教案_教学案例/设计_教学研究_教育专区。高中数学 1.3.1 算法案例辗转相除法与更相减损术...
数学:1.3.1《算法案例(辗转相除法)》课件(新人教版A必....ppt
数学:1.3.1《算法案例(辗转相除法)》课件(人教版A必修3)_理学_高等教育_教育专区。数学:1.3.1《算法案例(辗转相除法)》课件(人教版A必修3) ...
【人教A版】2016年秋高中数学必修三:1.3《算法案例》pp....ppt
人教A版】2016年秋高中数学必修三:1.3《算法案例》ppt课件 - 案例1 辗转相除法与更相减损术 〖创设情景,揭示课题〗 [问题1]:在小学,我们已经学过求最大...
高中数学 1.3.1 辗转相除法与更相减损术、秦九韶算法课....ppt
高中数学 1.3.1 辗转相除法与更相减损术、秦九韶算法课件人教A版必修3_教学案例/设计_教学研究_教育专区。1 .3 算法案例 -* - 第一课时 辗转相除法与...
更多相关标签: