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

【数学】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.


相关文章:
...必修三教案——算法案例(辗转相除法与更相减损...
人教A版数学必修三教案——算法案例(辗转相除法与更相减损术) - §1.3 算法案例 、教材分析 在学生学习了算法的初步知识, 理解了表示算法的算法步骤、 程序...
高中数学 1.3.1 算法案例导学案 新人教A版必修3
高中数学 1.3.1 算法案例导学案 新人教A版必修3 - 1.3.1 算法案例 【学习目标】1.理解辗转相除法与更相减损术的含义,了解其执行过程,并会求最大公约 数...
...章算法案例(1)第一、二课时辗转相除法与更相减...
人教A版高中数学必修三算法案例(1)、二课时辗转相除法与更相减损教案_数学_高中教育_教育专区。第一、二课时 辗转相除法与更相减损术 (1)教学目标 ...
高中数学算法案例辗转相除法和更相减损术学案新人...
通辽市科尔沁区大林镇高中数学 算法案例辗转相除法和更相减损术 学案 新人教版必修 3 课题:1.3 算法案例(1)——辗转相除法和更相减损术 【学习目标】 1. ...
...必修三算法案例第1课时辗转相除法与更相减损术...
人教A版高中数学必修三算法案例第1课时辗转相除法与更相减损术课时练习 - 1.3.1 辗转相除法与更相减损术 一、选择题 1.用辗转相除法求 294 和 84 的最大...
...必修三算法案例第1课时辗转相除法与更相减损术...
人教A版高中数学高一必修三算法案例1课时辗转相除法与更相减损术课时练习_数学_高中教育_教育专区。人教 A 版高中数学高一必修三算法案例1 课时辗转相除法...
高中数学必修3人教A1.3算法案例(教、学案)
高中数学必修3人教A1.3算法案例(教、学案) - 1. 3 算法案例 【教学目标】 : 1.理解辗转相除法与更相减损术中蕴含的数学原理,并能根据这些原理进行算法分析...
人教A版高中数学必修三1-3算法案例教案
人教A版高中数学必修三1-3算法案例教案 - 1.3 算法案例、二课时 辗转相除法与更相减损术 (1)教学目标 (a)知识与技能 1.理解辗转相除法与更相减损术...
人教版高二数学必修3第一章《算法案例》学案(第一...
人教版高二数学必修3《算法案例》学案(第课时) - §1.3 班级:高二( 算法案例 辗转相除法与更相减损术 )班 姓名: 学号: 学习目标: 1.理解辗转...
算法案例《辗转相除法与更相减损术》教学设计
算法案例辗转相除法与更相减损术》教学设计_数学_小学教育_教育专区。高中数学,必修三,算法案例 辗转相除法与更相减损术教学设计 问题 环节 (1)引入课题,求 9...
更多相关标签: