Pythonでのユークリッドアルゴリズム（減算）

Question

「大規模な数学的問題 - 無限のビジョン」、18ページイアンスチュワートはユークリッドの命題2、要素VIIIを参照しました。これは非常に基本的な除数を見つける基本的な方法です。私は引用しています。これは、大きい方の数字から小さい方の数字を繰り返し減算した後、同様の処理を残りの数字と小さい数字に適用し、残りがなくなるまで続きます」例は630と135です。135は630（495,360,225）から再差し引かれ、最終的に135より小さい90が得られます。したがって、数値は逆になり、最終的には90から減算され、最終的に45次に90から45を減算し、最後に0を得てgcdを45にする。これは、gcdを見つけるユークリッドアルゴリズムと呼ばれることもあります。

初心者（10歳の子供）を教えるには、コードをPythonで記述する必要があります。関数定義は存在してはいけません。また、減算以外の数学演算も使用する必要はありません。 if/while/else/elif/continue/breakを使いたいです。 3つの数字（またはそれ以上）が与えられれば、全体のプログラムはより小さなものを決めることを繰り返さなければならないという規定があるはずです。 gcdの以前のチェーンでは、この観点からアルゴリズムが見えません。 pythonであなただけの直接の分画モジュールが提供するGCD関数を使用すると思い、実際には

def gcd(x, y): 
    while y != 0: 
     (x, y) = (y, x % y) 

    return x 

：GCDアルゴリズムに

Answer 1

典型的な高速なソリューションは、このようないくつかの反復バージョンになります。あなたはあなただけ減らす使用したい複数の値に対処するために、このような機能を望んでいた場合

はまた：

reduce(gcd,your_array) 

を今、あなたが対処するので、一つの可能​​な解決策だけループ+ substractionsを使用するために自分自身を制限したいようですxは、yの正の整数は、このようになります：

def gcd_unopt(x, y): 
    print x,y 

    while x!=y: 
     while x>y: 
      x -= y 
      print x,y 
     while y>x: 
      y -= x 
      print x,y 

    return x 

print reduce(gcd_unopt,[630,135]) 

わからないあなたが機能を使用しないようにしたかった理由は、GCDは、定義によって機能が、そうであっても、それは単に関数の宣言を取り除くと使用します、簡単ですですグローバル変数としてのパラメータ。例：

x = 630 
y = 135 

print x,y 

while x!=y: 
    while x>y: 
     x -= y 
     print x,y 
    while y>x: 
     y -= x 
     print x,y