计算机等级考试二级VB常用算法：约数因子

文章作者 100test 发表时间 2007:05:13 21:52:11
来源 100Test.Com百考试题网

计算机等级考试训练软件《百宝箱》

　　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）补充代码（2003春二（9））
给定一个十进制正整数，找出小于它并与其互质的所有正整数（所谓互质数是指最大公约数为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）编程题（2002秋上机试卷01）
　　 生成一个三行八列的二维数组A（3,8），其中前两行元素产生的方法是：
用初值X1=26及公式Xi 1=（25×Xi 357） Mod 1024，产生一个数列：X1、X2、......、X16 。
　　其中X1~X8作为A的第一行元素；X9~X16作为A的第二行元素；A的第三行元素值取前两行同列元素的最大公约数。最后按图示格式显示在图片框中。