Posted on 2007-04-02 22:55
大大毛 閱讀(408)
評論(0) 編輯 收藏 所屬分類:
常用算法
??????最近用到最小公倍數、最大公約數是因為需要對用戶 Key In 的數據（分數形式）進行檢驗，檢驗的規則是同組的數據之和 =? 1，這樣就需要求分母的最小公倍數。
??????在網上搜索了一下，主要介紹的算法有兩種：
??????1. 歐幾里德算法
?????????又叫輾轉相除法，是最常用的算法，以前學到的就是這個了。它僅在對大素數的模運算時會遇到麻煩。
'
Euclid算法（VB）
Public
?
Function
?fEuclid(lngNum1?
As
?
Long
,?lngNum2?
As
?
Long
)?
As
?
Long
????
Dim
?lngA?
As
?
Long
,lngB?
As
?
Long
,lngC?
As
?
Long
????
If
?lngNum1?
=
?
0
?
Or
?lngNum2?
=
?
0
?
Then
????????
If
?lngNum1?
=
?
0
?
Then
????????????fEuclid?
=
?lngNum2
????????
Else
????????????fEuclid?
=
?lngNum1
????????
End
?
If
????????
Exit
?
Function
????
End
?
If
????
If
?lngNum1?
>=
?lngNum2?
Then
????????lngA?
=
?lngNum1:lngB?
=
?lngNum2
????
Else
????????lngA?
=
?lngNum2:lngB?
=
?lngNum1
????
End
?
If
????lngC?
=
?lngA?
Mod
?lngB
????
Do
?
While
?lngC?
>
?
0
????????lngA?
=
?lngB:lngB?
=
?lngC
????????lngC?
=
?lngA?
Mod
?lngB
????
Loop
????
????fEuclid?
=
?lngB
End?Function
??????2. Stein算法
?????????a.??? 如果A=0，B是最大公約數；如果B=0，A是最大公約數
?????????b.?? An = A，Bn = B，Cn = 1 （當n=1時）
?????????c1. 如果An和Bn都是偶數，則An+1 = An /2，Bn+1 = Bn /2，Cn+1 = Cn *2
?????????c2. 如果An是偶數，Bn不是偶數，則An+1 = An /2，Bn+1 = Bn ，Cn+1 = Cn
?????????c3. 如果Bn是偶數，An不是偶數，則Bn+1 = Bn /2，An+1 = An ，Cn+1 = Cn
?????????c4.?如果An和Bn都不是偶數，則An+1 = |An - Bn|，Bn+1 =min(An,Bn)，Cn+1 = Cn
?????????d.??? n++
?????????Stein算法最大的好處就是它只使用到了減法以及移位操作（與2運算），能夠避免歐幾里德算法運用到大數上所面臨的問題。
'
Stein算法（VB）
Public
?
Function
?fStein(lngNum1?
As
?
Long
,?lngNum2?
As
?
Long
)?
As
?
Long
????
Dim
?lngResult?
As
?
Long
,?lngA?
As
?
Long
,?lngB?
As
?
Long
,?lngC?
As
?
Long
????lngA?
=
?lngNum1:?lngB?
=
?lngNum2:?lngC?
=
?
1
????
????
Do
?
While
?lngA?
<>
?
0
?
And
?lngB?
<>
?
0
????????
If
?lngA?
Mod
?
2
?
=
?
0
?
And
?lngB?
Mod
?
2
?
=
?
0
?
Then
????????????lngA?
=
?lngA?
/
?
2
:?lngB?
=
?lngB?
/
?
2
:?lngC?
=
?lngC?
*
?
2
????????
Else
????????????
If
?lngA?
Mod
?
2
?
<>
?
0
?
And
?lngB?
Mod
?
2
?
<>
?
0
?
Then
????????????????
If
?lngA?
>
?lngB?
Then
????????????????????
'
lngB?=?lngB
????????????????????lngA?
=
?lngA?
-
?lngB
????????????????
Else
????????????????????lngB?
=
?lngA
????????????????????lngA?
=
?lngB?
-
?lngA
????????????????
End
?
If
????????????
Else
????????????????
If
?lngA?
Mod
?
2
?
=
?
0
?
Then
????????????????????lngA?
=
?lngA?
/
?
2
????????????????
Else
????????????????????lngB?
=
?lngB?
/
?
2
????????????????
End
?
If
????????????
End
?
If
????????
End
?
If
????
Loop
????
If
?lngA?
=
?
0
?
Then
????????lngResult?
=
?lngC?
*
?lngB
????
Else
????????lngResult?
=
?lngC?
*
?lngA
????
End
?
If
????
????fStein?
=
?lngResult
End?Function
??????最小公倍數 = M * N / 最大公約數