算法案例.ppt

算法初步
第
一
章
本章内容
算法与程序框图
基本算法语句
算法案例
第一章小结
算法案例
第一课时案例1, 案例2
第二课时案例3
案例1 辗转相除法与更相减损术
案例2 秦九韶算法
第一课时
返回目录
学习要点
1. 用辗转相除法怎样求两个数的最大公约数?
2. 你能写出辗转相除法的程序吗?
3. 用更相减损术怎样求两个数的最大公约数?
4. 你能写出更相减损术的程序吗?
5. 什么是秦九韶算法? 它的特点是什么?
6. 你能写出秦九韶算法的程序吗?
案例1 辗转相除法与更相减损术
问题1. 你能求两个数的最大公约数吗? 看下面一列等式, 请问: 37 是 2146 与 1813 的公约数吗?
2146=18131+333,
1813=3335+148,
333=1482+37,
148=374.
有37的约数,
有37的约数,
有37的约数,
有37的约数,
求两个数的最大公约数的算法步骤:
(1) 大数除以小数取余数;
(2) 较小的数与余数又进行大数除以小数取余数;
如此重复进行, 直到余数为 0.
余数为 0 时的除数就是最大公约数.
这叫辗转相除法, 又叫欧几里得算法.
21461813余333,
1813333余148,
333148余37,
14837余0.
练习: (补充)
用辗转相除法求 2231 和 1403 的公约数.
解:
进行辗转相除
2231=14031+828,
1403=8281+575,
828=5751+253,
575=2532+69,
253=693+46,
69=461+23,
46=232+0.
22311403 余 828,
1403828 余 575,
828575 余 253,
575253 余 69,
25369 余 46,
6946 余 23,
4623 余 0.
最大公约数是23.
用等式表示:
21461813余333,
1813333余148,
333148余37,
14837余0.
程序:
程序框图:
INPUT “输入整数m,n(m>n)”; m,n
DO
r=m MOD n
m=n
n=r
LOOP UNITL r=0
PRINT m
END
m=n
n=r
r=0?
否
求m除以n的余数r
m
n
输入m, n
是
输出m
r
≠0
≠0
≠0
=0.
37
“问题1”中有辗转相除法求最大公约数的程序:
0
【更相减损术】
我国的《九章算术》中, 求两个数的最大公约数的算法采用“更相减损术”, 其算法步骤是:
第一步: 任意给定两个正整数, 判断它们是否都是偶数. 若是, 用 2 约简, 然后执行第二步; 若不是, 直接执行第二步.
第二步: 以较大的数减去较小的数. 若差不等于较小的数, 则用差与较小的数继续进行大减小, 直到差等于较小的数为止.
第三步: 检查是否用 2 约简了, 若是, 第二步最后的差乘以约去的 2 就是最大公约数; 若不是, 最后的差即为最大公约数.
例1. 用更相减损术求 98 与 63 的最大公约数.
解:
98 与 63 中有一个不是偶数, 不能减半.
作辗转相减:
98-63=35,
63-35=28,
35-28=7,
28-7=21,
21-7=14,
14-7=7.
∴ 7是98与63的最大公约数.