この記事では、2つの非陰性整数の最大の共通除数を解決するためのJavaのアルゴリズムについて説明します。次のように、参照のために共有してください。
コード関数：
1。Java実装（テストケースを備えた完全なソースコード）;
2。2つの非陰性整数pとq（p> = q）の最大の共通除数を解決します。
3。2つのソリューション：ループ法と再帰的方法。
完全なソースコード：
/ * gcd：Greateast Common divisor */public class gcd {public static void main（string args []）{/ * test case */int p = 32; int q = 24; System.out.println（ ""+p+"および"+q+"の最大の除数は /n"+"[gcd1]："+gcd1（p、q）+" /n"+"[gcd2]："+gcd2（p、q））; } //（q％gcd == 0およびp％gcd == 0 [qから1]）public static int gcd1（int p、int q）{int gcd = 1; int d = q; while（d> 0）{d--; if（q％d == 0 && p％d == 0）{gcd = d;壊す; }} gcdを返します。 } // gcd（p、q）= gcd（q、p％q）[q = 0、gcd = p] public static int gcd2（int p、int q）{if（q == 0）return p; int r = p％q; //system.out.println("( "+q+"、"+r+ "）"）; gcd2（q、r）を返します。 }}ランニングスクリーンショット：
コード説明：
円形の方法GCD1（P、Q）
自然言語の説明：ループ法は、2つの非陰性整数p、q（p> = q）の最大の共通除数を解決します。つまり、pの共通除数の最大値をp。 p（Decrent Step = 1）DからのD（分割）の減少は、常に「満たされようとしている条件の最大値」であるとします。 dが条件を満たしている場合（pで割ることができ、pで割り切れることができます）、dはpとqの一般的な除数であり、dはpとqの最大の共通除数です。
再帰方法GCD2（P、Q）
自然言語の説明：再帰的方法は、2つの非陰性整数P、Q（p> = q）の最大の共通除数を解決します。 qが0に等しい場合、最大の一般的な除数はpです。それ以外の場合、PとQの残りの部分を取り、R = P％Qを取得し、PとQの最大の共通除数はQおよびRの最大の共通除数です。
コードエクスペリエンス：
ループ方法に関しては、最初は一般的な除数を解決する方法を作成し、整数配列を使用して非陰性整数のすべての一般的な除数を保存し、2つの数字の最大の一般的な除数であるPとQで一般的な最大の除数を比較して調べることでした。後で、それは最大を見つけるためであるため、背面から正面に直接減少する方が簡単ではないと思いましたか？背面から前面に減少すると、この数が常に最大であることを保証できます。これは、条件を満たしていないよりも大きい人（同時にPとQで分割できる）を排除するため、最大値を最初に見つけるのを防ぐことができます。最大値を見つける方法はたくさんありますが、証明して検索する必要があるかどうかは多くありますが、ハハ、なぜ哲学について少し感じるのですか？
再帰に関して、私の直感に基づいて完全に理解できるのは、PとQの最大の共通の除数がQとRの最大の共通除数であるという唯一の文であり、リングの始まりですが、リングの終了条件が0であることをまだ理解していません。
これは、最大の一般的な分裂アルゴリズムに対する非常に簡単な解決策ですが、主に私があまりよく知らない再帰方法を感じるために、2つの方法でそれを書く必要があります。過去に、私はそこで照らされたハノーバータワーとフィボナッチ数を解くための再帰アルゴリズムの明確な式を見ました、そして、私はこれが完全に数学であるとため息をついていました！今日私が学んだ気持ちは、その時よりもさらに衝撃的でした。私は何が起こったのだろうと思って、それを奇妙に解決しました。当時、私は記憶、効率、その他の指標についてあまり気にしませんでした。これを考えることができる人たちは本当に賢いと思った。彼らにとって、それがコンピューターであろうとプログラミング言語であろうと、それは問題を解決するための単なるツールでした。一部の人々は、再帰は脳がコンピューターについて考えることを可能にするアルゴリズムであり、それは本当に適切だと感じていると言う人もいます。
参照
チューリングプログラミングシリーズ：アルゴリズム（第4版）ロバートセッジウィック（著者）、ケビンウェイン（著者）、Xie Luyun（翻訳者）
Javaアルゴリズムの詳細については、このサイトに興味のある読者は、「Javaデータ構造とアルゴリズムのチュートリアル」、「Java操作DOMノードのヒントの要約」、「Javaファイルの要約およびディレクトリ操作のヒント」、「Java Cache操作のヒントの要約」というトピックを見ることができます。
この記事がみんなのJavaプログラミングに役立つことを願っています。