VB常用算法（五）約數因子- -

曹蘇群  http://caosuqun.bokee.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的第三行元素值取前兩行同列元素的最大公約數。最后按圖示格式顯示在圖片框中。