【Java】最大公約数と最小公倍数をもとめる_Ver1

今回は入力された二つの数字から最大公約数(Greatest Common Factor...以下GCM)と最小公倍数(Least Common Multiple ... 以下LCM)を求める問題です。

コード更新しています。解説等はこのままこの記事で解説していますので、解説等読んだ後はVer2のコードを参照してください。

dadainu.hateblo.jp

LCMは以下の式から求めることができます。

入力された二つの数値をa,bとした場合、
    LCM = (a * b) / GCM

ということは、GCMを求めることができればLCMも自然と求めることができます。GCMは以下のような処理で求めることができます。

118と86の最大公約数を求める場合、
    118 = 86 * 1 + 32
    86  = 32 * 2 + 22
    32  = 22 * 1 + 10
    22  = 10 * 2 + 2
    10  = 2 * 5 + 0
    最大公約数は、2

上記で示しているのは、余りが0になるまで商を余りで割っていき、余りが0になった時の商が最大公約数であることを示しています。最大公約数の求め方をいろいろ探したのですが、公式ばかりが記載してありこれを理解するのに時間がかかりました。一度紙に書いてやってみると処理の流れが理解できると思います。

GCMとLCMの処理を以下コードで表します。

import static java.lang.System.out;
import static java.lang.Long.parseLong;
import java.io.File;
import java.util.Scanner;

public class GCDandLCM {

    public static void main(String[] args) {
        new GCDandLCM().printGCDLCM();
    }

    public void printGCDLCM() {
        try (Scanner scan = new Scanner(System.in)) {
            gcdLCM(scan);
        } catch (Exception e) {
            System.exit(0);
        }
    }

    public void printGCDLCM(String inputDataPath) {
        try (Scanner scan = new Scanner(new File(inputDataPath))) {
            gcdLCM(scan);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    public void gcdLCM(Scanner scan) {
        String inputData;
        while ((inputData = scan.nextLine()) != null && !"".equals(inputData)) {
            long[] data = getData(inputData);
            out.println(gcd(data) + " " + lcm(data));
        }
    }

    private long[] getData(String inputData) {
        String[] dataSplit = inputData.split(" ");
        long[] data = { parseLong(dataSplit[0]), parseLong(dataSplit[1]) };
        return data;
    }

    private long lcm(long[] data) {
        return (data[0] * data[1]) / gcd(data);
    }

    private long gcd(long[] data) {
        long[] tmpData = changeAB(data).clone();
        long mod = -1;
        while ((mod = tmpData[0] % tmpData[1]) != 0) {
            tmpData[0] = tmpData[1];
            tmpData[1] = mod;
        }
        return tmpData[1];
    }

    private long[] changeAB(long[] data) {
        if (data[0] < data[1]) {
            long tmp = data[0];
            data[0] = data[1];
            data[1] = tmp;
        }
        return data;
    }
}

のちのち自分用のユーティリティとして使用できるように、メソッド分割しています。一つのメソッドに大量にコードがあると後から解読するのに時間がかかってしまうので。また、引数を持つprintGCDLCMがありますが、テスト用にデータをファイルから受け取れるようにしたメソッドです。

以下テストドライバのコードです。

import org.junit.After;
import org.junit.Before;
import org.junit.Test;
import volume0.BaseTest;

public class GCDandLCMTest extends BaseTest {

    private GCDandLCM gl;

    @Before
    public void setUp() throws Exception {
        super.setUp();
        gl = new GCDandLCM();
    }

    @After
    public void tearDown() throws Exception {
        super.tearDown();
    }

    @Test
    public void testPrintGCDLCM0001() {
        try {
            gl.printGCDLCM("./data/volume0_0005/in.txt");
            outList = outContent.toString().split("\n");
            assertOut(outList, "./data/volume0_0005/out.txt");
        } catch (Exception e) {
            printErr(e);
        }
    }
}

テストで使用した「in.txt」・「out.txt」は以下の内容になります。

in.txt
8 6
50000000 30000000

out.txt
2 24
10000000 150000000

 どうやったらコードで表現できるのだろうかを考える過程は、すごく楽しいものです。また、より保守性の高いコードに仕上げる過程も楽しいです。わたしのコードでもっと良くできるところがありましたら、コメントお願いいたします。

今回の問題は以下にあります。

最大公約数と最小公倍数 | Aizu Online Judge

アルゴリスムで困った時は、以下の本を参考にしてます。Javaに置き換えるのが少々難解ですが、、、

テストドライバで継承しているクラスは以下の記事に記載しています。参考にしてみてください。

dadainu.hateblo.jp