指定された配列の GCD ペアを検索します

Java Q&A: 指定された配列の GCD ペアを見つけることは、配列内の数値の最大公約数 (GCD) の計算を必要とする一般的な問題です。 Java では、ユークリッド アルゴリズムを使用してこの問題を解決できます。この記事では、PHP エディターの Xigua が、Java を使用して特定の配列の GCD ペアを見つけるメソッドを記述する方法を紹介し、読者がこのアルゴリズムをよりよく理解し、適用できるようにします。

質問内容

サイズ n の整数配列が与えられます。n は偶数です。配列から 2 つの数値を選択し、gcd を求めます。同様に、配列内の残りの項目から 2 つの項目を選択し、gcd を見つけます。上記の手順を繰り返して、gcd ペアを見つけます。 gcd 値を合計し、最大の合計を取得します。

制約:

リーリー

例 1:

リーリー ＃＃＃＃＃＃答え：＃＃＃＃＃＃ リーリー

イラスト:

リーリー

例 2:

リーリー ＃＃＃＃＃＃答え：＃＃＃＃＃＃ リーリー

イラスト:

リーリー

これは私のコードです: リーリー 私のコードは最初の例では機能しますが、2 番目の例では間違った出力が得られます。 デバッグしたところ、使用していた方法が間違っていることがわかりました。この問題を解決する正しい方法は何ですか?

解決策総 gcd を計算するすべての可能な方法を再帰的に検索できます。何をするか？

配列に要素が 2 つだけ含まれている場合は、これら 2 つの要素の gcd のみを返すことができます。

さらに多くの値が含まれている場合は、すべての値のペアを繰り返し処理します。各ペアについて、その gcd を計算し、両方の値が削除された配列のコピーを使用して関数を再帰的に呼び出します。両方の計算の結果を加算すると、現在選択されている値のペアの合計 gcd が得られます。

ここで、これまでに見つかった最高の gcd を追跡し、最後にそれを返します。

これはまさにそれを行う(はずの)コードです。

リーリー

このアルゴリズムは非常に遅いです。作業をスピードアップする必要がある場合、改善できる領域が少なくとも 2 つあります。

gcd の計算は高価な操作です。

考えられる一意の値のすべてのペアの gcd を事前計算し、それらをハッシュマップに保存すると、二重計算が排除されます。

いくつかの可能な順列を複数回チェックします。 (例: 次の再帰で最初のペアを選択してから 2 番目のペアを選択することは、2 番目のペアを選択してから最初のペアを選択することと同じです)

この問題を解決する方法について漠然としたアイデアがありますが、今夜は遅すぎます はい、 ごめん。

• おそらく、より高速なアルゴリズムがあると思われますが、これは単なる私の考えです。
• 編集者
: そうですね、少し寝てから、急に理解できました。ペアを作成するときに外側のループを省略すると、ペアの重複した並べ替えは行われません。基本的には、次のように

i

を 0 に置き換えるだけです。 リーリー

以上が指定された配列の GCD ペアを検索しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。