ユークリッドの互除法:C ++とJavaの例で説明されているGCD(最大公約数)

このトピックでは、最初に最大公約数(GCD)とMOD演算について知っておく必要があります。

最大公約数(GCD)

2つ以上の整数のGCDは、余りがゼロになるように各整数を分割する最大の整数です。

例-

GCD 20、30 = 10   (10は20と30を除算する最大数で、余りは0です)

42、120、285のGCD = 3   (3は、42、120、および285を除算する最大数であり、余りは0です)

「mod」操作

mod演算は、2つの正の整数が除算されたときに余りを与えます。次のように書きます-

A mod B = R

つまり、AをBで除算すると、余りRが得られます。これは、商を与える除算演算とは異なります。

例-

7 mod 2 = 1   (7を2で割ると余りが1になります)

42 mod 7 = 0   (42を7で割ると余りが0になります)

上記の2つの概念を理解すると、ユークリッドの互除法を簡単に理解できます。

最大公約数(GCD)のユークリッドアルゴリズム

ユークリッドアルゴリズムは、2つの数のGCDを見つけます。

このアルゴリズムの動作を確認することで、このアルゴリズムをよりよく理解できます。1220と516のGCDを計算したいと仮定して、ユークリッドアルゴリズムを適用しましょう-

1220と516のGCDを計算したいと仮定して、ユークリッドアルゴリズムを適用しましょう-

ユークリッドの例

アルゴリズムの擬似コード-

ステップ1:    2つの数字にしましょう  a, b

ステップ2:  a mod b = R

ステップ3:  みよう  a = b  と  b = R

手順4:    が0になるまで、手順2と3を繰り返し  a mod bます。

ステップ5:   GCD = b

ステップ6:終了

GCDを実行するJavaScriptコード-

function gcd(a, b) { var R; while ((a % b) > 0) { R = a % b; a = b; b = R; } return b; } 

再帰を使用してGCDを実行するJavaScriptコード-

function gcd(a, b) { if (b == 0) return a; else return gcd(b, (a % b)); } 

再帰を使用してGCDを実行するCコード

int gcd(int a, int b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return gcd(a-b, b); return gcd(a, b-a); } 

GCDを実行するためのC ++コード-

int gcd(int a,int b) { int R; while ((a % b) > 0) { R = a % b; a = b; b = R; } return b; } 

再帰を使用してGCDを実行するPythonコード

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

再帰を使用してGCDを実行するJavaコード

static int gcd(int a, int b) { if(b == 0) { return a; } return gcd(b, a % b); } 

ユークリッドアルゴリズムを使用して、3つ以上の数値のGCDを見つけることもできます。GCDは結合法則であるため、次の操作が有効です-  GCD(a,b,c) == GCD(GCD(a,b), c)

最初の2つの数値のGCDを計算してから、結果と次の数値のGCDを見つけます。例-  GCD(203,91,77) == GCD(GCD(203,91),77) == GCD(7, 77) == 7

n  同じように数字のGCDを見つけることができます  。

拡張ユークリッドアルゴリズムとは何ですか?

これは、ユークリッドアルゴリズムの拡張です。また、次のように係数x、yを計算します。

ax + by = gcd(a、b)

xとyは、ベズーのアイデンティティの係数としても知られています。

拡張ユークリッドアルゴリズムのcコード

struct Triplet{ int gcd; int x; int y; }; Triplet gcdExtendedEuclid(int a,int b){ //Base Case if(b==0){ Triplet myAns; myAns.gcd = a; myAns.x = 1; myAns.y = 0; return myAns; } Triplet smallAns = gcdExtendedEuclid(b,a%b); //Extended euclid says Triplet myAns; myAns.gcd = smallAns.gcd; myAns.x = smallAns.y; myAns.y = (smallAns.x - ((a/b)*(smallAns.y))); return myAns; }