ユークリッドアルゴリズム/ユークリッド拡張アルゴリズム-python

冒頭に述べる.
ユークリッドを尊重するために、まず簡単に紹介します.
ユークリッド、古代ギリシャ人、数学者.トレミ1世時代に活躍したアレクサンダー・ダリアは、「幾何の父」と呼ばれた.
彼の最も有名な著作「幾何学の元」はヨーロッパの数学の基礎で、五大公設を提出し、ユークリッド幾何学は、歴史上最も成功した教科書と広く考えられている.
ユークリッドも透視、円錐曲線、球面幾何学、数論に関する作品を書いた.(https://baike.baidu.com/item/ユークリッド/182343?fr=aladdin)
----------------------------------------------------------------------------------------
以下はすべて自分が本を読む时自分で考えたいくつかの考え方で、総括します.
同じようなことがあれば、異議があればpy(妹紙のみ)してもいいです.
 
ユークリッドアルゴリズム、いわゆる転がり相殺法.人間の言葉は、最大公約数を求める方法です.
証明:gcd(a,b)=gcd(b,a%b)
(gcd(a,b),abの最大公約数;a%b,型演算,すなわち余数演算を求める.例えば7%2=1です.)
 
証明プロセス:
正の整数a,b(a>b)を設定します.
設定:gcd(a,b)=c(私はcを設定します)
c|a,c|b(|は、除去可能であることを示す)
A=bx+a%b(xは整数で、これは余剰演算を求めるので、emmm、このように言うのは十分に親しみやすいでしょう)
a%b=a-bx(恒等変換はおろか知らない.233333)
なぜなら、c|bはc|bx(c|b=k(kは整数)であり、kxは整数であるから、はっきり言ってください.emmmm)
則:(a%b)/c=(a-bx)/c======」(a%b)/c=a/c-bx/c
なぜなら:c|a,c|bx
従って、a/c、bx/cはいずれも整数であるため、a/c-bx/cも整数である.したがって(a%b)はc整数であってもよい.
即ち、c|(a%b)
また、c|b
従って、gcd(b,a%b)=c則:gcd(a,b)=gcd(b,a%b)が得られる.△この証明の過程は、ネット全体がこれ以上はっきり書いているとは信じられない.
 
これを証明すると,abの最大公約数を反復,反復除去(転がり除去)により求めることができる.
Emmm、どうしていいんですか.gcd(a,b)=gcd(b,a%b)は繰り返しの過程であるからである.
例えば、gcd(a,b)=gcd(b,a%b)=gcd(a%b,b%(a%b)=gcd(r 1,r 2)=・・=gcd(rn-1,rn)(rn=rn-2%rn-1)と書き続けることができます.
これでもっとはっきりできるのではないでしょうか.の
 
コード実装
1、再帰操作:転々相殺
2、再帰終了操作:残りは0
"""
これは単純なバージョンにすぎません.
例えば、最大公約数がない場合は判断していません.
"""
 

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

------------------------------   -------------------------------------
    。    。   。
               。    。
-----------------------------   ---------------------------------------
  ，     。。
         ：
       ax+by=z   。
            。

  ，   a，b。（a，b>0）,  ab       （             ）
       c， gcd（a，b）= c
    ax+by = c，     x，y     ax+by=z   。
       。              。（     ）
    ax+by=c，       k， a（xk）+b（yk）= ck
   ck=z，  a（xk）+b（yk）= z。     x，y    。
        k     ax+by=z  x y 。
（        ，     。  ）

  ，        。  ax+by=gcd（a，b）  ，x，y    。
（         ~~）

----------------    ，    -----------------------

転載先:https://www.cnblogs.com/sbxlqswl/p/9839714.html