プログラミング入門(金曜1・2限)講義資料(2008年後期)

プログラミング入門 第5回

アルゴリズム

今まで見てきたように,コンピュータに問題を解決させるためには,決まった手順が必要です.このような手順のことをアルゴリズム(algorithm, 日本語では算法)と言います.

アルゴリズムとは,ある目的を実現するために必要な手順のことで,手順の各段階で何を行うかが明確に述べられている必要があります.つまり,誰でもその手順に従えば同じ結果が得られるようなものでなければなりません.

アルゴリズムを特定のプログラミング言語で記述したものがプログラムです.

バグについて

プログラムを書くときに間違いは付き物です.プログラムの間違いをバグと呼びます.また,バグを取り除く作業をデバッグと呼びます.

バグには主に文法上のバグとアルゴリズムのバグの2通りあります.

文法上のバグは,ソースプログラムがプログラミング言語の文法に従っていないというミスで,コンパイラが報告します.

アルゴリズムのバグは,ある問題を解決するための方法そのものに間違いがあったというものです.プログラムはコンパイルできるけれども,実行すると変な結果になるというものです.一般に,こちらの方が深刻なバグと考えられます.

デバッグの方法

ソースプログラムの文法上のバグはコンパイラが報告するので,それをヒントに直します.複数の間違いが報告される場合がありますが,基本は「最初のバグを直す」です.

コンパイル・実行はできるものの,プログラムの挙動がおかしいという場合,ソースプログラムを良く見て中で何が起きているのかを追跡する必要があります.

追跡にはデバッガ(debugger)と呼ばれるデバッグ専用のプログラムを利用できる場合もありますが,基本は「画面に表示してみる」です.

怪しいとにらんだところに,System.out.println 等を追加して,変数の値を表示させてみましょう.ちゃんと自分が思った値になっていますか?

このような,デバッグのためにプログラムに画面出力を追加することは簡単でよく行われますので,困ったときにはまずやってみましょう.

また,実行中にエラーが起きることもあります.Javaでは,実行中のエラーは例外(Exception)という形で報告されます.この場合は,なぜ例外が発生したのかを突き止める必要があります.

段階的詳細化(再び)

ある程度複雑なプログラムを作成するとき,まず,問題をより小さい問題に分割して,それを組み合わせてプログラムを作成すると,すっきりとしたプログラムを作成することができます.

例: 自分が「手に持ったゴミをゴミ箱に捨てる」動作を考えます.これは以下のような「より小さい問題」に分割できるでしょう.

それぞれの項目もより詳細に記述できます.例えば,1は首を左から右に動かしながら,ゴミ箱を探す.なかったら,足を使って反対を向き.... というように詳細化できるでしょう.

さらに,「首を左から右に動かす」という処理も詳細化していくと,適切な筋肉を働かせるという処理になりそうですし,「筋肉を働かせる」という処理は「神経に電気信号を流す」という処理に詳細化できそうです.

プログラミングでも,これと同じようにやりたいことを段々詳細化して, コンピュータが実行可能な(つまりプログラミング言語で表現できる)処理にまで落していくことが必要です.

フラグの使用

キーボードから整数 n を入力し,n が素数か否かを判定するプログラム Prime を作ってみましょう.

nが素数ならば,nは 2 〜 (n-1) のどの数でも割り切れないことを利用します.

考え方: for文を使って,2から順番にチェックしていきます.どれかの数で割りきれたら,素数ではありません.つまり,2〜(n-1)の繰り返しの中で,割り切る数が存在したかどうかを覚えておく必要があります.

「割りきる数が存在したか」の結果は存在したか,存在しなかったの2通りしかありません.これを,例えばint型の変数を使って0か1かで表すこともできますが,Javaではこういうことを表すのに都合が良いboolean 型という基本型があります.boolean型の変数には,trueかfalseしか入れることができません.

実は,if文やwhile文等の条件に書いていた真偽式(a == 0 等)は,boolean型で結果を返すものだったのです.

このように,true か false かを覚えておくための変数のことを,プログラミングの世界ではフラグとかフラグ変数と呼び,非常によく使われます.


このファイルをダウンロード ■ UNIX用(EUC版) ■ Windows用(SJIS版)
(上のどちらかのリンクを右ボタンでクリックして「リンク先を名前をつけて保存」して下さい)

// 素数判定
public class Prime {
    public static void main(String[] args) {
        System.out.print("整数を入力して下さい: ");
        int n = Keyboard.intValue();

	// 素数かどうかを覚えておくフラグ変数.最初は true にしておき,
	// 割り切る数を見つけたら false にする
        boolean isprime = true;

	// 2〜(n-1)までの間に割りきる数があったら素数ではない
        for (int i = 2 ; i <= n - 1 ; i++) {
            if (n % i == 0) {		// 割りきれる?
		isprime = false;	// 素数ではなかった
		// 素数でないことがわかったので,これ以上繰り返しても無駄.
		break;
            }
        }

	// 結果の表示
	// 一度も割りきれなかったら,
	// isprime == true のままここに到達する!
        if (isprime) {
            System.out.println(n + "は素数です");
        } else {
            System.out.println(n + "は素数ではありません");
        }
    }
}


if (isprime) と書いているところに注目してください.isprime は trueかfalseが入っている(boolean型の)変数なので,このように書くことができます.

演習(フラグ)

実数値を5個入力して,それが昇順に並んでいる(つまり,小さいものから大きいものへ順番に並んでいる)ならば,「ソートされています」と表示し,そうでなければ「ソートされていません」と表示するプログラム FlagExercise を作ってください.

ソートされているかどうかを表すフラグを使用する.まずソートされていると仮定し,配列をチェックしてソートされていない場所を見つけたらフラグの値を修正する.Primeでのフラグの使い方を参考にすること.

if (x[0] <= x[1] && x[1] <= x[2] && ... ) は扱う数が増えたときに困るのでダメ.

演習(金種計算)

(段階的詳細化の練習)

金額(円)を入力すると,1万円札,5000円札,2000円札,1000円札,500円玉,100円玉,50円玉,10円玉,5円玉,1円玉,各何枚必要かを出力するプログラム Kinshu を作ってください.

金額: 18324
10000: 1枚
5000: 1枚
2000: 1枚
1000: 1枚
500: 0枚
100: 3枚
10: 2枚
5: 0枚
1: 4枚

まず,大まかに何をすればいいのかを段階を追って書いてみること(日本語で).

その記述をだんだん詳細化していき,Javaですぐに書けるという段階にまでなったらコーディング(プログラムを書くこと)を開始すれば良い.

並べ替え(ソート)

10個の値が int 型の配列 x[0] 〜 x[9] に入っているときに,それを小さい順番に並べ替えたい.というような問題をやってみましょう.このように,小さい順(あるいは大きい順)に並べ替えることをソートあるいはソーティングといいます.

ソートの方法は昔から研究されていて,様々なやり方があります.ここでは,簡単に理解できるバブルソートという方法を紹介します.

バブルソートの考え方

    1. x[0]とx[1]を比較し,x[0] > x[1] ならば x[0] と x[1] の中身を入れ替える.
    2. x[1]とx[2]を比較し,x[1] > x[2] ならば x[1] と x[2] の中身を入れ替える.
    3. . . .
    4. x[8]とx[9]を比較し,x[8] > x[9] ならば x[8] と x[9] の中身を入れ替える.

    この操作によって,x[9]はx[0]〜x[9]の中で最大になる.(x[9]を確定)

    さらに,この操作を続けていく.

    1. x[0]とx[1]を比較し,x[0] > x[1] ならば x[0] と x[1] の中身を入れ替える.
    2. x[1]とx[2]を比較し,x[1] > x[2] ならば x[1] と x[2] の中身を入れ替える.
    3. . . .
    4. x[7]とx[8]を比較し,x[7] > x[8] ならば x[7] と x[8] の中身を入れ替える.

    この操作によって,x[8]はx[0]〜x[8]の中で最大になる.(x[8]を確定)

    1. x[0]とx[1]を比較し,x[0] > x[1] ならば x[0] と x[1] の中身を入れ替える.
    2. x[1]とx[2]を比較し,x[1] > x[2] ならば x[1] と x[2] の中身を入れ替える.
    3. . . .
    4. x[6]とx[7]を比較し,x[6] > x[7] ならば x[6] と x[7] の中身を入れ替える.

      この操作によって,x[7]はx[0]〜x[7]の中で最大になる.(x[7]を確定)

この操作を繰り返していくことで,最終的に配列xを小さい順に並べ替えることができる.

この方法がバブルソートと言われるのは,最大値が泡のように浮かんでくるからのようです.

まず,このアルゴリズムで本当にソートできるのか,紙の上で確かめて見ましょう.

次に,バブルソートをプログラムにしてみましょう.

x[0]とx[1]を比較し,x[0] > x[1] ならば x[0] と x[1] の中身を入れ替える.
x[1]とx[2]を比較し,x[1] > x[2] ならば x[1] と x[2] の中身を入れ替える.
. . .
x[8]とx[9]を比較し,x[8] > x[9] ならば x[8] と x[9] の中身を入れ替える.

の部分(最大値を寄せる処理と呼びます)は繰り返し処理なのでfor文(あるいはwhile文)で書けるでしょう.

また,最大値を寄せる処理自体も9回(配列の要素数-1回)繰り返すので,これもfor文(あるいはwhile文)で書けます.

これをまとめると,大まかなプログラムの構造は以下のようになるでしょう.

// 最大値を寄せる処理を繰り返す
for (...) {
    // 最大値を寄せる処理
    for (...) {
        x[?]とx[?+1]を比較し,x[?] > x[?+1] ならば x[?] と x[?+1] の中身を入れ替える.
    }
}

これをもう少し詳細化していきましょう(段階的詳細化).1回目の最大値を寄せる処理では,x[9]を確定し,次にx[8]を,と繰り返して,最後にはx[1]を確定します.そこで,変数 n で「今は x[n] を確定している最中である」ということを表すことにします.

x[9]の9というのは,配列xの添字の最大値ですから,x.length - 1 と表すことができます.9と書くより x.length - 1 と書いた方が,後から配列の大きさを変えたくなったときにいちいち変更しなくて済むので便利です.

// 最大値を寄せる処理を繰り返す
// 最初は x[9] を確定する.
for (n = x.length - 1 ; n >= 1 ; n--) {	// x[1] まで確定すれば終了
    // 最大値を寄せる処理 (x[n]を確定する)
    for (i = 0 ; i < n ; i++) {
        x[i]とx[i+1]を比較し,x[i] > x[i+1] ならば x[i] と x[i+1] の中身を入れ替える.
    }
}

x[i] と x[i+1] の中身を入れ替える処理は,以下のように書いては正常に動きません.(何故正常に動かないのか自分で考えて下さい)

   x[i] = x[i+1];
   x[i+1] = x[i]; 

こういうときは一時的に別の変数に待避させます.

   int temp = x[i];	// x[i] を temp に覚えておいて,
   x[i] = x[i + 1];	// x[i] に x[i + 1] を代入し
   x[i + 1] = temp;	// x[i + 1] は temp を代入

課題5-1 (バブルソート)

バブルソートのプログラム Sort を作ってください.

10個の数を入力して,小さい順にソートし,出力してください.

1. ソースプログラム,2. 実行結果,3. 苦労したところや改善すべき点,感想 を書くこと.