-1

この奇妙な種類のエラーがあります。

示されているように、BigInteger クラスを使用して基本的なユークリッド アルゴリズムを実装しようとしています。実行するとStackoverFlowErrorがスローされますが、デバッグすると正しく実行され、正しい答えが得られます。

デバッグと通常の実行中の違いを真剣に理解していません。

      static BigInteger gcd(BigInteger a, BigInteger b) {
        if (a.equals(BigInteger.ZERO)) {
            return b;
        } else if (b.equals(BigInteger.ZERO)) {
            return a;
        }
        BigInteger max = a.max(b);
        BigInteger min = a.min(b);
        return gcd(max.subtract(min), min);
      }
4

2 に答える 2

0

これはGCDのユークリッドアルゴリズムではありません。正しいGCDアルゴリズムは、反復回数が実際には少ないため、再帰的な手順として簡単に説明できます。ただし、この誤って実装されたアルゴリズムは、数百万回の反復で実行される可能性があります。たとえば、「a」が1,000,000で、「b」が1の場合、100万回の再帰呼び出しが発生します。

（ただし、呼び出しは末尾再帰呼び出しであるため、優れたJava実装では実際にスタックフレームが最適化されます。ただし、ここでは発生しないようです。何らかの理由で、デバッガーバージョンで末尾呼び出しの最適化を実装できますが、奇数。）

実際のアルゴリズムでは、再帰ステップは（a --b、b）ではなく（a％b、b）です。「euclidGCDアルゴリズム」のGoogle。

于 2012-05-18T14:44:01.620 に答える
0

繰り返される減算を mod 操作に置き換えれば、このアルゴリズムで必要な呼び出しは少なくなります。max が非常に大きく、min が非常に小さい場合にどうなるかを確認してください。

于 2012-05-18T11:19:50.757 に答える