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

Pythonで2つの数値のgcdを再帰的に計算するプログラム

aとbの2つの数があるとします。これら2つの数値のGCDを再帰的に見つける必要があります。 GCDを取得するには、ユークリッドアルゴリズムを使用します。

したがって、入力がa =25 b =45のような場合、出力は5になります

これを解決するには、次の手順に従います-

  • 関数gcd（）を定義します。これにはa、bが必要です
  • aがbと同じ場合、
    • 返品
  • それ以外の場合、a
  • return gcd（b、a）
  • それ以外の場合、
    • return gcd（b、a --b）

    • 例

    理解を深めるために、次の実装を見てみましょう-

    def gcd(a, b):
   if a == b:
      return a
   elif a < b:
      return gcd(b, a)
   else:
      return gcd(b, a - b)

a = 25
b = 45
print(gcd(a, b))

    入力

    25, 45

    出力

    5

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

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

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

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