零基础学算法->最大公约数(GCD)和最小公倍数(LCM)

桃扇骨 2022-01-14 12:39 189阅读 0赞

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][]

#### 欧几里德算法 ####

'Use Euclid Method
    'Calculate GCD and LCM
    'https://zh.wikipedia.org/wiki/%E6%9C%80%E5%B0%8F%E5%85%AC%E5%80%8D%E6%95%B8
    
    Sub Euclid_Method()
    Dim a&, b&
    Dim nGCD&, nLCM
    
    With Sheet4
    a = .Cells(4, 3).Value
    b = .Cells(5, 3).Value
    nGCD = Euclid_GCD_Iter(a, b)
    nLCM = Euclid_LCM_Iter(a, b)
    .Cells(6, 3) = nGCD
    .Cells(7, 3) = nLCM
    
    End With
    Debug.Print Timer
    End Sub
    
    'Iterate
    'x>y
    Function Euclid_GCD_Iter(a, b)
    Dim r&
    If a > b Then x = a: y = b Else x = b: y = a  'Make x>y
    r = x Mod y              'remainder
        Do While r           'Loop till r>0
            x = y
            y = r
            r = x Mod y
            Debug.Print x, y
        Loop
       Euclid_GCD_Iter = y    'Return GCD
    End Function
    
    Function Euclid_LCM_Iter(x, y)
    Dim t
    t = Euclid_GCD_Iter(x, y)       'Get the GCD
    Euclid_LCM_Iter = (x * y) / t   'LCM=(a*b)/GCD
    End Function

#### Stein算法 ####

'Use Stein Method
    'Calculate GCD and LCM
    '******************************************
    'https://baike.baidu.com/item/%E6%9C%80%E5%A4%A7%E5%85%AC%E7%BA%A6%E6%95%B0/869308?fr=aladdin
    'Stein Algorithm:
    '
    'Set A1=A;B1=B;C1=1
    '1 if An=0,Bn*Cn is GCD, Exit Program
    '2 if Bn=0, An*Cn is GCD, Exit Program
    '3 if An and Bn is Even; An+1=An/2,Bn+1=Bn/2,Cn+1=Cn/2
    '4 If An is Even, Bn is not Even; An+1=An/2,Bn+1=Bn,Cn+1=Cn
    '5 If Bn is Even, An is not Even; An+1=An,Bn+1=Bn/2,Cn+1=Cn
    '6 if Either An or Bn is Even; An+1=|An-Bn|,Bn+1=Min(An,Bn),Cn+1=Cn
    '7 n+1, go to Step 1
    '******************************************
    Sub Stein_Method()
    Dim a&, b&
    Dim nGCD&, nLCM
    
    With Sheet5
    a = .Cells(4, 3).Value
    b = .Cells(5, 3).Value
    nGCD = Stein_GCD_Recur(a, b)
    nLCM = Stein_LCM(a, b)
    .Cells(6, 3) = nGCD
    .Cells(7, 3) = nLCM
    
    End With
    Debug.Print Timer
    End Sub
    
    'Iterate
    'x>y
    Function Stein_GCD_Recur(a, b)
    Dim c&
    If a > b Then x = a: y = b Else x = b: y = a  'Make x>y
    If y = 0 Then Stein_GCD_Recur = x: Exit Function
    If x Mod 2 = 0 And y Mod 2 = 0 Then
        Stein_GCD_Recur = 2 * Stein_GCD_Recur(x / 2, y / 2)    'An and Bn is Even
    ElseIf x Mod 2 = 0 Then
        Stein_GCD_Recur = Stein_GCD_Recur(x / 2, y)            'An is Even
    ElseIf y Mod 2 = 0 Then
        Stein_GCD_Recur = Stein_GCD_Recur(x, y / 2)            'Bn is Even
    Else
        Stein_GCD_Recur = Stein_GCD_Recur((x + y) / 2, (x - y) / 2)   'An or Bn is NOT Even
    End If
    End Function
    
    Function Stein_LCM(x, y)
    Dim t
    t = Stein_GCD_Recur(x, y)     'Get the GCD
    Stein_LCM = (x * y) / t       'LCM=(a*b)/GCD
    End Function

转载于:https://my.oschina.net/tedzheng/blog/3001276

[2019_Python_]: https://my.oschina.net/u/2663968/blog/3061697
[hot3.png]: /images/20220114/8d425d6f22984031b51ca076e3defdb2.png