PowerPoint 演示文稿

例 4.12 用辗转相除法求两自然数m，n的最大公约数和最小公倍数。
分析：求最大公约数的算法思想：
(1)对于已知两数m，n，使得m>n；
(2) m除以n得余数r；
(3)若r=0，则n为最大公约数结束；否则执行(4)；
(4)mçn，nçr，再重复执行(2)。
例 求 m=14 ,n=6 的最大公约数.
If m < n Then t = m: m = n: n = t
r=m mod n
Do While (r <> 0)
m=n
n=r
r= m mod n
Loop
Print "最大公约数=", n
m n r
14 6 2
6 2 0
辗转相减法
§ m=m-n m>n
§ n=n-m n>m
§ m、n为公约数 m=n
Do While m <> n m n
If m > n Then 14 6
m = m – n 8 6
Else 2 6
n = n – m 2 4
End If 2 2
Loop