java - Basic Java: 最大公約数を見つける

Question

次の式を使用して、ユーザーが入力した 2 つの数値の最大公約数を見つけるプログラムを作成する必要があります。

x >= y の場合は gcd(x, y) = gcd(x – y, y)、x < y の場合は gcd(x, y) = gcd(x,yx) です。

例: gcd(72, 54) = gcd(72 – 54, 54) = gcd(18, 54) 72 > 54 なので、72 を 72 – 54 = 18 に置き換え、新しい値でループを続けます。

反復 2: gcd(18, 54) = gcd(18, 54 – 18) = gcd(18, 36) 18 < 54 なので、54 を 54 – 18 = 36 に置き換え、新しい値でループを続けます。

反復 3: gcd(18, 36) = gcd(18, 36 – 18) = gcd(18, 18) 18 < 36 なので、36 を 36 – 18 = 18 に置き換え、新しい値でループを続けます。

反復 4: gcd(18, 18) = gcd(18 – 18, 18) = gcd(0, 18) = 18 18 >= 18 なので、最初の 18 を 18 – 18 = 0 に置き換えます。 0 ループを続行しません。ゼロ以外の値 18 は gcd です。

ここに私がこれまでに持っているコードがあります:

ここに画像の説明を入力

「不正な式の開始」というエラーが表示されます。

score 0 · Accepted Answer

あなたはすでに最初の文で答え (アルゴリズム) を述べています。

gcd(x, y) = gcd(x – y, y) if x >= y and gcd(x, y) = gcd(x,y-x) if x < y.

では、それをどのようにコードに変換するのでしょうか? 方程式の左側はメソッドプロトタイプで、右側はメソッド本体です。

public static int gcd(x, y)  // doesn't HAVE to be public or static
{
  gcd(x – y, y) if x >= y and gcd(x, y) = gcd(x,y-x) if x < y
}

しかし、本体のコードはコンパイルされないため、本体を書き直す必要があります。"and gcd(x, y) = ..."はメソッドプロトタイプの繰り返しであるため、削除されていることに注意してください。

public static int gcd(x, y)
{
  if (x >= y)
  {
    return ... // you fill this in
  }
  else if (x < y)
  {
    return ... // you fill this in
  }
}

最後の「else-if」チェックは実際には必要ありませんが、教師はおそらくそこを見たいと思っていることに注意してください。

編集：

これはおそらく再帰の教室での演習であるため、から取った次の作業例を検討してjavax.swing.table.DefaultTableModelください。

private static int gcd(int i, int j)
{
  return (j == 0) ? i : gcd(j, i%j);
}

補足: これは提出しないでください。明らかに、与えられたアルゴリズムから派生したものではありません。教師は間違いとしてマークする可能性があります。

三項演算子の構文を学習していない可能性があるため、次のように書き直します。

private static int gcd(int i, int j)
{
  if (j == 0)
    return i;
  else
    return gcd(j, i%j);
}

これは再帰の例です。特定の状況下では既知の値を返すことができますが、それ以外の場合、メソッドは別のパラメーターセットを使用して自分自身を再度呼び出す必要があります。

編集2：

再帰的なアプローチの代わりに対話的なアプローチが必要なため、すべての再帰的なメソッドは反復を使用して (つまり、ループを介して) 書き直すことができることを覚えておいてください。

参考文献：

3 に答える 3