題目：

創新互聯是一家專注于成都網站制作、做網站與策劃設計,曲水網站建設哪家好?創新互聯做網站,專注于網站建設10多年,網設計領域的專業建站公司;建站業務涵蓋:曲水等地區。曲水做網站價格咨詢:13518219792

給定兩個自然數，求這兩個數的大公約數。

分析：

單看題目的話，非常簡單，我們可以循環遍歷自然數，如果能夠整除兩個自然數，就把這個數記下來，在這些記錄中找到大的一個。
但是這樣做有幾個缺點：一是做除法計算量比較大，二是遍歷所有自然數完全沒有必要。另外，如果能夠循環，還是不要遞歸，因為Python的函數遞歸大棧空間是1000（如果我沒有記錯的話），如果數字大一些，很容易出現爆棧。

所以在這里有兩種處理方法：

1、如果較大的自然數除較小的一個自然數，取得余數，較小的自然數和余數的大公約數就是我們要求的值。
2、如果較大的自然數減去較小的自然數，取得差值，較小的自然數和差值的大公約數就是我們要求的值。

基于以上兩條，我們就可以在根據定義得到的算法的基礎上進行改進，但是！減法操作當然比取余要方便很多。而且在計算機里，做位運算的速度要比加減乘除都快，所以，我寫了四個算法，具體描述在代碼的 __doc__里有注釋闡述

代碼：

def greatest_common_divisor_1(self, num1, num2):
    '''
    數值計算尋找大公約數，給定兩個整數，計算其大公約數，時間復雜度為 o(min(num1,num2))，取余運算復雜度高
    '''
    gbc = 1
    for i in xrange(2, min(num1, num2)+1):
      if num2 % i == 0 and num1 % i == 0:
        gbc = i
    return gbc

  def greatest_common_divisor_2(self, num1, num2):
    '''
    輾轉相減法，時間復雜度最差為 o(min(num1,num2))，一般情況下都比這個要好。相減運算要比除法方便很多
    '''
    while num1 != num2:
      if num1 > num2:
        num1 = num1 - num2
      else:
        num2 = num2 - num1
    return num1

  def greatest_common_divisor_3(self, num1, num2):
    '''
    求余數法，取模運算比較麻煩，時間復雜度低 o(log max(num1, num2))
    '''
    while num1 != num2:
      if num1 > num2:
        if num1 % num2 == 0:
          return num2
        num1 = num1 % num2
      else:
        if num2 % num1 == 0:
          return num1
        num2 = num2 % num1
    return num1

  def greatest_common_divisor(self, num1, num2):
    '''
    求兩個數的大公約數
    綜合取余法和輾轉相減法，既能得到較好的時間復雜度，又能避免取余運算，時間復雜度穩定 o(log max(num1,num2))
    如果取兩個非常大的數的話，前面的方法很容易爆棧、取余困難等等，但是該方法沒有問題
    a = 999999342353200
    b = 777774234
    print greatest_common_divisor(a, b)
    '''
    factor = 1
    if num1 < num2:
      return greatest_common_divisor_1(num2, num1)
    while num1 != num2:
      if num1 & 1 is False and num2 & 1 is False: # 均為偶數
        num1 = num1 >> 1
        num2 = num2 >> 2
        factor *= 2
      elif num1 & 1 is False and num2 & 1 is True:
        num1 = num1 >> 1
      elif num1 & 1 is True and num2 & 1 is False:
        num2 = num2 >> 1
      else:
        if num1 > num2:
          num1 = num1 - num2
        else:
          num2 = num2 - num1
    return factor*num1

名稱欄目：python如何求解兩數的最大公約數-創新互聯
文章分享：http://m.newbst.com/article14/jgdde.html

成都網站建設公司_創新互聯，為您提供動態網站、網站營銷、網站策劃、標簽優化、網站制作、微信小程序

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯