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

基本的なユークリッドアルゴリズムのCプログラム？

ここでは、2つの数値のGCDを見つけるためのユークリッドアルゴリズムを確認します。 GCD（最大公約数）は、ユークリッドの互除法を使用して簡単に見つけることができます。 2つの異なるアプローチがあります。 1つは反復的で、もう1つは再帰的です。ここでは、再帰的なユークリッドアルゴリズムを使用します。

アルゴリズム

EuclidanAlgorithm（a、b）

begin
   if a is 0, then
      return b
   end if
   return gcd(b mod a, a)
end

例

#include<iostream>
using namespace std;
int euclideanAlgorithm(int a, int b) {
   if (a == 0)
      return b;
   return euclideanAlgorithm(b%a, a);
}
main() {
   int a, b;
   cout << "Enter two numbers: ";
   cin >> a >> b;
   cout << "GCD " << euclideanAlgorithm(a, b);
}

出力

Enter two numbers: 12 16
GCD 4

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

    この記事では、以下に示す問題ステートメントの解決策について学習します。 問題の説明 − 2つの数値が与えられた場合、それら2つの数値のgcdを計算し、それらを表示する必要があります。 2つの数値のGCD最大公約数は、両方を除算できる最大の数値です。ここでは、ユークリッドアプローチに従って、gcdを計算します。つまり、数値を繰り返し除算し、余りがゼロになったときに停止します。ここでは、再帰で取得された以前の値に基づいてアルゴリズムを拡張します。 次に、以下の実装のソリューションを見てみましょう- 例 # extended Euclidean Algorithm def gcdExtende

  2. 基本的なユークリッドアルゴリズムのためのPythonプログラム

    この記事では、以下に示す問題ステートメントの解決策について学習します。 問題の説明 − 2つの数値が与えられた場合、それら2つの数値のgcdを計算し、それらを表示する必要があります。 2つの数値のGCD最大公約数は、両方を除算できる最大の数値です。ここでは、ユークリッドアプローチに従って、gcdを計算します。つまり、数値を繰り返し除算し、余りがゼロになったときに停止します。 次に、以下の実装のソリューションを見てみましょう- 例 # euclid algorithm for calculation of greatest common divisor def gcd(a, b): &nb