いろいろな計算処理（アルゴリズム）を書いてみる - Java で始めるプログラミング入門

実は，繰返し処理と条件分岐さえあれば，どんなプログラムでも書くことができるようになります．
# 正確には計算可能なものだけ．たとえば，任意のプログラムを入力として受け付け，それが終了するかしないかを判定するプログラムは（たとえどのようなプログラミング言語を用いても）書くことができません．
さて，せっかく条件分岐と繰返し処理を学んだので，単に入力された値を表示するといった単純なものではなく，もっとコンピュータに計算をさせるようなプログラムをいくつか書いてみることにしましょう．

最大公約数を求める

まずは，小学校のころを思い出して，与えられた２つの数の最大公約数を求めるプログラムを作成してみることにします．最大公約数とは２つの数を割り切る最大の数なので，たとえば，60と24という２つの数が与えられたとき，最大公約数は12になります．
さて，どのようにプログラムを書けばよいでしょうか？
まず，思い浮かぶ簡単な方法は，最大公約数の候補を適当に生成して，それらが与えられた２つの数を割り切るかどうかひとつずつ試していく，というものです．ようするにコンピュータの力を利用して力任せに問題を解くという手法（brute-force）です．最大公約数を求める問題の場合，与えられた２つの数のうち，小さい値からはじめて，１つずつ数を減らしていきながら，割り切れるかどうか調べていく，というものになります．

//
// 力任せ法（brute-force）によって最大公約数を求める
//
public class GCD {
    public static void main(String[] args) {
        // 入力された文字列を整数に変換する
        int p = Integer.parseInt(args[0]);
        int q = Integer.parseInt(args[1]);
        int d = Math.min(p, q);         // pとqのうち小さい方を返す

        for (/* 初期化コードは省略 */; d >= 1; d--) {
            if (p % d == 0 && q % d == 0) break;
        }
        System.out.printf("%dと%dの最大公約数は%dです\n", p, q, d);
    }
}

このプログラムは，これまで紹介した標準入力からではなく，コマンドライン引数から入力を受け取ります．コマンドライン引数とは，プログラムの起動時に与えるパラメータのことで，たとえば，上のプログラムの場合，以下のように２つのパラメータを与えてプログラムを起動します．

$ java GCD 60 24
60と24の最大公約数は12です

ここで与えた60と24という数は，mainメソッドの引数であるargsという変数に渡されます．argsは文字列の配列型（String[]）の変数で，args[0]に1目のコマンドライン引数である60が，args[1]には2番目の12が文字列として格納されます．つぎに，渡された文字列を整数値に変換してやる必要があります．これは，Integer.parseInt(args[0])の部分です．こうして，あらためて整数値としての値を得て，それらでpとqの変数を初期化しているのです．そして，pとqのうち小さい方を最初の候補として変数dを初期化します．（Math.min(p, q)の部分）
あとは，dの値を１つずつ減らして（d--）いきながら，dがpとqを割り切るかどうかを調べていくわけです．p % dはpをdで割ったときの余りを求めます．したがって，p % d == 0は余りが0かどうかの判定，すなわち，pがdで割り切れるかどうかを調べています．

プログラムをより堅牢にする

さて，上で紹介したプログラムには実はいくつか問題点があります．たとえば，以下のようにプログラムに与えるコマンドライン引数を１つだけにして起動したら，何が起こるでしょうか？

$ java GCD 60

筆者の環境では，以下のようなメッセージが表示されてしまいました．

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 1
        at GCD.main(GCD.java:8)

これは，プログラム(GCD.java)の8行目で，ArrayIndexOutOfBoundsExceptionという例外が発生したことを示しています．この例外は，配列の範囲外の要素にアクセスしたときに発生します．このケースでは，コマンドライン引数が１つしか与えられなかったにもかかわらず，2つ目の要素（args[1]）にアクセスしたため，Javaの実行時システムが例外を投げた（例外を発生させることを，例外を投げる，と言います）のです．
さきほどのプログラムは，コマンドライン引数を２つ受け取ることを想定して書いたので，このように実際は１つだけしか与えられなかった，といったケースに対応していませんでした．この問題に対処する方針としてはいくつか考えられます．

どうせ，１つの数に対する最大公約数なんてあまり意味がないので，とりあえず気にしない．
入力をチェックして，２つの引数が与えられなかった場合，適当なエラーメッセージを出して終了する．
１つ以上（2つでも3つでも4つでも．．．）の数に対しても最大公約数を求められるようにアルゴリズムを修正する．

どの対処方法が正しいかどうかは，プログラムの使われ方によってかわってきます．個人的に使うプログラムで例外が発生しても気にしなくて済むならば，1のアプローチが簡単です．でも，自分の作ったプログラムを他人に使ってもらうような場合，突然例外が発生してプログラムが終了してしまったら，その人は驚いてしまうことでしょう．3番目のアプローチは最も汎用的ではありますが，少々難しいし，そこまでやる必要はないかもしれません．ここでは２番目のアプローチに沿って，プログラムを修正してみることにしましょう．

以下のように，argsの長さをチェックして，2以外ならユーザに対してエラーメッセージを出して終了させるのが簡単です．

public class GCD {
    public static void main(String[] args) {
        if (args.length != 2) {
            System.out.println("入力パラメータの数は２つでなければなりません");
            return;
        }
        // 入力された文字列を整数に変換する
        ...

return文は，メソッドの実行を途中で終了し，メソッドの呼び出し元に処理を戻す命令です．mainメソッドの中でreturn文が実行されると，プログラムが終了します．

これで，少しだけプログラムが親切になりました．

$ java GCD 60
入力パラメータの数は２つでなければなりません

でも，まだ問題が残っています．以下のように数値ではない入力を与えたらどうなるでしょう？

$ java GCD foo bar

筆者の環境では，以下のような例外が発生しました．

Exception in thread "main" java.lang.NumberFormatException: For input string: "foo"
        at java.lang.NumberFormatException.forInputString(NumberFormatException.java:66)
        at java.lang.Integer.parseInt(Integer.java:485)
        at java.lang.Integer.parseInt(Integer.java:520)
        at GCD.main(GCD.java:11)

これは，Integer.parseInt(args[0])の処理に失敗して，NumberFormatExceptionという例外が発生したことを示しています．つまり，fooという文字列は整数値に変換できませんでした，ということです．

ここでは，発生した例外をキャッチしてやることで，この問題に対応することにしましょう．そのためにはtry〜catch構文を用います．

public class GCD {
    public static void main(String[] args) {
        ...
        // 入力された文字列を整数に変換する
        int p, q;
        try {
            p = Integer.parseInt(args[0]);
            q = Integer.parseInt(args[1]);
        } catch (NumberFormatException e) {
            System.out.println("入力された文字列を整数に変換できません");
            return;
        }
        int d = Math.min(p, q);
        ...

tryの{と}で囲まれた文の中で何らか例外が発生した場合，その例外とマッチするcatch節の部分に実行が移ります．ここでは，NumberFormatException例外が発生した場合に，catch (NumberFormatException e) {以下の処理に実行が移ることになります．これが例外のキャッチです．
実行結果は以下のようになります．

$ java GCD foo bar
入力された文字列を整数に変換できません

このように，いろいろな入力ケースに対して，プログラムがきちんと動作するようにするには，適切に例外をキャッチしてやることが必要です．特に入出力を扱うような場合，外部の環境によってどのような値が渡されるか，プログラムを書いた時点では予想できないことがありますので，このような処理は堅牢なプログラムを作る上で重要になります．
# ライブラリのメソッドがどのような例外を返すかどうかは，ライブラリのリファレンスマニュアルに記載されています．

さて，これでどんな入力でも対応できるGCDプログラムが完成したのでしょうか？
実は，まだまだ想定していないケースがあります．たとえば，0の値や負の値をパラメータとして与えた場合です．
たとえば，5と0の最大公約数や，-12と30の最大公約数はどんな値になるのでしょうか？この問題に対処するには，そもそも，そういった数に対する最大公約数はどういった値にするべきなのか，といった仕様をきっちりと定義してやる必要があります．あるプログラムが正しいかどうかはそれだけでは判断できなくて，あくまでも仕様に対して，そのプログラムが正しいかどうか，といった相対的な判断しかできません．たとえば，さきほどのプログラムの仕様として，「引数は正整数のみとし，それ以外の入力が与えられた場合は未定義の値を出力する」というものだったらば，プログラムは正しいことになります．もし，0や負の値に対しても最大公約数を求めたいのであれば，まずは入力が負や0に対する妥当な仕様を策定し，それにしたがってプログラムを修正する必要があるのです．これについては，読者に対する課題とします．

いずれにしても，きちんとしたプログラムを書く，というのは実は大変なことだということがわかります．本職のプログラマたちも，単に動くだけのプログラムを書くのではなく，いろんな状況に対してもきちんと動作する，ことを常に心がけており，そのために日々格闘しているのです．
# 実はそれだけではありません．どうやったら，より柔軟性の高いプログラムになるか，拡張性が高くなるか，テストがしやすいか，実行効率が良くなるか，セキュリティが高くなるか，可読性が高くなるか，などなど，様々な観点からプログラムの品質を高める努力をしています．
# 本連載では，そのための考え方や手法について，折にふれて紹介していけたらと考えています．

Euclidの互除法による解

さて，前節では，どうやって堅牢なプログラムを作るか，といった観点から最大公約数のプログラムを改良していきましたが，最大公約数を求めるアルゴリズムについては，何も変更しませんでした．ここでは，別の観点として，最大公約数を求めるより賢いアルゴリズムを紹介したいと思います．

実は，最大公約数を求めるには，Euclidの互除法というアルゴリズムが古くからよく知られています．これは，２つの整数pとqがあり，rをpをqで割ったときの余りとしたときに，pとqの最大公約数とqとrの最大公約数は常に等しくなる，すなわち，GCD(p,q)=GCD(q,r)という関係を利用したアルゴリズムです．
この関係を使えば，64と28の最大公約数は以下のようにもとめることができます．

GCD(64,28) = GCD(28,8) // 64を28で割ったあまりは8
           = GCD(8, 4) // 28を8で割ったあまりは4
           = GCD(4, 0) = 4 // 8を4で割ったあまりは0，割り切れたので答えは4

この考え方を使って，GCDのプログラムを書くと次のようになります．

//
// Euclidの互除法によって最大公約数を求める
//
public class GCD {
    public static void main(String[] args) {
        // 入力された文字列を整数に変換する
        int p = Integer.parseInt(args[0]);
        int q = Integer.parseInt(args[1]);

        for (;;) {
            int r = p % q;
            if (r == 0) break;
            p = q;
            q = r;
        }
        System.out.printf("%sと%sの最大公約数は%dです\n", args[0], args[1], q);
    }
}

このアルゴリズムは，先に紹介した力任せによる手法よりもずっと早く解を見つけ出すことができます．
すなわち，力任せ法では，解の候補となる値を1つずつ減算して調べていったのにたいして，Euclidの互除法では，余りを求めながら（繰り返しの処理ごとにrの値はどんどん小さくなります）調べていってるので，より早く，解にたどりつくわけです．したがって，このアルゴリズムはさきほどのアルゴリズムよりも（処理速度の面から）効率が良い，といえます．

より本格的なプログラムを作成するために，プログラマは様々なアルゴリズムについて知っている必要があります．
# 大学の情報系学部で最初の学期に受ける講義はたいてい「アルゴリズムとデータ構造」というタイトルの授業で，プログラミングの基本となる様々なアルゴリズムや重要なデータ構造について学びます．
本連載では，折にふれて重要なアルゴリズムやデータ構造，なども紹介していく予定です．（ただし本格的には専門の教科書や参考書を使って勉強してください）
もちろん，典型的なアルゴリズムはライブラリとして実装されていることが多く，実際の開発においてプログラマが直接，これらのアルゴリズムを実装することはほとんどありませんが，アルゴリズムを多く学び，そのアイディアや概念を学ぶことによって，プログラミングの腕が上がるのは間違いありません．いろんな場面で応用がきくようになります．

# わたしが学生時代のアルゴリズムの先生は「よりアルゴリズムを見つけるには，問題の背後にある良い（数学的）構造を見つけることがポイントである」と常日頃からおっしゃってました．たとえば，GCDの例でいうと，GCD(p,q)=GCD(q,r)という良い構造に着目したおかげで，Euclidの互除法という効率良いアルゴリズムが得られたのです．
# すべての問題に対して，このように効率の良いアルゴリズムが存在するかというとそうではありません．たとえば，NP完全問題と呼ばれる範疇に含まれる問題は，本質的に力任せ法による解法しかないので，解くのに非常に時間がかかります．

まとめ

今回は，Javaによる繰り返し処理の構文の一つであるfor文と例外処理のさわりの部分，そして条件分岐と繰り返し処理の応用として，いくつかのアルゴリズムを紹介しました．（本当はもっといろんなのを紹介したかったのですが，力尽きました．．．）
繰り返しの構文はfor以外にもwhileなどがありますが，ここでは取り上げられませんでした．そのうち紹介します．
また，例外処理についての詳しい説明も，いずれ章をあらためて紹介することにします．