人教A版高中数学必修3第一章算法案例1.3 算法与案例（第一课时）课件（共15张PPT）
文档属性
| 名称 | 人教A版高中数学必修3第一章算法案例1.3 算法与案例（第一课时）课件（共15张PPT） |  | |
| 格式 | zip | ||
| 文件大小 | 465.0KB | ||
| 资源类型 | 教案 | ||
| 版本资源 | 人教新课标A版 | ||
| 科目 | 数学 | ||
| 更新时间 | 2020-04-18 15:38:04 | ||
图片预览
文档简介
(共15张PPT)
1.3 算 法 案 例
案例1 辗转相除法与更相减损术
大家喜欢打乒乓球吧，由于东西方文化及身体条件的不同，西方人喜欢横握球拍打球，东方人喜欢直握拍打球。对于同一个问题，东西方处理问题方式是有所不同的。在小学，我们学过求两个正整数的最大公约数的方法：先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后所把所有的除数连乘起来。当两个数公有的质因数较大时(如8251与6105)，使用这种方法求最大公约数就比较困难。下面我们介绍两种不同的算法------辗转相除法与更相减损术，由此可以体会东、西方文化的差异。
1、求两个正整数的最大公约数
（1）求25和35的最大公约数 （2）求49和63的最大公约数
2、求8251和6105的最大公约数
所以，25和35的最大公约数为5
所以，49和63的最大公约数为7
1.辗转相除法（欧几里得算法）
观察用辗转相除法求8251和6105的最大公约数的过程
第一步 用两数中较大的数除以较小的数，求得商和余数 8251=6105×1+2146
结论： 8251和6105的公约数就是6105和2146的公约数，求8251和6105的最大公约数，只要求出6105和2146的公约数就可以了。
第二步 对6105和2146重复第一步的做法 6105=2146×2+1813 同理6105和2146的最大公约数也是2146和1813的最大公约数。
完整的过程
8251=6105×1+2146
6105=2146×2+1813
2146=1813×1+333
1813=333×5+148
333=148×2+37
148=37×4+0
例2 用辗转相除法求225和135的最
大公约数
225=135×1+90
135=90×1+45
90=45×2
显然37是148和37的最大公约数，也就是8251和6105的最大公约数
显然45是90和45的最大公约数，也就是225和135的最大公约数
从上面的两个例子可以看出计算的规律是什么？
S1：用大数除以小数
S2：除数变成被除数，余数变
成除数
S3：重复S1，直到余数为0
利用辗转相除法求最大公约数的步骤如下：
第一步：用较大的数m除以较小的数n得到一个商q0和一个余数r0；(m=n×q0+r0)
第二步：若r0＝0，则n为m，n的最大公约数；若r0≠0，则用除数n除以余数r0得到一个商q1和一个余数r1；(n=r0×q1+r1)
第三步：若r1＝0，则r0为m，n的最大公约数；若r1≠0，则用除数r0除以余数r1得到一个商q2和一个余数r2；(r0=r1×q2+r2)
……
依次计算直至rn＝0，此时所得到的rn-1 即为所求的最大公约数。
第一步,给定两个正数m,n
第二步,如果m 否则计算m除以n所得到余数r;
第三步,m=n,n=r
第四步,若r=0,则m,n的最大公约数等于n;
否则返回第二步
辗转相除法求最大公约数算法：
否
辗转相除法的程序框图及程序:
开始
输入两个正数m,n
mr=m MOD n
r<>0?
输出n
结束
m=x
m=n
n=r
否
是
是
x=n
n=m
练习1：利用辗转相除法求两数4081与20723的最大公约数.
(53)
20723=4081×5+318;
4081=318×12+265;
318=265×1+53;
265=53×5+0.
2.更相减损术:
我国早期也有解决求最大公约数问题的算法，就是更相减损术。
更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母·子之数，以少减多，更相减损，求其等也，以等数约之。
翻译出来为：第一步：任意给出两个正数；判断它们是否都是偶数。若是，用2约简；若不是，执行第二步。
第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数。
例2 用更相减损术求98与63的最大公约数.
解：由于63不是偶数，把98和63以大数减小数，并辗转相减，
即：98－63＝35;
63－35＝28;
35－28＝7;
28－7＝21;
21－7＝14;
14－7＝7.
所以，98与63的最大公约数是7。
练习2：用更相减损术求两个正数84与72的最大公约数。
(12)
第一步,给定两个正整数,不妨设m>n,
第二步,若m,n都是偶数,则不断用2约简,使他们不同时是偶数,约简后的两个数仍记为m,n
第三步,d=m-n
第四步,判断”d<>0”是否成立,若是,则将n,d 中较大者记为m,较小的记为n,返回第三步;否则,2^k *d(k是约简整数的2的个数)为所求的最大公约数.
更相减损术算法
是
否
n=d
是
是
否
否
d=m-n
INPUT “m,n=“;m,n
IF m 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
3.辗转相除法与更相减损术的比较:
（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主;计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。
（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到.
1.3 算 法 案 例
案例1 辗转相除法与更相减损术
大家喜欢打乒乓球吧，由于东西方文化及身体条件的不同，西方人喜欢横握球拍打球，东方人喜欢直握拍打球。对于同一个问题，东西方处理问题方式是有所不同的。在小学，我们学过求两个正整数的最大公约数的方法：先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后所把所有的除数连乘起来。当两个数公有的质因数较大时(如8251与6105)，使用这种方法求最大公约数就比较困难。下面我们介绍两种不同的算法------辗转相除法与更相减损术，由此可以体会东、西方文化的差异。
1、求两个正整数的最大公约数
（1）求25和35的最大公约数 （2）求49和63的最大公约数
2、求8251和6105的最大公约数
所以，25和35的最大公约数为5
所以，49和63的最大公约数为7
1.辗转相除法（欧几里得算法）
观察用辗转相除法求8251和6105的最大公约数的过程
第一步 用两数中较大的数除以较小的数，求得商和余数 8251=6105×1+2146
结论： 8251和6105的公约数就是6105和2146的公约数，求8251和6105的最大公约数，只要求出6105和2146的公约数就可以了。
第二步 对6105和2146重复第一步的做法 6105=2146×2+1813 同理6105和2146的最大公约数也是2146和1813的最大公约数。
完整的过程
8251=6105×1+2146
6105=2146×2+1813
2146=1813×1+333
1813=333×5+148
333=148×2+37
148=37×4+0
例2 用辗转相除法求225和135的最
大公约数
225=135×1+90
135=90×1+45
90=45×2
显然37是148和37的最大公约数，也就是8251和6105的最大公约数
显然45是90和45的最大公约数，也就是225和135的最大公约数
从上面的两个例子可以看出计算的规律是什么？
S1：用大数除以小数
S2：除数变成被除数，余数变
成除数
S3：重复S1，直到余数为0
利用辗转相除法求最大公约数的步骤如下：
第一步：用较大的数m除以较小的数n得到一个商q0和一个余数r0；(m=n×q0+r0)
第二步：若r0＝0，则n为m，n的最大公约数；若r0≠0，则用除数n除以余数r0得到一个商q1和一个余数r1；(n=r0×q1+r1)
第三步：若r1＝0，则r0为m，n的最大公约数；若r1≠0，则用除数r0除以余数r1得到一个商q2和一个余数r2；(r0=r1×q2+r2)
……
依次计算直至rn＝0，此时所得到的rn-1 即为所求的最大公约数。
第一步,给定两个正数m,n
第二步,如果m
第三步,m=n,n=r
第四步,若r=0,则m,n的最大公约数等于n;
否则返回第二步
辗转相除法求最大公约数算法：
否
辗转相除法的程序框图及程序:
开始
输入两个正数m,n
m
r<>0?
输出n
结束
m=x
m=n
n=r
否
是
是
x=n
n=m
练习1：利用辗转相除法求两数4081与20723的最大公约数.
(53)
20723=4081×5+318;
4081=318×12+265;
318=265×1+53;
265=53×5+0.
2.更相减损术:
我国早期也有解决求最大公约数问题的算法，就是更相减损术。
更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母·子之数，以少减多，更相减损，求其等也，以等数约之。
翻译出来为：第一步：任意给出两个正数；判断它们是否都是偶数。若是，用2约简；若不是，执行第二步。
第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数。
例2 用更相减损术求98与63的最大公约数.
解：由于63不是偶数，把98和63以大数减小数，并辗转相减，
即：98－63＝35;
63－35＝28;
35－28＝7;
28－7＝21;
21－7＝14;
14－7＝7.
所以，98与63的最大公约数是7。
练习2：用更相减损术求两个正数84与72的最大公约数。
(12)
第一步,给定两个正整数,不妨设m>n,
第二步,若m,n都是偶数,则不断用2约简,使他们不同时是偶数,约简后的两个数仍记为m,n
第三步,d=m-n
第四步,判断”d<>0”是否成立,若是,则将n,d 中较大者记为m,较小的记为n,返回第三步;否则,2^k *d(k是约简整数的2的个数)为所求的最大公约数.
更相减损术算法
是
否
n=d
是
是
否
否
d=m-n
INPUT “m,n=“;m,n
IF 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
3.辗转相除法与更相减损术的比较:
（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主;计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。
（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到.