与えられた2つの正の整数は、最大公約数を見つけるために、私は、これはすべてのコードを書く学生は絶対に演習を満たしていると信じて、もちろん、解決策も非常に多く、次の最初の任意のアルゴリズム処理なしでプログラムを提供します：
public static int getResult(int a,int b){
int max = (a>b)?a:b;
int result=0;
for(int i = 1;i < max;i++){
if(a%i == 0 && b%i == 0){
result=i;
}
}
return result;
}
これは確かに解決することは可能ですが、正の整数の大きい方をループするには、2つの量が非常に大きい場合、効率は非常に低く、あなたが非効率的な手順に遭遇するたびに、必然的に最適化を考えるでしょう、アルゴリズムの最適化は、常に非常に信頼性の高い方法です。ここでは、最大公約数の問題を解決するためにアルゴリズムを追加するいくつかの方法のリストです。
解決策 I：
Turbulence division method, assuming that the positive integers num1,num2 of the greatest common divisor, assuming that f(x,y) for the greatest common divisor of the two, take k = x / y, b = x % y; then x = k y + b; then the number can be x, y divisible by the same time must also be able to be b, y at the same time, can be b, y can be divided by the same time the number can also be divided by the same time x, y, that is to say, the greatest common factor of x, y is the greatest common factor b, y, then there are f = f(y , x% y), so recursive operation, for example, such as the num1,num2 of the greatest common denominator, assuming that f(x,y) is the greatest common factor of the two.yとすると、f = f(y , x%y) のような再帰的な演算となります。
f(42,30) = f(30,12) = f(12 , 6) = f(6,0) = 6; これで操作の回数は大幅に減りました。以下にコードを添付します：
int result = ((y == 0) ? x : gcd(y, x % y));
return result;
}
解決策 II：
解決策1は、大会の数を見つけるという問題に対する良い解決策ですが、アルゴリズムには除算が含まれており、コンピュータでの除算のオーバーヘッドが大きいので、我々は除算を使用することはできません。このように考えることができ、数はx、y整数であることができ、また、x - y、y整数でなければなりません、つまり、数はx、y整数であることは、この数はx - y、y整数であることは十分に必要な条件です。f(x, y) = f(x-y , y); このように計算すると、大きな整数間のモジュロ演算を大きな整数間の減算演算に変換します。f= fなので、正の数と負の数の最大公約数を求めないようにするには、柔軟にf= f,を片方が0になるまで繰り返し使います：
f(42,30) = f(30,12) = f(18 , 12) = f(12 , 6) = f(6,6) = f(6 , 0) = 6; この操作は、上記の方法と比較して、大規模データのモデル化の問題を最適化しますが、操作数は増加します：
private static int gcd(int x, int y) {.
if (y == 0) {
return x;
}
if (x < y) {
return gcd(y, x);
} else {
return gcd(x - y, y);
}
}
解決策3
解決策1の欠点は、ビッグデータの除算操作の複雑さ、解決策2は、ビッグデータの除算操作を殺したが、操作の数が増加。2つの方法は非常に完璧ではありませんし、問題を解決するために3番目の方法は、バイナリ方式を使用して3番目の方法は、それは多くの学生は、決して、実際には、このことは難しいことではありませんあきらめて01100100を参照してくださいと推定されています。
x,yについて、x = k * x1,y = k * y1 ,とすると、f(x ,y) = f(k * x1,k * y1) = k * f(x1 ,y1);これは1つです。
また、x = p * x1、pが素数でy%p ！= 0とすると、f = f(p * x1, y) = f(x1 ,y)。
と2の式から、大会の数を計算することができます：
p=2とします：
x,yが偶数だとすると、f= 2f(x "1,y "1)；
f(x,y)=f(x "1,y)；
f(x,y)=f(x,y "1)；
x,yがともに奇数であると仮定すると、f(x,y) = f(y,x-y);-これは解答2の導入部から導かれます。
以下も42と30の例：
括弧はすべて2進数式で、最悪の場合の複雑さはlog 2(max(x,y)) です。
コードを以下に添付します：
if (x < y) {
return gcd(y, x);
}
if (y == 0) {
return x;
}
if (isEven(x)) {
if (isEven(y)) {
// x，yすべてが均一である，f(x,y)=2*f(x/2,y/2)
return gcd(x >> 1, y >> 1) << 1;
} else {
// x偶数、奇数，f(x,y)=f(x/2,y)
return gcd(x >> 1, y);
}
} else {
if (isEven(y)) {
// x奇数、Yさえ，f(x,y)=2*f(x,y/2)
return gcd(x, y >> 1);
} else {
// x，yすべてが奇妙である，f(x,y)=f(x-y,y)
return gcd(x - y, y);
}
}
}
public static boolean isEven(int x) {
return (x % 2 == 0) ? true : false;
}
これらのことを考えたことがない、初めてアルゴリズムを見て、突然高いああ感じるが、確かに、以前の一般的な大会の数の問題を解決するために使用されるこのソリューションを参照してください、確かに明るいスポットああ、私は誰もがああ〜アドバイスを与えるために、より多くを願っています！
