Python
 Computer >> コンピューター >  >> プログラミング >> Python

拡張ユークリッドアルゴリズムのためのPythonプログラム

この記事では、以下に示す問題ステートメントの解決策について学習します。

問題の説明 − 2つの数値が与えられた場合、それら2つの数値のgcdを計算し、それらを表示する必要があります。

2つの数値のGCD最大公約数は、両方を除算できる最大の数値です。ここでは、ユークリッドアプローチに従って、gcdを計算します。つまり、数値を繰り返し除算し、余りがゼロになったときに停止します。ここでは、再帰で取得された以前の値に基づいてアルゴリズムを拡張します。

次に、以下の実装のソリューションを見てみましょう-

例

# extended Euclidean Algorithm
def gcdExtended(a, b, x, y):
   # Base Case
   if a == 0 :
      x = 0
      y = 1
      return b
   x1 = 1
   y1 = 1 # storing the result
   gcd = gcdExtended(b%a, a, x1, y1)
   # Update x and y with previous calculated values
   x = y1 - (b/a) * x1
   y = x1
   return gcd
x = 1
y = 1
a = 11
b = 15
g = gcdExtended(a, b, x, y)
print("gcd of ", a , "&" , b, " is = ", g)

出力

gcd of 11 & 15 is = 1

拡張ユークリッドアルゴリズムのためのPythonプログラム

すべての変数はローカルスコープで宣言されており、それらの参照は上の図に示されています。

結論

この記事では、拡張ユークリッドアルゴリズム用のPythonプログラムを作成する方法について学びました


  1. 選択ソート用のPythonプログラム

    この記事では、Python3.xでの選択ソートとその実装について学習します。またはそれ以前。 選択ソート アルゴリズムでは、配列は、ソートされていない部分から最小要素を再帰的に見つけて、それを先頭に挿入することによってソートされます。特定の配列での選択ソートの実行中に、2つのサブ配列が形成されます。 すでにソートされているサブアレイ ソートされていないサブアレイ。 選択ソートを繰り返すたびに、ソートされていないサブアレイの最小要素がポップされ、ソートされたサブアレイに挿入されます。 アルゴリズムの視覚的表現を見てみましょう- それでは、アルゴリズムの実装を見てみましょう- 例

  2. 2つ以上（または配列）の数値のGCD用のPythonプログラム

    この記事では、以下に示す問題ステートメントの解決策について学習します- 問題の説明 −数の配列が与えられ、最大公約数を見つける必要があります。 3つ以上の数のgcdを見つける必要がある場合、gcdは、引数として提供されるすべての数に共通の素因数の積に等しくなります。引数の数のペアのGCDを繰り返し取得することによって計算することもできます。 ここでは、後者のアプローチを実装します では、実装を見てみましょう 例 def findgcd(x, y):    while(y):       x, y = y, x % y   &n