インスピレーションプログラミング: 最大公約数アルゴリズムの分析

2 つの正の整数が与えられたら、その最大公約数を求めます。これは、コードを書く学生なら誰でも遭遇したことがある問題だと思います。もちろん、解決法はいくつもあります。以下は、アルゴリズム処理をまったく行わないプログラムです。

 公共 静的  int getResult( int a, int b){
 int最大値 = (a>b)?a:b; 
     int結果 = 0 ; 
     ( int i = 1 ;i < max;i++) { 
         (a%i == 0 && b%i == 0 )の場合{
            結果=i;
        }
    } 
    結果を返します。
 }

これは確かに解決可能ですが、より大きな正の整数をループする必要があり、両方の数値が非常に大きい場合は、効率が非常に低くなります。非効率的なプログラムに遭遇すると、必然的に最適化について考えることになりますが、アルゴリズムの最適化は常に非常に信頼できる方法です。最大公約数問題を解決するためのアルゴリズムを追加する方法はいくつかあります。

解決策1:

ユークリッドのアルゴリズムでは、正の整数 num1 と num2 の最大公約数を求めたいとします。f(x,y) は 2 つの最大公約数です。k = x / y (切り捨て)、b = x % y (余り) とすると、x = ky + b となり、x と y の両方で割り切れる数は b と y でも割り切れる必要があり、b と y で割り切れる数は x と y の両方で割り切れる必要があります。つまり、x と y の最大公約数は b と y の最大公約数であるため、f (x, y) = f(y, x%y) (x>=y>0) となり、これを再帰的に行うことができます。たとえば、

f(42,30) = f(30,12) = f(12 , 6) = f(6,0) = 6; これにより、計算回数が大幅に削減されます。コードは以下に添付されています:

 int結果 = ((y == 0 ) ? x : gcd(y, x % y)); 
    結果を返します。
 }

解決策2:

解決策 1 は、公約数を見つける問題を非常にうまく解決しますが、アルゴリズムには除算が含まれており、コンピューターでの除算のオーバーヘッドが非常に高くなります。除算を回避することは可能ですか?これを次のように考えることができます。ある数が x と y に分割できる場合、その数は xy と y にも分割できる必要があります。言い換えると、x と y に分割できる数は、その数が xy と y に分割されるための必要かつ十分な条件です。すると、f(x, y) = f(xy , y) となり、このように計算することで、大きな整数間の剰余演算を大きな整数間の減算演算に変換することができます。 f(x, y) = f(y, x) なので、正の数と負の数の最大公約数を見つけないようにするには、柔軟に f(x, y) = f(y, x) を使用して、片側が 0 になるまで反復する必要があります。たとえば、次のようになります。

f(42,30) = f(30,12) = f(18 , 12) = f(12 , 6) = f(6,6) = f(6 , 0) = 6; 上記の方法と比較すると、この操作は大きなデータ係数の問題を最適化しますが、操作の数が増えます。コードは次のとおりです。

プライベート静的int gcd(int x, int y) {

 y == 0の場合
         xを返します。
    } 
    もし（x < y）{ 
         gcd(y, x)を返します。
    }それ以外{ 
         gcd(x - y, y)を返します。
    }
 }

解決策3:

ソリューション 1 の欠点は、ビッグ データの分割操作が複雑であることです。ソリューション 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(x, y) = f(p * x1, y) = f(x1, y) となり、これは 2 です。

式 1 と 2 から、公約数を計算できます。

p=2と仮定します。

x と y が両方とも偶数であると仮定します: f(x, y) = 2f(x»1, y»1);

x が偶数で y が奇数であると仮定します: f(x,y) = f(x»1,y);

x が奇数で y が偶数であると仮定します: f(x,y) = f(x,y»1);

x と y が両方とも奇数であると仮定します: f(x,y) = f(y,xy); - これはソリューション 2 から導出されます。

42 と 30 を例に挙げてみましょう。

f(42,30) = f(101010,11110) = 2f(10101,1111) = 2f(1111,110)=2 * f(1111,11) = 2 f (1100,11) = 2f(110,11)=2 f(11,11) = 2 f(0,11) = 2 3=6

括弧内のすべてはバイナリで表現されるため、最悪の場合、複雑さは log 2(max(x,y)); になります。 - 2 が底です。 くそ、この形式を正しく理解できない。

コードは以下に添付されています:

もし（x < y）{ 
         gcd(y, x)を返します。
    } 
     y == 0の場合
         xを返します。
    } 
     if (isEven(x)) { 
         if (isEven(y)) { 
             // x、y は両方とも偶数なので、f(x,y)=2*f(x/2,y/2)  
             gcd(x >> 1 , y >> 1 ) << 1を返します。
        }それ以外{ 
             // x は偶数、y は奇数、f(x,y)=f(x/2,y)  
             gcd(x >> 1 , y)を返します。
        }
    }それ以外{ 
         if (isEven(y)) { 
             // x は奇数、y は偶数、f(x,y)=2*f(x,y/2)  
             gcd(x, y >> 1 )を返します。
        }それ以外{ 
             // x、y は両方とも奇数なので、f(x,y)=f(xy,y)  
             gcd(x - y, y)を返します。
        }
    }
 } 
 
公共 静的 ブール型isEven( int x) { 
    戻り値(x % 2 == 0 ) ? true : false ;
 }

これまでこのようなことを考えたことはありませんでした。初めてアルゴリズムを見たとき、とても高度なものだと思いました。しかし、以前解いていた公約数の問題をこのように解くのを見ると、本当に目を見張るものがあります。皆さんがもっと提案してくれると嬉しいです〜

オリジナルリンク: http://my.oschina.net/u/858241/blog/209774