高一数学人教A版必修3课件:1.3算法案例


一位美国的幼儿园老师为了教育孩子火海逃生,引导学生做了一个非 非常有趣的游戏──“火海逃生”。老师将许多乒乓球放进瓶子,只露出 系着的棉线。花瓶代表大楼,细细的瓶颈是惟一的出口,七只乒乓球则 是楼里的居民,要求当大楼突然起火时,全体居民能在短时间里安全逃 离。七名学生兴奋地上场了,他们各执一根棉线,报警器一响,都以最 快的反应拉扯绳子,可一个“人”也没能脱离火海,原来,七只乒乓球都 卡在了瓶口。又开始了第二次实验? 这几个学生面面相觑,只见其中一个小声跟同伴们商量了几句,这 回大家没有各顾各地拉绳子,而是由左到右依次地拉。果然,报警 器的尾音还没结束,七位“居民”已离开了出口,转移到了安全地带。

运筹帷幄,决胜千里

算法案例之求最大公约数
例、求18与24的最大公约数:

解:2 1 8 2 4 用公有质因数2除, 3 9 12 用公有质因数3除, 3 4 3和4互质不除了。 得:18和24最大公约数是:2×3=6

短除法

求以下几组正整数的最大公约数。 (注:若整数m和n满足n整除m,则(m,n)=n。用(m,n)来表示 m和n的最大公约数。)

(1)(18,30) 6; (3)(63,63) 63; (5)(301,133 ) 7;

(2)(24,16) (4)(72,8)

8; 8;

想一想,如何求8251与6105的最大公约数?

开始 输入:m,n m>n? Y

穷举法
穷举法(也叫枚举法) 步骤: 从两个数中较小数开始 由大到小列举,直到找到公 约数立即中断列举,得到的 公约数便是最大公约数 。

N

t=m,m=n,n=t
i=m+1 i=i-1

m MOD i=0且n MOD i=0?

N

Y
输出:i 结束

辗转相除法
定理: 已知m,n,r为正整数,若m=nq+r(0≤r<n)(即r=m MOD n),则(m,n)=(n,r)。

分析:m=nq+r r=m-nq

…… ① …… ②

例1、求8251和6105的最大公约数。 解: (8251,6105) 8251=6105×1+2146 =(6105,2146) 6105=2146 ×2+1813 =(2146,1813) 2146=1813 ×1+333 =(1813,333) 1813=333 ×5+148 =(333,148) 333=148 ×2+37 =(148,37) 148=37 ×4 =37

练习:用辗转相除法求下列两数的最大公约数: (1)(225,135) 45 (2)(98,196) 98 24 (3)(72,168) (4)(153,119) 17

8251和6105的最大公约数 解: (8251,6105) 8251=6105×1+2146 =(6105,2146) 6105=2146 ×2+1813 =(2146,1813) 2146=1813 ×1+333 =(1813,333) 1813=333 ×5+148 =(333,148) 333=148 ×2+37 =(148,37) =37 148=37 ×4
关系式m=np+r中m,n,r得取值变化情况 次数 m n r 1 8251 6105 2146 2 6105 2146 1813 3 2146 1813 333 4 1813 333 148 5 333 148 37 6 148 37

0

思考:辗转相除直到何时结束?主要运用的是哪种算法结构?
辗转相除法是一个反复执行直到余数等于0停止的步骤, 这实际上是一个循环结构 辗转相除法求两个数的最大公约数,其算法可以描述如下: ① 输入两个正整数m和n; ② 求余数r:计算m除以n,将所得余数存放到变量r中; ③更新被除数和余数:m=n,n=r。 ④判断余数r是否为0:若余数为0则输出结果,否则转 向第②步继续循环执行。 如此循环,直到得到结果。

开始 输入:m,n r=m MOD n m=n n=r

r=0? Y
输出:m 结束

N

程序: INPUT “m,n=”;m,n DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m END

更相减损术
同理:a,b,c为正整数,若a-b=c,则(a,b)=(b,c)。

“更相减损术”(也是求两个正整数的最大公约数的算法) 步骤: 第一步:任意给定两个正整数;判断他们是否都是偶数。 若是,则用2约简;若不是则执行第二步。
第二步:以较大的数减较小的数,接着把所得的差与较 小的数比较,并以大数减小数。继续这个操作,直到所 得的减数和差相等为止,则这个等数就是所求的最大公 约数。

例、用更相减损术求98与63的最大公约数 (自己按照步骤求解) 解:由于63不是偶数,把98和63以大数减小数,并辗转相减。 (98,63) =(63,35) 98-63=35 63-35=28 =(35,28)

35-28=7
28-7=21 21-7=14 14-7=7

=(28,7)
=(21,7) =(14,7) =(7,7) =

7

所以,98和63的最大公约数等于7。

练习:用更相减损术求下列两数的最大公约数:

(1)(225,135) 45 (3)(72,168) 24

(2)(98,196) 98 (4)(153,119) 17

例 用更相减损术求98与63的最大公约数 解:由于63不是偶数,把98和63以大数减小数, 并辗转相减 (98,63) 98-63=35 =(63,35) 63-35=28 =(35,28) 35-28=7 =(28,7) 28-7=21 =(21,7) 21-7=14 =(14,7) 14-7=7 =(7,7) 所以,98和63的最大公约数等于7。 =7 关系式a-b=c中a,b,c得取值变化情况

次数 a b c

1 98 63 35

2 63 35 28

3 35 28 7

4 28 7 21

5 21 7 14

6 14 7

7

思考:更相减损直到何时结束?运用的是哪种算法结构?
更相减损是一个反复执行直到减数等于差时停止的步骤, 这实际也是一个循环结构

开始 输入:a,b i=0

a MOD 2=0且b MOD 2=0? N

b>a? Y
t=a,a=b,b=t a=a-b N a=b? Y 输出:a×2i 结束

N

程序: INPUT “a,b”;a,b i=0 WHILE a MOD 2=0 AND b MOD 2=0 a=a/2 b=b/2 i=i+1 i=i+1 Y WEND a=a/2,b=b/2 DO IF b>a THEN t=a a=b b=t END IF a=a-b LOOP UNTIL a=b PRINT a*2^i END

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

作业: P38 习题:1.3 第一题


相关文档

高一数学人教A版必修3课件:1.3算法案例(第1课时)
高一数学人教A版必修3课件:1-3 《算法案例的应用习题分析》
高一数学人教A版必修3课件:1.3算法案例(第3课时)
高一数学(人教A版)必修3课件:第一章 算法初步
高一数学人教A版必修3课件:算法初步复习
高一数学人教A版必修3课件:算法案例
高一数学人教A版必修3课件:算法案例-进位制
高一数学人教A版必修3课件:1.3算法案例(第2课时)
高一数学人教A版必修3课件:1.1.1 算法的概念 三
高一数学人教A版必修3课件:算法案例-秦九韶算法
电脑版