python如何求解兩數(shù)的最大公約數(shù)

更新時(shí)間：2018年09月27日 09:46:11 作者：冬日新雨

這篇文章主要為大家詳細(xì)介紹了python如何求解兩數(shù)的最大公約數(shù)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

題目：

給定兩個(gè)自然數(shù)，求這兩個(gè)數(shù)的最大公約數(shù)。

分析：

單看題目的話，非常簡單，我們可以循環(huán)遍歷自然數(shù)，如果能夠整除兩個(gè)自然數(shù)，就把這個(gè)數(shù)記下來，在這些記錄中找到最大的一個(gè)。
但是這樣做有幾個(gè)缺點(diǎn)：一是做除法計(jì)算量比較大，二是遍歷所有自然數(shù)完全沒有必要。另外，如果能夠循環(huán)，還是不要遞歸，因?yàn)镻ython的函數(shù)遞歸最大?？臻g是1000（如果我沒有記錯(cuò)的話），如果數(shù)字大一些，很容易出現(xiàn)爆棧。

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

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

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

代碼：

def greatest_common_divisor_1(self, num1, num2):
    '''
    數(shù)值計(jì)算尋找最大公約數(shù)，給定兩個(gè)整數(shù)，計(jì)算其最大公約數(shù)，時(shí)間復(fù)雜度為 o(min(num1,num2))，取余運(yùn)算復(fù)雜度高
    '''
    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):
    '''
    輾轉(zhuǎn)相減法，時(shí)間復(fù)雜度最差為 o(min(num1,num2))，一般情況下都比這個(gè)要好。相減運(yùn)算要比除法方便很多
    '''
    while num1 != num2:
      if num1 > num2:
        num1 = num1 - num2
      else:
        num2 = num2 - num1
    return num1

  def greatest_common_divisor_3(self, num1, num2):
    '''
    求余數(shù)法，取模運(yùn)算比較麻煩，時(shí)間復(fù)雜度低 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):
    '''
    求兩個(gè)數(shù)的最大公約數(shù)
    綜合取余法和輾轉(zhuǎn)相減法，既能得到較好的時(shí)間復(fù)雜度，又能避免取余運(yùn)算，時(shí)間復(fù)雜度穩(wěn)定 o(log max(num1,num2))
    如果取兩個(gè)非常大的數(shù)的話，前面的方法很容易爆棧、取余困難等等，但是該方法沒有問題
    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: # 均為偶數(shù)
        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

以上就是本文的全部內(nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: