（Python）三種演算法求解最大公約數和最小公倍數- IT閱讀

採用迴圈遞減的方法從最小數開始遞減至1; 判斷當兩數的取餘都等於0時跳出迴圈; 當前數即為最大的公約數. 詳細程式碼： （Python）三種演算法求解最大公約數和最小公倍數 首頁 最新 HTML CSS JavaScript jQuery Python3 Python2 Java C C++ Go SQL 首頁 最新 Search （Python）三種演算法求解最大公約數和最小公倍數 2019-02-03254 1.窮舉法 窮舉法的基本思想是：根據題目的部分條件確定答案的大致範圍，並在此範圍內對所有可能的情況逐一驗證，直到全部情況驗證完畢。

若某個情況驗證符合題目的全部條件，則為本問題的一個解；若全部情況驗證後都不符合題目的全部條件，則本題無解。

窮舉法也稱為列舉法。

窮舉法時最通用的，也是最傻瓜式的一種演算法，通過迴圈遞增或者迴圈遞減的方法來遍歷所有合理範圍內的數，通過判斷是否滿足條件來結束程式，從而得到最大公約數 解題步驟： 通過鍵盤輸入兩個需要求解的數 比較兩數的大小，找出較小的數 採用迴圈遞減的方法從最小數開始遞減至1 判斷當兩數的取餘都等於0時跳出迴圈 當前數即為最大的公約數 詳細程式碼： ##窮舉法求兩數最大公約數 defgetGreatdivisor(a,b): ifa>b:#預設b較大得數，否則兩數交換位置 a,b=b,a foreachinrange(a+1,0,-1): if(a%each==0)&(b%each==0): result=each break; print("最大公約數為：",result) a=int(input("first:")) b=int(input("second:")) getGreatdivisor(a,b) 2.更相減損法 更相減損術是出自《九章算術》的一種求最大公約數的演算法，它原本是為約分而設計的，但它適用於任何需要求最大公約數的場合。

原文是： 1 可半者半之，不可半者，副置分母、子之數，以少減多，更相減損，求其等也。

以等數約之。

如果需要對分數進行約分，那麼）可以折半的話，就折半（也就是用2來約分）。

如果不可以折半的話，那麼就比較分母和分子的大小，用大數減去小數，互相減來減去，一直到減數與差相等為止，用這個相等的數字來約分。

解題步驟： 通過鍵盤輸入兩個需要求解的數a，b 比較兩數的大小，找出較小的數，預設a為較小的數 較大數b減去較小數a，如果相減結果等於較小數a，演算法終止，當前a或b即為最大的公約數 若減結果不等於較小數a，則轉到第二步 詳細程式碼： ##相減法求兩數最大公約數 defgetGreatdivisor(a,b): ifa>b:#預設b較大得數，否則兩數交換位置 a,b=b,a ifb-a==a: print("最大公約數為",a) else: getGreatdivisor(b-a,a) a=int(input("first:")) b=int(input("second:")) getGreatdivisor(a,b) 3.輾轉相除法 輾轉相除法，又名歐幾里德演算法（Euclideanalgorithm），是求最大公約數的一種方法。

它的具體做法是：用較小數除較大數，再用出現的餘數（第一餘數）去除除數，再用出現的餘數（第二餘數）去除第一餘數，如此反覆，直到最後餘數是0為止。

如果是求兩個數的最大公約數，那麼最後的除數就是這兩個數的最大公約數。

解題步驟： 通過鍵盤輸入兩個需要求解的數a，b 比較兩數的大小，找出較小的數，預設a為較小的數 較大數b取餘較小數a，如果取餘結果等於較小數a，演算法終止，當前a或b即為最大的公約數 若取餘結果不等於較小數a，則轉到第二步 詳細程式碼; ##輾轉相除法求兩數最大公約數 defgetGreatdivisor(a,b): ifa>b:#預設b較大得數，否則兩數交換位置 a,b=b,a ifb%a==0: print("最大公約數為",a) else: getGreatdivisor(b%a,b) a=int(input("first:")) b=int(input("second:")) getGreatdivisor(a,b) 4.用窮舉法實現求任意個數的最大公約數和最小公倍數 基本思想：通過鍵盤輸入需要求解的數值個數，將數值存放在一個列表中，對列表中的數值進行排序（會用到sort()函式），若要求最大公約數則從列表中去出第一個元素作為開始，若要求最小公倍數則從列表中去除最後一個元素作為開始。

最後採用窮舉法的思想求得解。

注：這其中的判斷結束條件和之前有所不同，需要設定一個標記來記錄是否列表中的所有元素都滿足取餘條件，沒窮舉一個數都需要遍歷列表判斷是否取餘結果等於零，滿足條件標記自增，否則跳出遍歷迴圈繼續試下一個數。

當標記等於列表元素個數時結束程式，當前數即為最大公約數或者最小公倍數 詳細程式碼： ##求n個數得最大公約數和最小公倍數 importsys defgetLCM(list,n): list.sort() max=list[n-1] foreachinrange(max,10000,): result=each count=0 fornumberinrange(len(list)): ifeach%list[number]==0: count+=1; else: break ifcount==len(list): break print("最小公倍數為：",result) defgetGCD(list,n): list.sort() min=list[0] foreachinrange(min,0,-1): result=each count=0 fornumberinrange(len(list)): iflist[number]%each==0: count+=1; else: break ifcount==len(list): break print("最大公約數為：",result) list=[] n=int(input("輸入個數:")) foriinrange(n): list.append(int(input("輸入第%d個數"%(i+1)))) getLCM(list,n) getGCD(list,n) 相關文章 （Python）三種演算法求解最大公約數和最小公倍數 Prim演算法求解最小生成樹的Java實現 三種演算法求一個數字序列的最長遞增子序列 Python動態規劃演算法求解最長公共子序列 三種演算法求兩個正整數的最大公約數和最小公倍數；求三個數的最大公約數和最小公倍數 劍指offer(面試題14):動態規劃和貪心演算法求解最優化問題 Leetcode[53]分治演算法求解最長子串和問題 [演算法]歐幾里得演算法——求解最大公因數 Manacher演算法：求解最長迴文字串，時間複雜度為O(N) 用c++程式碼實現貪心演算法求解最短路徑問題 floyd演算法求解最短路徑 資料結構-基於鄰接表實現圖的遍歷視覺化及使用Floyd、Dijkstra演算法求解最短路徑（JavaScript實現） 資料結構-基於鄰接矩陣實現圖的遍歷視覺化及使用Floyd、Dijkstra演算法求解最短路徑（JavaScript實現） 演算法學習之二——用DP和備忘錄演算法求解最長公共子序列問題 2502SUBWAY（FLOYD演算法求解最短路） 分類導航 HTML/CSS HTML教程 HTML5教程 CSS教程 CSS3教程 JavaScript JavaScript教程 jQuery教程 Node.js教程 服務端 Python教程 Python3教程 Linux教程 Docker教程 Ruby教程 Java教程 JSP教程 C教程 C++教程 Perl教程 Go教程 PHP教程 正則表達式 資料庫 SQL教程 MySQL教程 PostgreSQL教程 SQLite教程 MongoDB教程 Redis教程 Memcached教程 行動端 IOS教程 Swift教程 Advertisement 三度辭典 Copyright©2016-2021IT閱讀  Itread01.comAllRightsReserved. 0.001291036605835