Javaによるアルゴリズムとデータ構造

戻る  

演習5-3の解答

// 演習5-3
// 配列の全要素の最大公約数を求める

import java.util.Scanner;

class GCDArray {

  //--- 整数値x, yの最大公約数を非再帰的に求めて返却 ---//
  static int gcd(int x, int y) {
    while (y != 0) {
      int temp = y;
      y = x % y;
      x = temp;
    }
    return (x);
  }

  /*--- 要素数nの配列aの全要素の最大公約数を求める ---*/
  static int gcdary(int a[], int start, int no) {
    if (no == 1)
      return a[start];
    else if (no == 2)
      return gcd(a[start], a[start + 1]);
    else
      return gcd(a[start], gcdary(a, start + 1, no - 1));
  }

  public static void main(String[] args) {
    Scanner stdIn = new Scanner(System.in);
    System.out.print("何個の整数の最大公約数を求めますか：");
    int num;
    do {
      num = stdIn.nextInt();
    } while (num <= 1);

    int[] x = new int[num];          // 長さnumの配列

    for (int i = 0; i < num; i++) {
      System.out.print("x[" + i + "]：");
      x[i] = stdIn.nextInt();
    }

    System.out.println("最大公約数は" + gcdary(x, 0, num) + "です。");
  }
}

戻る