【Java】ユークリッドの互除法をJavaで実装してみる【アルゴリズム】

はじめに

基礎的なアルゴリズムをJavaで実装していきます。
今回は 「ユークリッドの互除法」 です。

ユークリッドの互除法

目的：
2つの値(A, B)の最大公約数を求めます。

手段：
「AとBで 大きい方 - 小さい方 を繰り返して、AとBが同じ値になったらそれが最大公約数だよ」というアルゴリズムです。

設計

呼び出し元のMainクラスと、処理を行うEucridクラスに分けました。
さらにEucridクラスの中でもユーザーから入力を受け付け処理を呼び出して表示するView・Controller部分と、アルゴリズムの核心的処理を行うModel部分を別のメソッドにしてみました。

それぞれのクラス・メソッドの役割を明確にして、結合度を下げることで変更に強い設計を意識しています。

今回はユーザーに値を入力してもらう形にしましたが、例えばこれをCSVを読み込んで処理するように変更したいと思ったとき、変更するのは EucridStarter() だけになります。
入力や出力が何であれ、このアルゴリズムの根幹であるEucridExec(int a, int b)は変わらないからです。

わずかな変更であってもバグを作り込まないとも限らないので、変更の影響範囲は極力小さくすることを心がけます。

ソース

フォルダ構成

ソースコード

main.java

package main;

import process.Eucrid;

public class Main {

	public static void main(String[] args) throws InterruptedException {
		// ユークリッドクラスをインスタンス化して処理をスタート
				Eucrid eucrid = new Eucrid();
				eucrid.EucridStarter();
	}
}

Eucrid.java

package process;

import java.util.Scanner;

public class Eucrid {
	public void EucridStarter() throws InterruptedException {
		//変数の初期化
		int a = 0;
		int b = 0;

		// ユーザーに数を2つ入力してもらう
		Scanner sc = new Scanner(System.in);

		System.out.println("【ユークリッドの互除法】");
		System.out.println("2つの値を入れると、最大公約数を計算して表示します。");
		System.out.println("まず1つ目の値を整数で入力してください。");
		a = Integer.parseInt(sc.nextLine());

		System.out.println("2つ目の値を整数で入力してください。");
		b = Integer.parseInt(sc.nextLine());
		sc.close();

		// 2つの値を引数でユークリッドの互除法メソッドに渡して実行
		int result = EucridExec(a, b);

		System.out.println("考えています...");
		Thread.sleep(1000); //待機

		// 結果をコンソールに表示	
		if (result == 1) {
			System.out.println("2つの数は互いに素です。");
		} else {
			System.out.println(a + "と" + b + "の最大公約数は" + result + "です。");
		}
	}

	public int EucridExec(int a, int b) {
		// aとbが一緒になるまで繰り返す
		while (a != b) {
			// 値が大きい方から小さい方を引き、結果を値が大きい方の変数に代入する
			if (a > b) {
				a = a - b;
			} else {
				b = b - a;
			}
		}
		return a;
	}
}

実行

おわりに

アルゴリズム自体はシンプルですが、プログラムで表現しようとすると標準入力の受け取り方から型変換など色々な要素が関わってきます。
基礎練習にはもってこいの題材だと思いました。

参考図書

基本情報技術者試験のアルゴリズム問題がちゃんと解ける本 第2版 [矢沢 久雄]

記事リンク