def gcd(a, b):
    if a< b:
        a, b = b, a
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)

創新互聯不只是一家網站建設的網絡公司；我們對營銷、技術、服務都有自己獨特見解，公司采取“創意+綜合+營銷”一體化的方式為您提供更專業的服務！我們經歷的每一步也許不一定是最完美的，但每一步都有值得深思的意義。我們珍視每一份信任，關注我們的成都網站建設、成都網站制作質量和服務品質，在得到用戶滿意的同時，也能得到同行業的專業認可，能夠為行業創新發展助力。未來將繼續專注于技術創新，服務升級，滿足企業一站式成都全網營銷推廣需求，讓再小的高端網站設計也能產生價值！

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

'''擴展歐幾里得算法是歐幾里得算法（又叫輾轉相除法）的擴展。
除了計算a、b兩個整數的大公約數，此算法還能找到整數x、y（其中一個很可能是負數）。
通常談到大公因子時, 我們都會提到一個非常基本的事實: 
給予二整數 a 與 b, 必存在有整數 x 與 y 使得
ax + by = gcd(a,b)。
有兩個數a,b，對它們進行輾轉相除法，可得它們的大公約數——這是眾所周知的。
然后，收集輾轉相除法中產生的式子，倒回去，可以得到ax+by=gcd(a,b)的整數解。'''


def Ext_Euclid(a, b):
    if b == 0:
        return 1, 0, a
    else:
        x, y, d = Ext_Euclid(b, a % b)
        x, y = y, (x-(a//b)*y)
        return x, y, d


t = Ext_Euclid(56, 15)
print(t)

你是否還在尋找穩定的海外服務器提供商？創新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統配攻擊溯源，準確流量調度確保服務器高可用性，企業級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

標題名稱：python最大公約數遞歸方法與非遞歸辦法及擴展-創新互聯
URL地址：http://www.js-pz168.com/article28/djhojp.html

成都網站建設公司_創新互聯，為您提供網站策劃、品牌網站建設、企業建站、全網營銷推廣、網站收錄、關鍵詞優化

廣告

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