文档介绍：一种科学只有在成功地运用数学时,才算达到完善的地步
数学, 科学的皇后; 数论, 数学的皇后
算法是数学及其应用的重要组成部分,是计算科学的重要基础
数学是科学的大门和钥匙
§ 算法案例
1
问题1: (1)求30和18的最大公约数,即gcd(18,30)=? (2)求gcd(8251,6105)=?
gcd(30,18)=gcd(18,12)
解法二:30=18×1+12
(1)解法一:(小学已学的短除法)
18=12×1+6
gcd(18,12)=gcd(12,6)
12=6×2+0
gcd(12,6)=6
即gcd(30,18)=6
这就是求两个正整数的最大公约数的古老有效的算法---辗转相除法(欧几里得算法)
§---辗转相除法和更相减损术
2
8251=6105×1+2146
6105=2146×2+1813
2146=1813×1+333
1813=333×5+148
333=148×2+37
148=37×4+0
gcd(8251,6105)=37
2:gcd(8251,6105)=?
§---辗转相除法和更相减损术
思考1:你能用自然语言描述用辗转相除法求8251和6105的最大公约数的算法步骤吗?
3
思考: 2,你能把辗转相除法求任意两个正整数m,n(m>n)的最大公约数编成一个计算机程序吗?
§---辗转相除法和更相减损术
4
写算法步骤:
第一步,给定两个正整数m,n
第二步,计算m除以n的余数为r
第三步,m=n,n=r
第四步,若r=0,则m,n的最大公约数等于m,否则,返回第二步。
§---辗转相除法和更相减损术
5
画程序框图
关键:确定框图中所用到的结构
确定循环结构:
1,初始化条件:m,n
2,确定循环体:m=n×q+r
m=n,n=r
3,设置循环控制条件:r=0
循环结构的类型选择:直到型或当型
§---辗转相除法和更相减损术
6
编制程序:
直到型:
INPUT m,n
DO
r=m MOD n
m=n
n=r
LOOP UNTIL r=0
PRINT m
END
§---辗转相除法和更相减损术
7
当型结构:
INPUT m,n
r=1
WHILE r >0 r=m MOD n
m=n
n=r
WEND
PRINT m
END
只要r≠0都可以
§---辗转相除法和更相减损术
8
自主学习 1 ,请阅读P36 –P37《九章算术》中介绍的“更相减损术”求两个正整数的最大公约数的算法。并体会例题1求98和63的最大公约数的过程,设计程序。
§---辗转相除法和更相减损术
9
程序参考:
m=98
n=63
DO d=ABS(m-n)
m=n
n=d
LOOP UNTIL d=0
PRINT m
END
§---辗转相除法和更相减损术
10