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

3/18/2007来源:软件水平考试人气:14794

  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的两个正整数,下图是程序执行画面)。

  vb

以下是引用片段:
  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的第三行元素值取前两行同列元素的最大公约数。最后按图示格式显示在图片框中。

  vb