2009 年度「計算数学1」 2009-05-25

§58 ソートのまとめ

(58.1) 以上で、「計算機基礎論3B」から続いてきた、 ソートのプログラムの学習は終わりとする。

(58.2) 興味のある人は、取り上げたうちの、 計算量が Ο(N log(N)) のアルゴリズム --- ヒープソート、クイックソート、マージソート --- について、配列の大きさ N をさらにいろいろな値に変えて実験し、 N を大きくするとき N log(N) の定数倍に近づいてゆくかどうかを調べ、 もしそうなっていたら、その定数の値はいくつになるか、 求めてみてほしい。 それが小さいほど、速いアルゴリズムということになる。 そのほか、この三つのアルゴリズムにはそれぞれ長所・短所がある。 まとめてみるとよいだろう。

(58.3) ソートのような、問題の意味を理解するだけなら簡単な問題にも、 いろいろな解法があり、 工夫次第でスピードを上げることができる。 先人たちの研究結果を学ぶことの大切さを知ってほしい。

(58.4) また、いくら努力してもこえられない理論上の限界 (§46) がある、 ということを理解するのも大切である。

(58.5) 数学では、可能な操作は一瞬で終わったとして先へ進む。 たとえば、 「この行列の固有値を小さい順に並べて λ1 < λ2 < ... < λn とします」 のように。 このあたりの、ものの考え方の違いについても考えてみてほしい。

§59 乱数を利用したプログラム

(59.1) 乱数を利用したプログラム例として、 ランダムウォーク randomwalk.c と一人で遊ぶポーカー poker.c を用意した。 いずれも、いままで習ったC言語の知識で理解できるように書いてある。 ソースファイルを読んで、自分流に変えられる部分は変えるなどしてみよ。

§60 画面制御エスケープシーケンス

(60.1) いままで、画面出力は GNOME 端末の中に、下へ下へと書かれてゆくだけだった。 「画面制御エスケープシーケンス」を使うと、それをさまざまに変化させることができる。

(60.2) それは、この実習室の linux の GNOME 端末が以下でのべる画面制御エスケープシーケンスに対応しているからである。 すべての端末が、対応しているわけではない。 以下のプログラムはすべての C コンパイラを通ると思うが、 端末によっては、以下で述べるような動作をしないこともある。

(60.3) 画面制御エスケープシーケンスとは、 「\033」で始まる決まった文字列である。 これを画面に出力することで、画面を制御する。 いままで習ってきた範囲の知識で使うには、 必ず printf() で画面に出力することになるので、 以下ではその形で示す。 なお、「\033」は、 「\n」がこの二文字で改行という一文字を表したように、 これで一文字を表している。(詳細は K&R2 を参照。)

(60.4) GNOME 端末の上で、「次に出力されるのはここです」を示すために出ている黒い長方形を、 「カーソル」と呼ぶ。

(60.5) 画面を消すコマンドは「clear」である。 プロンプトの出ているところにこれを打ち込むと、 画面の文字がすべて消え、左上のすみに新しくプロンプトが出た状態になる。 これを、「画面をクリアする」ということもある。 以下を利用したプログラムを書いていると、 画面のあちこちにいろいろなものが出力され、わけがわからなくなることがある。 そのときはこれを使うとよい。

(60.6) 以下に、画面の全部または一部のクリア、 カーソル移動に関する画面制御エスケープシーケンスのうちの、いくつかをあげる。

printf("\033[0J");            /* カーソル位置から画面の右下すみまでを削除。0 は省略可 */
printf("\033[2J");            /* 画面全体のクリア。カーソルは左上すみには戻らない(ようだ)*/
printf("\033[K");             /* カーソル位置から行末までを削除 */
printf("\033[%d;%dH", x, y);  /* カーソルを第 x 行、第 y カラムへ移動(左上が (1,1))*/
注意:ここでは並べて示したが、このように並べて順に実行してもおそらく意味はない。 また、x, yint 型変数である。 三つめのカーソル移動は、
printf("\033[1;3H");          /* カーソルを第 1 行、第 3 カラムへ移動 */

のように、文字列の中に直接、整数を書き込んでしまってもよい。

(60.7) 次の例は、(1, 1), (2, 4), (3, 9), ... (9, 81) にカーソルを移動してから hello, world と出力するだけの、サンプルプログラムである。

#include <stdio.h>

main () {
    int i;

    for (i = 1; i < 10; i++) {
        printf("\033[%d;%dHhello, world", i, i*i);
    }
}
画面制御エスケープシーケンスと、出力させたい文とを、 この例のように続けて書いてもよい。 どうせすぐ別の行に移るからと、最後の \n を抜かしているので、 (この実習室の linux で)このプログラムを動かすと、 終了後、行の途中にプロンプトが出る。 (画面が乱れた場合は上述のように clear を実行せよ。)

(60.8) 次は、「行末まで削除」を試すもの。

#include <stdio.h>

main () {
    int i;

    printf("\033[10;1Hhello, world\n");         /* (10, 1) に移動して出力 */
    printf("1 から 12 までの好きな数を");
    printf("入れて Enter を押してください.\n");
    scanf("%d", &i);                            /* 一旦停止して入力を待つ */
    printf("\033[10;%dH", i);                   /* (10, i) に移動 */
    printf("\033[K");                           /* 行末まで削除 */
    printf("\n");
}

(60.9) 文字の色を変えることもできる。 なお、多くの人に使ってもらうプログラムを作る場合には、 色の見え方が他の大多数の人とは異なる人のことを忘れないように。

(60.10) GNOME 端末そのものを、白黒反転させて使うことができる。 「編集」「現在のプロファイル」「色」と進み、 「内蔵型スキーム」を「白地に黒文字」から「黒地に白文字」に変えてみよ。

(60.11) 色のほかに、反転文字なども使えるので、まとめて「属性」と呼ぼう。 文字の属性を変える画面制御エスケープシーケンスを printf() とともに示すと、

printf("\033[%dm", i);
となる。iint 型変数である。 その値によって、どのような属性に移るかが決まる。 あるいは、
printf("\033[35m");
のように、文字列の中に直接、整数を書き込んでしまってもよい。 センターの GNOME 端末の場合、0 から 127 以外は意味がないようである。 デフォルトの属性に戻すには
printf("\033[m");
とする。 なお、「\n」で改行する前にはデフォルトに戻すほうがよいようである。 (端末によっては、 反転文字のまま改行すると画面上の行末まで地に色がついてしまったように思う。)

(60.12) i がいくつのときどうなるかは、次のプログラムを動かして試す。

#include <stdio.h>

main () {
    int i;

    for (i = 0; i < 128; i++) {
        printf("\033[%dm", i);  /* i 番の属性に */
        printf("[%03d]", i);    /* その i を出力 */
        printf("\033[m");       /* デフォルトに戻す */
        if (i % 16 == 15) {     /* 16 ごとに改行 */            
            printf("\n");
        } else {
            printf("  ");
        }
    }
}
一つの番号を試したあと、すぐ「デフォルトに戻す」のは、 端末によって、あるいは番号によっては、前の属性が残ったまま、 そこに新しい属性が加えられてゆくことがあるからである。 上の「デフォルトに戻す」を抜かすとどうなるか、試してみよ。 ((60.11) の終わり近くに書いたことと合わせると、属性を変えて文字列を出力したら、 即座にデフォルトに戻すよう心がけるのが無難、ということになる。)

(60.13) 数と属性の関係について、センターの linux の GNOME 端末で、 私が試して観察した結果を以下に述べる。 (あくまでも、私の観察に基づくものである。正式なものではない。)

効果
1太字(強調?)
2薄字(?)
4下線つき
7反転(字と地の)
8隠し?(見えない)
9打ち消し線つき

38 も下線つきになるようだが、よくわからない。

30 番台、40 番台、90 番台、100 番台は、一位が色を、十位(と百位)がその他の属性を表し、 その組み合わせとなる。 反転と書いたのは、地がその色になり、 その上に文字がデフォルトの色で表示される、ということである。

サンプル参考
0  
1  
2  
3 赤+緑
4  
5マゼンタ(紫に似る) 赤   +青
6シアン(水色に似る)    緑+青
7 赤+青+緑
     
効果
30暗い色
40暗い色、反転
90明るい色
100明るい色、反転

(60.14) 次のように、[m の間に、 ; で区切って複数の数を書くこともできる。 その場合、それらの属性をあわせもつようになるようである。

#include <stdio.h>

main () {
    int i;

    for (i = 0; i < 128; i++) {
        printf("\033[91;%dm", i);   /* 91 番と i 番の属性に */
        printf("[%03d]", i);        /* その i を出力 */
        printf("\033[m");           /* デフォルトに戻す */
        if (i % 16 == 15) {         /* 16 ごとに改行 */            
            printf("\n");
        } else {
            printf("  ");
        }
    }
}

(60.15) カーソル移動の簡単な応用となる、二次元ランダムウォークのプログラム randomwalk2.c を用意した。コメントを読みつつ、考えてみてほしい。 また、§59 で述べたポーカーのプログラムは、出力に色をつけたり、 カードの出力される位置が一定になるよう改造したりできるだろう。 さらに、スート(マーク)やランク(数)を、「#」を縦横に並べて

 ## ##       #
#######     # #
 #####     #####
   #      #     #
のように大きく表示させることができるだろうか? (実際には縦横の文字数はもっと多くてよい。)

(60.16) randomwalk2.c の中で使った、 関数 fflush() について説明する。このプログラムは、 printf() で画面にキャラクタを出力し、 少し止まる。それからそれを消し、次の位置にキャラクタを書く。 これをくり返す。 すると、ユーザには画面上をキャラクタが動き回っているように見える、 というものである。 しかし、printf() が実行されても、すぐに画面に出力されるとは限らない。 効率をあげるため、出力するものを少しためてから、 まとめて画面に書くようにできているためである。 そのため、時間かせぎの空ループの直前で「fflush(stdout);」を実行しないと、 期待したとおりに動かない。 (stdout は、普通は画面を意味するが、ここでは全体で決まり文句と考ればよい。)

(60.17) 興味のある者は、randomwalk2.c を、次のように改造してみよ。

注意:実際の酔人の動きを観察するためなどと称して、大量の飲酒をするのは避けること。

§61 センターの linux の“裏”端末

(61.1) センターの linux の、あまり知られていない、“裏”端末を紹介する。

(61.2) Ctrl+Alt+F1 で“裏”端末に表示が切り替わる。 ログインプロンプトが出ているので、 この実習用アカウントのアカウント名・パスワードでログインする。 プロンプトの出ているところで Ctrl+D を押せばログアウトできる。 ログインしたままで次に述べるように“表”に戻ることもできるが、 シャットダウンする前には、“裏”端末のほうはログアウトしておくほうがよい。

(61.3) “表”に表示を戻すのは、Ctrl+Alt+F7 である。

(61.4) linux を使っていて画面全体がまったく動かなくなってしまった場合、 この“裏”端末からログインして、 ある方法で正常に戻すことができる場合がある。 (具体的には、 悪さをしているプロセスを kill することになる。)

(61.5) “裏”端末は、§60 で述べた画面制御エスケープシーケンスが、 やや違う意味で解釈されるようである。 試してみると、よい体験になるだろう。

§62 多重配列

(62.1) 次の宣言で、3 × 5 の配列が使えるようになる。 つまり、a[0][0] から a[2][4] までが使えるようになる。

    int a[3][5];

§63 「トランプを切る」にあたる操作

(63.1) 配列を int a[N]; と宣言すれば a[0] から a[N-1] までが使える。 これを初期化したあと、トランプを切るようにランダムにかき混ぜるには、

とすればよい。 乱数がよい乱数だと仮定すれば、 これですべての置換が均等に得られる。

(63.2) プログラムで書けば次のようになる。 関数 swap() は、ソートのときに作ったものである。

    for (i = N - 1; i > 0; i--) {
        swap(rand() % (i+1), i);
    }


岩瀬順一