證明:
設兩數為a、b(b<a),求它們最大公約數(a、b)的步驟如下:用b除a,得a=bq1+r1(0≤r1<b)。若r1=0,則(a,b)=b;若r1≠0,則再用r1除b,得b=r1q2+r2(0≤r2<r1)。若r2=0,則(a,b)=r1,若r2≠0,則繼續用r2除r1,……如此下去,直到能整除為止。其最後一個非零餘數即為(a,b)。
算法
輾轉相除法是利用以下性質來確定兩個正整數 a 和 b 的最大公因子的:
1. 若 r 是 a ÷ b 的餘數, 則
GCD(a,b) = gcd(b,r)
2. a 和其倍數之最大公因子為 a。
另一種寫法是:
1. a ÷ b,令r為所得餘數(0≤r<b)
若 r = 0,算法結束;b 即為答案。
2. 互換:置 a←b,b←r,並返回第一步。
3.a是個最小的自然數。
相關詞條
-
狼群算法
狼群算法是基於狼群群體智慧型,模擬狼群捕食行為及其獵物分配方式,抽象出遊走、召喚、圍攻3種智慧型行為以及“勝者為王”的頭狼產生規則和“強者生存”的狼群更新機...
基本信息 狼群系統分析 算法內容 算法描述 套用 -
套用隨機過程教程及在算法和智慧型計算中的隨機模型
圖書信息書名:套用隨機過程教程及在算法和智慧型計算中的隨機模型 ISBN...與算法兼顧。全書共分17章,內容包括機率論精要回顧與補充、隨機樣本生成法...的幾個算法、離散狀態的Markov控制與決策過程簡介、Poisson隨機分析...
-
視覺追蹤
複雜環境下目標的檢測、跟蹤與識別算法研究與套用。1991年,美國國防高級...工作組ATRWG。之後,國外知名大學與研究機構也對視頻目標的檢測與跟蹤算法進行深入研究,J.Davis等人提出了一種適用於人體檢測的背景相減算法,它...
研究意義 分類 典型算法 面臨的挑戰 -
搜尋引擎——原理、技術與系統
算法四、字元的輸入和顯示五、編碼識別第三節 中文自動分詞...第二節 網頁消重算法一、消重算法二、算法評測第三節 小結...類思想的共現辭彙算法一、基本定義二、FDC共現辭彙算法第六節...
內容簡介 目錄 -
K-means
簡介 K-means算法是很典型的基於距離的 聚類算法,採用距離作為相似性的評價指標,即認為兩個對象的距離越近,其相似度就越大。該算法認為簇...類聚類中心點的選取對聚類結果具有較大的 影響,因為在該 算法第一步中...
簡介 K-MEANS算法的工作原理及流程 K均值聚類存在的問題 k-means 算法缺點 -
最近鄰居法
的值。該算法的功能有:從目標區域抽樣計算歐式或馬氏距離;在交叉驗證後...分類之後的惰性學習。k-近鄰算法是所有的機器學習算法中最簡單的之一。無論是...)的對象。雖然沒要求明確的訓練步驟,但這也可以當作是此算法的一個訓練樣本集。最...
簡介 流程介紹 參數選擇 屬性 決策邊界 -
數學課系
變化。空間空間的研究源自於幾何-尤其是歐式幾何。三角學則結合了空間及數...代數4. 數論5.歐式幾何6.非歐式幾何7.解析幾何8.微分 ...
科系介紹 數學的本質 數學研究領域 數學的分類 符號語言嚴謹 -
時空資料庫查詢與推理
順序杏詢算法2.3 Voronoi圖及生成方法2.3.1 Voronoi...描述2.6.2 基於Voronoi圖的cNN查詢算法2.7 動態創建局部k階Voronoi圖的連續ckNN查詢算法2.8 本章小結第3章 反向最...
內容簡介 作者簡介 圖書目錄 -
路況
的改進K-近鄰算法中計算了待分類樣本與所有訓練樣本的歐式距離,事實上僅...,提出採用路況圖像的灰度直方圖作為特徵,使用LDA 算法對直方圖採樣點進行降維,並結合改進K-近鄰算法對路況進行分類.實踐證明,由於直方圖特徵...
背景簡介 路況分類處理