12

質問は次のとおりです。

「2 つの整数をパラメーターとして受け取り、2 つの数値の最大公約数を返す gcd という名前のメソッドを作成します。2 つの整数 a と b の最大公約数 (GCD) は、a と b の両方の因数である最大の整数です。任意の数と 1 の GCD は 1 であり、任意の数と 0 の GCD はその数です。

2 つの数値の GCD を計算する効率的な方法の 1 つは、ユークリッドのアルゴリズムを使用することです。

GCD(A, B) = GCD(B, A % B) 
GCD(A, 0) = Absolute value of A"

この問題を解決する方法について、私は本当に混乱しています。これまでのプログラムで何が間違っていたかについて、いくつかのヒントとヒントが欲しいだけです。(私はスキャナーを入れなければなりません。それが私の先生の要件です。) 私はこれを自分で解決したいので、完全なコードを教えないでください。上記の式をどのように組み込むかについてのヒントを教えてください。(そして、なぜ == 0 を入れたのか疑問に思っているなら、それは、0 と 90 という 2 つの数字がある場合、それらの GCD は 0 になると思ったからですよね??)

また、私のコードには while ループを含める必要があります... if ループの方がいいと思います...

前もって感謝します！:)

私の現在のプログラム:

public static void main(String[] args) {
        Scanner console = new Scanner(System.in);
        int a = console.nextInt();
        int b = console.nextInt();
        gcd (a, b);
    }

    public static void gcd(int a, int b) {
        System.out.print("Type in two numbers and I will print outs its Greatest Common Divisor: ");
        int gcdNum1 = console.nextInt();
        int gcdNum2 = console.nextInt();
        while (gcdNum1 == 0) {
            gcdNum1 = 0;
        }
        while (gcdNum2 > gcdNum1) {
            int gcd = gcdNum1 % gcdNum2;
        }
        System.out.print(gcdNum1 + gcdNum2);
    }
}
4

8 に答える 8

35

再帰的な方法は次のようになります。

static int gcd(int a, int b)
{
  if(a == 0 || b == 0) return a+b; // base case
  return gcd(b,a%b);
}

while ループの使用:

static int gcd(int a, int b)
{
  while(a!=0 && b!=0) // until either one of them is 0
  {
     int c = b;
     b = a%b;
     a = c;
  }
  return a+b; // either one is 0, so return the non-zero value
}

を返すときa+b、実際には、そのうちの 1 つが 0 であると仮定して、ゼロ以外の数値を返しています。

于 2012-12-02T20:49:22.293 に答える
8

3行の方法でそれを行うこともできます:

public static int gcd(int x, int y){
  return (y == 0) ? x : gcd(y, x % y);
}

ここで、 の場合y = 0、x が返されます。それ以外の場合は、gcd別のパラメーター値でメソッドが再度呼び出されます。

于 2013-11-15T18:12:27.650 に答える
1 
import java.util.Scanner;


public class Main {




public static void  main(String [] args)
{
    Scanner input = new Scanner(System.in);
    System.out.println("Please enter the first integer:");
    int b = input.nextInt();
    System.out.println("Please enter the second integer:");
    int d = input.nextInt();

    System.out.println("The GCD of " + b + " and " + d + " is " +  getGcd(b,d) + ".");
}


public static int getGcd(int b, int d)
{
    int gcd = 1;

    if(b>d)
    {
        for(int i = d; i >=1; i--)
        {
            if(b%i==0 && d%i ==0)
            {
                return i;
            }
        }
    }
    else
    {
        for(int j = b; j >=1; j--)
        {
            if(b%j==0 && d% j==0)
            {
                return j;
            }
        }
    }   
    return gcd;

}
}
于 2013-03-19T04:11:48.357 に答える
0 
import java.util.Scanner;

class CalculateGCD 
{   
  public static int calGCD(int a, int b) 
  { 
   int c=0,d=0;  
   if(a>b){c=b;} 
   else{c=a;}  
   for(int i=c; i>0; i--) 
   { 
    if(((a%i)+(b%i))==0) 
    { 
     d=i; 
     break; 
    } 
   } 
   return d;  
  }  

  public static void main(String args[]) 
  { 
   Scanner sc=new Scanner(System.in); 
   System.out.println("Enter the nos whose GCD is to be calculated:"); 
   int a=sc.nextInt(); 
   int b=sc.nextInt(); 
   System.out.println(calGCD(a,b));  
  } 
 }
于 2014-04-06T22:57:52.133 に答える
0 
private static void GCD(int a, int b) {

    int temp;
    // make a greater than b
    if (b > a) {
         temp = a;
         a = b;
         b = temp;
    }

    while (b !=0) {
        // gcd of b and a%b
        temp = a%b;
        // always make a greater than bf
        a =b;
        b =temp;

    }
    System.out.println(a);
}
于 2013-11-11T01:49:55.523 に答える
0

さて、一週間ほど前にプログラミングを始めたばかりなので、たいしたことはありませんが、これを問題として思いついたので、プログラミングを始めたばかりの人にとっては理解しやすいかもしれません。前の例のように Euclid の方法を使用します。

public class GCD {
  public static void main(String[] args){
    int x = Math.max(Integer.parseInt(args[0]),Integer.parseInt(args[1]));    
    int y = Math.min(Integer.parseInt(args[0]),Integer.parseInt(args[1]));     
    for (int r = x % y; r != 0; r = x % y){
      x = y;
      y = r;
    }
    System.out.println(y);
  }
}
于 2014-06-24T04:17:43.047 に答える
0

それを行う 1 つの方法は、以下のコードです。

        int gcd = 0;
        while (gcdNum2 !=0 && gcdNum1 != 0 ) {
        if(gcdNum1 % gcdNum2 == 0){
            gcd = gcdNum2;
        }
            int aux = gcdNum2; 
            gcdNum2 = gcdNum1 % gcdNum2;
            gcdNum1 = aux;
    }

これを行うために再帰は必要ありません。

注意してください、数値がゼロの場合、GCD はゼロではない数値です。

    while (gcdNum1 == 0) {
    gcdNum1 = 0;
}

要件を満たすようにこれを変更する必要があります。

コードを完全に変更する方法を説明するつもりはありません。gcd の計算方法だけを説明します。

于 2012-12-02T20:51:10.633 に答える