0
Help us understand the problem. What are the problem?

More than 5 years have passed since last update.

posted at

updated at

Organization

Javaでユーグリッドの互除法を実装してみた

ユーグリッドの互除法とは

2つの自然数の最大公約数を求めるアルゴリズム。

簡単に表すと

a % b = r
b % r = s
r % s = 0

といった形で、割る数を次の割られる数、余りを次の割る数にして再帰的にそれを繰り返して行く。
余りが0になった時の割る数(上の例だとs)が自然数aとbの最大公約数になる。

参考
ユークリッドの互除法の証明と不定方程式 | 高校数学の美しい物語

実装してみた

package com.company;

import java.io.*;

class Main {
    public static void main(String[] args) {
        try {
            BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
            String[] str = bufferedReader.readLine().split(" ");
            int x = Integer.parseInt(str[0]);
            int y = Integer.parseInt(str[1]);

            System.out.println(getCommonDivisor(x, y));

        } catch (Exception e) {
            System.out.println(e);
        }
    }

    private static int getCommonDivisor(int x, int y) {
        int biggerNum = Math.max(x, y);
        int smallerNum = Math.min(x, y);

        // 大きい方から小さい方を割った余を求める
        int surplus = biggerNum % smallerNum;

        // 割り切れていれば、それを返す
        if (surplus == 0) {
            return smallerNum;
        }
        // 割り切れなければ再帰的に自信を呼び出す
        surplus = getCommonDivisor(smallerNum, surplus);

        return surplus;
    }
}

試してみる

// 入力
390 273 

// 出力
39

追記(2017年6月23日)

上記のコードは、もともと入力などについては深く考えず、ただアルゴリズムを実装してみたというものだったので、例外処理などを考慮しておらず、簡単に落ちます。

そこで、@saka1029 さんからいただいたコメントを反映したコードを新たに記述しました。
@saka1029 さん、ありがとうございました。

今回は、以下のような条件でコードを記述しています。

ユークリッドの互除法の実装なら負の数は入り口ではじく。

数字以外のものの入力がされても、落ちない

また、自然数に0を含める流派と自然数に0を含めない流派が存在しますが、今回は、「自然数に0を含めない流派」を採用します。

例外処理を行ったコード

package com.company;

import java.io.*;

class Main {
    private static int x = -1;
    private static int y = -1;
    private static final String caution = "自然数を半角空白区切りで2つ入力してください(ただし、本プログラムでは自然に0は含めないものとする)";

    public static void main(String[] args) {
        System.out.println(caution);
        readInput();
        System.out.println(doEuclideanAlgorithm(x, y));
    }

    private static void readInput() {
        try {
            while (x <= 0 || y <= 0) {
                BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
                String[] str = bufferedReader.readLine().split(" ");
                x = Integer.parseInt(str[0]);
                y = Integer.parseInt(str[1]);
                if (x <= 0 || y <= 0) {
                    System.out.println("入力が不適切です。" + caution);
                }
            }
        } catch (Exception e) {
            System.out.println("入力が不適切です。" + caution);
            readInput();
        }
    }

    private static int doEuclideanAlgorithm(int x, int y) {
        int biggerNum = Math.max(x, y);
        int smallerNum = Math.min(x, y);

        // 大きい方から小さい方を割った余を求める
        int surplus = biggerNum % smallerNum;

        // 割り切れていれば、それを返す
        if (surplus == 0) {
            return smallerNum;
        }
        // 割り切れなければ再帰的に自信を呼び出す
        surplus = doEuclideanAlgorithm(smallerNum, surplus);

        return surplus;
    }
}

試してみた

自然数を半角空白区切りで2つ入力してください(ただし、本プログラムでは自然に0は含めないものとする)
a a
入力が不適切です。自然数を半角空白区切りで2つ入力してください(ただし、本プログラムでは自然に0は含めないものとする)
390 0
入力が不適切です。自然数を半角空白区切りで2つ入力してください(ただし、本プログラムでは自然に0は含めないものとする)
0 273 
入力が不適切です。自然数を半角空白区切りで2つ入力してください(ただし、本プログラムでは自然に0は含めないものとする)
-390 273
入力が不適切です。自然数を半角空白区切りで2つ入力してください(ただし、本プログラムでは自然に0は含めないものとする)
390 -273
入力が不適切です。自然数を半角空白区切りで2つ入力してください(ただし、本プログラムでは自然に0は含めないものとする)
390 273 
39

その他

「ここおかしいよ」とか「もっとスマートにできるよ」ということがあったら、コメントいただけたら嬉しいです。

さらに追記(2017年6月23日)

@howdy39 さんのコメントにいただいた通り、微妙な箇所がありました。
@howdy39 さん、ありがとうございました。
@howdy39 さんのご指摘を採用させていただいたスマートなコードがこちら。

例外があった際にreadInput()を再帰的に実行しているので、while文はいりませんでした。

 実装

package com.company;

import java.io.*;

class Main {
    private static final String caution = "自然数を半角空白区切りで2つ入力してください(ただし、本プログラムでは自然に0は含めないものとする)";

    public static void main(String[] args) {
        System.out.println(caution);
        int[] inputs = readInput();
        System.out.println(doEuclideanAlgorithm(inputs[0], inputs[1]));
    }

    private static int[] readInput() {
        try {
            BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
            String[] str = bufferedReader.readLine().split(" ");
            int x = Integer.parseInt(str[0]);
            int y = Integer.parseInt(str[1]);
            if (x <= 0 || y <= 0) {
                throw new Exception("");
            }
            return new int[]{x, y};
        } catch (Exception e) {
            System.out.println("入力が不適切です。" + caution);
            return readInput();
        }
    }

    private static int doEuclideanAlgorithm(int x, int y) {
        int biggerNum = Math.max(x, y);
        int smallerNum = Math.min(x, y);

        // 大きい方から小さい方を割った余を求める
        int surplus = biggerNum % smallerNum;

        // 割り切れていれば、それを返す
        if (surplus == 0) {
            return smallerNum;
        }
        // 割り切れなければ再帰的に自信を呼び出す
        surplus = doEuclideanAlgorithm(smallerNum, surplus);

        return surplus;
    }
}

実行結果

自然数を半角空白区切りで2つ入力してください(ただし、本プログラムでは自然に0は含めないものとする)
a a 
入力が不適切です。自然数を半角空白区切りで2つ入力してください(ただし、本プログラムでは自然に0は含めないものとする)
390 0
入力が不適切です。自然数を半角空白区切りで2つ入力してください(ただし、本プログラムでは自然に0は含めないものとする)
0 273 
入力が不適切です。自然数を半角空白区切りで2つ入力してください(ただし、本プログラムでは自然に0は含めないものとする)
-390 273
入力が不適切です。自然数を半角空白区切りで2つ入力してください(ただし、本プログラムでは自然に0は含めないものとする)
390 -273
入力が不適切です。自然数を半角空白区切りで2つ入力してください(ただし、本プログラムでは自然に0は含めないものとする)
390 273
39

参考にさせていただいたサイト

ユークリッドの互除法の証明と不定方程式 | 高校数学の美しい物語

※ ブログでも同一の投稿をしている
Javaでユーグリッドの互除法を実装してみた

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Sign upLogin
0
Help us understand the problem. What are the problem?