【新手進(jìn)階】之四：基礎(chǔ)算法（四）

roych

現(xiàn)在，來(lái)介紹一下求最大公約數(shù)的一個(gè)算法——?dú)W幾里得相除法。歐幾里得相除法定理如下：已知整數(shù)X和Y（X≥Y），X除以Y的余數(shù)為R，X和Y的最大公約數(shù)等于Y和R的最大公約數(shù)。X和0的最大公約數(shù)為X。

據(jù)此可以進(jìn)行以下迭代：X mod Y=R→Y mod R=R1→R Mod R1=R2……Rn -1 mod Rn=0。最后得到的Rn便是最大公約數(shù)了。原理講清楚了，接下來(lái)，老規(guī)矩，先貼算法：

• 先排序，使得lngN>=lngM。
• 對(duì)lngN求模，x=lngN mod lngM。
• 當(dāng)x不等于0時(shí)，重復(fù)執(zhí)行步驟4~6。
• 將lngM代入lngN中。
• 將x代入lngM中。
• 對(duì)lngN求模，x=lngN mod lngM。
• 當(dāng)x=0時(shí)，lngN即是最大公約數(shù)。
  

1. Function getEuclid(ByVal lngN As Long, ByVal lngM As Long) As Long
   
2. Dim x As Long
   
3. If lngN < lngM Then x = lngN: lngN = lngM: lngM = x
   
4. x = lngN Mod lngM
   
5. Do Until x = 0
   
6.             lngN = lngM
   
7.             lngM = x
   
8.             x = lngN Mod lngM
   
9. Loop
   
10. getEuclid = lngM
    
11. End Function

復(fù)制代碼

基礎(chǔ)算法到此結(jié)束。
【新手入門(mén)】之一：If分支語(yǔ)句
【新手入門(mén)】之二：分支語(yǔ)句總結(jié)
【新手入門(mén)】之三：循環(huán)語(yǔ)句For
【新手入門(mén)】之四：循環(huán)語(yǔ)句Do和死循環(huán)
【新手入門(mén)】之五：公共變量與傳址過(guò)程、傳值過(guò)程
【新手入門(mén)】之六：“悲歡離合總無(wú)情”——淺談Split和Join
【新手入門(mén)】之七：嵌套與并列——再談If流程問(wèn)題
【新手入門(mén)】之八：“連就連”——淺談“&”和“+”連接符的區(qū)別
【新手入門(mén)】之九：從百錢(qián)百雞談起——淺談“規(guī)劃求解”兼答lingjiang問(wèn)
【新手入門(mén)】之十：書(shū)到用時(shí)方恨少——自定義菜單（Access 2003）的制作
【新手入門(mén)】之十一：淺談ADO之序言
【新手入門(mén)】之十二：淺談ADO之Connection
【新手入門(mén)】之十三：淺談ADO之Conmmand（上）
【新手入門(mén)】之十四：淺談ADO之Command（下）
【新手入門(mén)】之十五：淺談ADO之Recordset（上）
【新手入門(mén)】之十六：淺談ADO之Recordset（下）
【新手入門(mén)】之十七：淺談列表框的使用
【新手入門(mén)】之十八：雙擊列表框修改數(shù)據(jù)
【新手入門(mén)】之十九：從“書(shū)與女友恕不外借”談起——淺談“Bookmark”的使用
【新手入門(mén)】之二十：“書(shū)與書(shū)簽”——bookmark屬性答疑
【新手入門(mén)】之二十一：記錄集的“凌遲”——逐條導(dǎo)出記錄集

【新手進(jìn)階】之一：基礎(chǔ)算法（一）
【新手進(jìn)階】之二：基礎(chǔ)算法（二）
【新手進(jìn)階】之三：基礎(chǔ)算法（三）
【新手進(jìn)階】之四：基礎(chǔ)算法（四）
【新手進(jìn)階】之五：排序搜索（一）
【新手進(jìn)階】之六：排序搜索（二）
【新手進(jìn)階】之七：遞歸算法
【新手進(jìn)階】之八：冒泡排序
【新手進(jìn)階】之九：淺談不綁定數(shù)據(jù)源操作記錄
【新手進(jìn)階】之十：工作日的計(jì)算
【新手進(jìn)階】之十一：“庖丁解�！焙汀凹o(jì)昌學(xué)射”——淺談表格式文本數(shù)據(jù)的導(dǎo)入
【新手進(jìn)階】之十二：從四腳騰空的奔馬談起——原來(lái)界面可以這樣設(shè)計(jì)
【新手進(jìn)階】之十三：Outlook風(fēng)格導(dǎo)航界面
【新手進(jìn)階】之十四：倉(cāng)庫(kù)管理系統(tǒng)

WFH6898

學(xué)習(xí)了，謝謝

today_suny

謝謝版主！！