首页 > 考试 > 等级考试 > 二级 > Visual Basic >

计算机等级考试二级VB算法(5):约数因子

2009-02-28

1、算法说明 1)        最大公约数:          用辗转相除法求两自然数m、n的最大公约数。 (1)     &nb

1、算法说明

1) 最大公约数:
用辗转相除法求两自然数m、n的最大公约数。
(1) 首先,对于已知两数m、n,比较并使得m>n;
(2) m除以n得余数r;
(3) 若r=0,则n为求得的最大公约数,算法结束;否则执行步骤(4)
(4) mßn nßr 再重复执行(2)
譬如: 10与5
分析步骤: m=10 n=5
r=m mod n=0
所以n(n=5)为最大公约数
24与9
分析步骤: m=24 n=9
r=m mod n=6
r≠0 m=9 n=6
r=m mod n=3
r≠0 m=6 n=3
r=m mod n=0
所以n(n=3)为最大公约数


算法实现
循环实现
Private Function GCD(ByVal m As Long, ByVal n As Long) As Long
Dim temp As Long
If m < n Then temp = m: m = n: n = temp
Dim r As Long
Do
r = m Mod n
If r = 0 Then Exit Do
m = n
n = r
Loop
GCD = n
End Function


递归实现
Private Function GCD(ByVal m As Long, ByVal n As Long) As Long
Dim temp As Long
If m < n Then temp = m: m = n: n = temp
Dim r As Long
r = m Mod n
If r = 0 Then
GCD = n
Else
m = n
n = r
GCD = GCD(m, n)
End If
End Function


2) 最小公倍数
m×n÷最大公约数


3) 互质数
最大公约数为1的两个正整数


解题技巧
该算法需要识记!
这种类型题目的扩展是约数和因子题型。

1、算法说明

1) 最大公约数:
用辗转相除法求两自然数m、n的最大公约数。
(1) 首先,对于已知两数m、n,比较并使得m>n;
(2) m除以n得余数r;
(3) 若r=0,则n为求得的最大公约数,算法结束;否则执行步骤(4)
(4) m&szlig;n n&szlig;r 再重复执行(2)
譬如: 10与5
分析步骤: m=10 n=5
r=m mod n=0
所以n(n=5)为最大公约数
24与9
分析步骤: m=24 n=9
r=m mod n=6
r≠0 m=9 n=6
r=m mod n=3
r≠0 m=6 n=3
r=m mod n=0
所以n(n=3)为最大公约数


算法实现
循环实现
Private Function GCD(ByVal m As Long, ByVal n As Long) As Long
Dim temp As Long
If m < n Then temp = m: m = n: n = temp
Dim r As Long
Do
r = m Mod n
If r = 0 Then Exit Do
m = n
n = r
Loop
GCD = n
End Function


递归实现
Private Function GCD(ByVal m As Long, ByVal n As Long) As Long
Dim temp As Long
If m < n Then temp = m: m = n: n = temp
Dim r As Long
r = m Mod n
If r = 0 Then
GCD = n
Else
m = n
n = r
GCD = GCD(m, n)
End If
End Function


2) 最小公倍数
m×n÷最大公约数


3) 互质数
最大公约数为1的两个正整数


解题技巧
该算法需要识记!
这种类型题目的扩展是约数和因子题型。

相关文章
最新文章
热点推荐