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的两个正整数
解题技巧
该算法需要识记!
这种类型题目的扩展是约数和因子题型。
2、实战练习
1) 补充代码
给定一个十进制正整数，找出小于它并与其互质的所有正整数(所谓互质数是指最大公约数为1的两个正整数，下图是程序执行画面)。
以下是引用片段：
Option Explicit
Private Function gcd( (1) ) As Integer
Dim r As Integer
r = m Mod n
If r = 0 Then
gcd = n
Else
m = n: n = r
(2)
End If
End Function
Private Sub Command1_Click()
Dim n As Integer, p As Integer
n = Val(Text1)
For p = n - 1 To 2 Step -1
If (3) Then List1.AddItem p
Next p
End Sub |
2) 编程题
生成一个三行八列的二维数组A(3,8)，其中前两行元素产生的方法是：
用初值X1=26及公式Xi+1=(25×Xi+357) Mod 1024，产生一个数列：X1、X2、......、X16 。
其中X1~X8作为A的第一行元素;X9~X16作为A的第二行元素;A的第三行元素值取前两行同列元素的最大公约数。最后按图示格式显示在图片框中。
