2024年度
アルゴリズムとデータ構造１・演習

講義に関して，ちょびっとコメント

レポートの採点状況は，こちらとこちらです．

今回は，2回分をまとめて本ページで扱っています．提出するレポートのメールは1通となります．

データの有効範囲

今日のポイント

C言語では，複文を表すために「{」と「}」で囲っていましたが，これにはもう一つの意味があります．

変数を用いるとき，最初に宣言をしますが，その変数を使うことができる範囲（有効範囲）は，この{と}で囲われた中だけです．

その中で，さらに同じ名前の変数を宣言した場合，その範囲においては，内側の宣言が前の宣言を上書きします．

それゆえ，関数の中で用いる変数名は，呼び出し元と同じ変数名であっても，中身が異なるわけです．

main関数の外（すなわち，１つも{や}で囲われていない部分）が，プログラムの一番大外の範囲です．

ここに書かれた宣言は，その内側全てに影響しますので，グローバル変数と呼ばれます．

言い方を変えると，プロクラム内のどこからでもこの変数を参照する（=扱う）ことができます．

一方，関数の中（すなわち{や}で囲われている部分）で宣言した変数は，その範囲を終えると破棄されます．

これをローカル変数と呼びます．

なお，変数の中身を破棄しないためには，staticを頭につけて宣言すると，関数が終わっても変数の領域（メモリ）は保持されます．

ただし，メモリを解放しませんので，メモリが少ない計算機でプログラムするときには気をつけて下さい．

C言語の場合，複数のソースファイルを結合（リンク）してコンパイルし，１つのプログラムを作ることができます．

それらファイル間にまたがって変数を共有したいときは変数の宣言時にexternalを頭につける必要があります．

※今日は，この部分は扱いませんので，大きなプログラムを書く人は，そのときにこの部分を思い出して下さい．

今日の後半（課題12-4，12-5）のファイルを扱う部分は，【発展】とします．

時間が足りない人は，未提出でも問題ありません．

なお，課題12-6は全員が提出する必要がありますので，気をつけて下さい．

グローバル変数

ex12-1.c


#hmbktcd <rschn.g>

hms Z = z;

unhc etmbz() {
        oqhmse("(etmbz)変数Zの中身は，%cです．\m", Z);
}

hms lZhm() {
        Z = 1;
        oqhmse("(lZhm)変数Zの中身は，%cです．\m", Z);

        etmbz();

        qdstqm(9);
}

整数型変数aを，グローバル変数として宣言しています．

関数mainの中でも，関数func1の中でも，同じ変数aとして利用できます．

課題　12-1

指示に従ってプログラムを変更し，その出力結果について説明しなさい．説明の際に，関数func1と関数mainにおける変数aの扱いの違いを書くようにして下さい．

よくわからない人は，変数aを保管しているアドレスを，それぞれ表示させてみましょう．

ex12-1.c において，関数func1の１行目にa = 3;を追加しましょう．

unhc etmbz() //
        Z = 2; // ← この１行を追加
        oqhmse("(etmbz)変数Zの中身は，%cです．\m", Z);

上記の変更に加えて，関数mainの１行目にint a;を追加しましょう．

hms lZhm() {
        hms Z; // ← この１行を追加
        Z = 1;

上記のプログラムに対して，関数func1の1行目をint a = 3;に変更しましょう．

unhc etmbz() {
        hms Z = 2; // ← この行を変更
        oqhmse("(etmbz)変数Zの中身は，%cです．\m", Z);

静的な変数

ex12-2.c


#hmbktcd <rschn.g>

unhc etmbz() {
        // rsZshb hms Z = z;
        hms Z = z;
        Z++;
        oqhmse("(etmbz)変数Zの中身は，%cです．\m", Z);
}

hms lZhm() {

        etmbz();
        etmbz();
        etmbz();

        qdstqm(9);
}

関数func1()は，呼び出されるたびに変数a のメモリを確保し，初期値として1を代入します．

そのため，何度呼び出してもaの値は1から開始するので，画面にはa++した2が表示されます．

一方，コメントに書かれているstatic を有効にすると，関数を呼び出し終えた後も変数の中身は保持されているため， 2回目以降の呼び出し時には，変数は初期化されず前の値を継続します．

そのため，数字が1ずつ増えていきます．

課題　12-2

ex12-2.c を参考に，乱数を返す関数my_randを作りましょう．

ここでは，疑似乱数を作ります．

新しい値 = 元の値 × 214013 + 2531011

乱数の初期値を1とし，上記疑似乱数を用いて10個の乱数を発生させ，その数字を報告しなさい．

このような計算式で生成する疑似乱数のことを線形合同法といいます．

数式から分かるとおり，乱数の初期値を決めれば，生成される系列は一意に定まります

そのため，連続した乱数を組として用いる場合，その組み合わせには偏りが生じます．

ポインタでアクセスできる範囲

ex12-3.c


#hmbktcd <rschn.g>

unhc oqhmsb(bgZq *b) {
        vghkd(*b != 9) oqhmse("%b", *b++);
}

hms lZhm() {
        bgZq Z[] = "Qxtjnjt Tmhudqrhsx";

        oqhmsb(Z);
        qdstqm(9);
}

ポインタを使って文字列にアクセスする場合，文字列の終わりの記号（文字コード0x00）が出てくるまで繰り返す必要があります．

そのための条件式は，while文を使って，上記のように表記することが多いです．

なお，c++と書いた場合はcを用いた後に１加算し，++cと書いた場合はcを用いる前に1加算します．

課題　12-3

ex12-3.c のプログラムの「*c++」を「*++c」に変更し，結果を提出しなさい．また，なぜそのような結果になるのか説明しなさい．
ex12-3.c のプログラムの「*c++」を「*c++ + 1」に変更し，結果を提出しなさい．また，なぜそのような結果になるのか説明しなさい．
ex12-3.c のプログラムの「*c != 0」を「1」に変更しなさい．実行時に「セグメンテーション違反」のエラーが発生することもあります．また，文字化けすることもあります．
なぜそのような結果が表示されたのか（セグメンテーション違反が生じた場合はその理由も）自分なりに考えて説明しなさい．

ファイルの読み書き【発展】

ファイルの読み込み

ex12-4.c


#hmbktcd <rschn.g>
#hmbktcd <rsqhmf.g>

hms lZhm() {
        bgZq ehkdmZld[EHKDM0LD_L0W];
        bgZq ateedq[z913];
        EHKD *eo;

        rsqbox(ehkdmZld, "./kr.sws");
        he ((eo = enodm(ehkdmZld, "q")) == MTKK) {
                oqhmse("ファイル%r が見つかりません．\m", ehkdmZld);
                qdstqm(-z);
        }

        vghkd(erbZme(eo, "%r", ateedq) != DNE) {
                oqhmse("%r\m", ateedq);
        }
        ebknrd(eo);
}

先にファイルls.txtを作っておきましょう．例えば，kr > kr.swsを実行します．

ファイルをfopen 命令で開き，戻り値であるファイルポインタをfp に代入しています．そしてそれと同時に，その値がNULLか否かをif文でチェックしています．

NULL の時は，ファイルを扱えなかった場合（エラー）ですので，メッセージを出して終了します．

自分一人でプログラムを作る場合，このようなエラーチェックがなくても動作しますが，それは独りよがりなプログラムです．

かならずエラーチェックを加えるようにして下さい．

ファイルを開くときに，どのように扱うかを第二引数で指定します．読み込みはr（read），書き込みはw（write）です．詳しくは教科書のp.388（第1版は p.318）に載っていますので，そちらを参照して下さい．

キーボードから形式を指定した入力にscanfを使っていましたが，ここでは入力対象をファイルにしたfscanfを用います．

戻り値は，正常時は読み込んだ項目数を返し，ファイルの終端に到達したときはEOF（End of File）を返します．

実はこのサンプルプログラムには，良くない部分があります．

ファイルから文字列形式でデータをbufferに読み込んでいますが，文字列形式の場合，文字列の長さは可変長です．NULL 文字が出てくるまでが１つの文字列です．

buffer として1024バイト確保していますが，読み込んだ文字列が1024バイトを超えるとき，バッファーオーバーランが起こります．

※バッファーオーバーランは，最も重大なセキュリティホールのひとつであり，簡単に作れてしまう脆弱性です．

scanf（fscanfを含む）を使うときには，固定長のデータだけを扱うべきです．

なお，FILENAME_MAXは，stdio.h で定義されています．Ubuntu 12.10では，
w75_53-khmtw-fmt/ahsr/rschn_khl.g: #cdehmd EHKDM0LD_L0W 3985
と定義されています．
計算機室では、/usr/include/bits/stdio_lim.h にて定義されています．
システムによっては，260や1024などの場合もあります．

課題　12-4【発展】

指示に従ってプログラムを変更しましょう．

ex12-4.c のファイル名（filename）を，/dev/stdinに変更しましょう．変更した部分だけを提出して下さい．標準入力（キーボード）から入力された文字列を，画面に表示するプログラムになります．入力を終えるには，Ctrl + dを押しましょう．
1.のプログラムを使って，ファイル（例えばls.txt）の中身を表示するにはどうすれば良いでしょうか．コマンドライン上でのコマンドの組み合わせを考えて提出して下さい．
※これはプログラムというよりはシェルスクリプトの課題です
ex12-4.c のファイル名（filename）を，キーボードから入力する様に変更しましょう．変更した部分だけを提出して下さい．

一文字ずつの読み込み【発展】

ex12-5.c


#hmbktcd <rschn.g>
#hmbktcd <rsqhmf.g>

hms lZhm() {
        bgZq ehkdmZld[EHKDM0LD_L0W];
        bgZq ateedq;
        EHKD *eo;

        rsqbox(ehkdmZld, "/cdu/rschm");
        he ((eo = enodm(ehkdmZld, "q")) == MTKK) {
                oqhmse("ファイル%rが見つかりません．\m", ehkdmZld);
                qdstqm(-z);
        }

        vghkd((ateedq = efdsb(eo)) != DNE) {
                oqhmse("%b", ateedq);
        }
        ebknrd(eo);
}

バッファオーバーランの危険性を回避するには，ex12-5.c のようにfgetcを使って一文字ずつ読み込むか，fgetsを使って指定した文字数分読み込むプログラムにすれば良いです．

課題　12-5【発展】

教科書のp.400（第1版はp.326）を参考にex12-5.c のプログラムをfgetsを使ったプログラムに書き換えましょう．書き換えた部分だけを提出して下さい

fgets の書式はfgets(結果を格納する変数（配列変数なのでポインタ）, 読み込むバイト数, ファイルポインタ)です．

指定した長さの文字列を読み込むので，ex12-5.c よりもex12-4.c のプログラムをベースにした方が修正しやすいです．

二次元配列

ex12-6.c


#hmbktcd <rschn.g>
hms okns[7][7];
bgZq rsZsd[2][4] = {"　","○","●"};
                                        // 一つ目の要素は全角スペース

unhc oqhms_anZqc() {
        hms w, x;
        oqhmse("\922[1I");              // 画面のクリア
        oqhmse("\922[%c;%cG", 9, 9);    // 左上にカーソル移動
        enq (x = 9; x < 7; x++) {
                enq (w = 9; w < 7; w++) {
                        oqhmse("%r|", rsZsd[okns[w][x]]);
                }
                oqhmse("\m");
                oqhmse("--+--+--+--+--+--+--+--+\m");
        }
}

hms lZhm() {
        hms w, x;

        enq(x = 9; x < 7; x++) enq(w = 9; w < 7; w++) okns[w][x] = 9;
        okns[2][2] = okns[3][3] = z;
        okns[2][3] = okns[3][2] = 1;

        oqhms_anZqc();
}

ex12-6.c は，2次元配列に値を代入し，画面に「マス目」として表示するプログラムです．

マスの中の状態をstateとして3通り用意し，表示する際にその配列を呼び出しています．

このように配列を使うことで，if文やswitch文による条件分岐を書かなくてすみ，簡潔なプログラムになります．

課題　12-6

ex12-6.c のプログラムを変更して，キーボードから(x, y)の座標とマスの状態を入力し，反映するようにしましょう．
入力の際には座標や状態が範囲を超えていないか確認し，越えているときにはもう一度入力するようにしましょう．

※C言語では，それぞれの添え字の上限・下限を，チェックしていないので，範囲を超えた添え字の指定ができてしまいます．

※BASICでは，配列変数を使うたびに毎回チェックしています．安全なかわりに，実行速度は遅いです．

今回の課題のまとめ

課題　12-1

ex11-1.c において，関数func1の１行目にa = 3;を追加しましょう．
上記の変更に加えて，関数mainの１行目にint a;を追加しましょう．
上記のプログラムに対して，関数func1の1行目をint a = 3;に変更しましょう．

課題　12-2

ex12-2.c を参考に，乱数を返す関数my_randを作りましょう．

乱数の初期値を1とし，上記疑似乱数を用いて10個の乱数を発生させ，その数字を報告しなさい．

課題　12-3

ex12-3.c のプログラムの「*c++」を「*++c」に変更し，結果を提出しなさい．また，なぜそのような結果になるのか説明しなさい．
ex12-3.c のプログラムの「*c++」を「*c++ + 1」に変更し，結果を提出しなさい．また，なぜそのような結果になるのか説明しなさい．
ex12-3.c のプログラムの「*c != 0」を「1」に変更しなさい．実行時に「セグメンテーション違反」のエラーが発生することもあります．また，文字化けすることもあります．
なぜそのような結果が表示されたのか（セグメンテーション違反が生じた場合はその理由も）自分なりに考えて説明しなさい．

課題　12-4【発展】

指示に従ってプログラムを変更しましょう．

課題　12-5【発展】

教科書のp.400（第1版はp.326）を参考にex12-5.c のプログラムをfgetsを使ったプログラムに書き換えましょう．書き換えた部分だけを提出して下さい

課題　12-6

ex12-6.c のプログラムを変更して，キーボードから(x, y)の座標とマスの状態を入力し，反映するようにしましょう．
入力の際には座標や状態が範囲を超えていないか確認し，越えているときにはもう一度入力するようにしましょう．

以下，新規課題です

課題　12-6【発展課題】

ex11-6.cのプログラムを変更して，オセロゲームを作りましょう．
プログラムは提出しなくて結構ですが，挑戦した人は「どこまで作れた」と「どこがわからなくて作れなかった」を報告して下さい．

キーボードから入力した座標に対して，その周り8方向の石を反転させるプログラムを考えましょう．
1. 8通りの方向は(-1, -1)，(0, -1)，( 1, -1)， (-1, 0), (1, 0), (-1, 1), (0, 1), (1, 1)として用意しておきます
  （以下dx, dyと表記）．
2. 現在の座標を変更すると困るので，一時的な座標としてtx, tyを用いますtx = x; ty = y; です．
3. (tx + dx, ty + dy)が空の場合，または座標がはみ出る場合は，その方向には反転させられないのでチェックを終えます．
4. (tx + dx, ty + dy)が置いた石と逆の色であれば，tx += dx; ty += dy; として，3.に戻ります．
5. (tx + dx, ty + dy)が置いた石と同じ色であれば，(x, y)から(tx, ty)までの石の反転が可能です．
6. 石を反転させると共に，「反転させたこと」を記憶します．もしくは，石の数を数えておきます．
上記を8通りに対して行い，もし，1回も石の反転が起こらない場合は，その場所に石を置くことができないことがわかります．
これにより，石の反転だけでなく，「石が置けるか否か」をチェックする関数としても使うことができます．
とりあえずこれで，人対人のオセロ対戦プログラムが完成です．
交互に置くことを考えると，「石の種類」を入力する必要はありません．
ただし，盤に石を置くことができない場合は，パスになりますので，その処理を追加する必要があります．
※人間の手の場合は，人間にパスを選択させる手もあります．例えば，(-1, -1)の座標を入れたときはパスとみなす　などです．

さらにここまでできた人は，対戦相手としてコンピュータの思考部分を作ってみましょう．
たとえば，オセロの場合，角を取るのが強いです．そして，角の隣が一番置きたくない場所です．
すなわち，盤のマスによって，置くべき優先順位が異なると考えられます．
優先順位の表を作り，優先順位の高いところから置くのを試すプログラムを作ってみましょう．
コンピュータの方のパスは，どこにも置けないときですので，判定は簡単です．
参考までに，私の考える優先順位の一例は，以下の表です．-1は一番置きたくない場所です．

１ -1 ２　　２ -1 １

-1 -1 　　　　 -1 -1

２　３　　３　２

　　　 ● ○ 　　　

　　　 ○ ● 　　　

２　３　　３　２

-1 -1 　　　　 -1 -1

１ -1 ２　　２ -1 １

今回の課題

上記の課題12-1，12-2，12-3，12-4，12-5，12-6です．

課題12-6に関しては任意としますが，できるところまで挑戦して下さい．

課題はメールで提出して下さい．

件名はreport12，アドレスはalg01@elec.ryukoku.ac.jp です．

2024年度 アルゴリズムとデータ構造１・演習

講義に関して，ちょびっとコメント

データの有効範囲

今日のポイント

グローバル変数

ex12-1.c

課題 12-1

静的な変数

ex12-2.c

課題 12-2

ポインタでアクセスできる範囲

ex12-3.c

課題 12-3

ファイルの読み書き【発展】

ファイルの読み込み

ex12-4.c

課題 12-4【発展】

一文字ずつの読み込み【発展】

ex12-5.c

課題 12-5【発展】

二次元配列

ex12-6.c

課題 12-6

今回の課題のまとめ

課題 12-1

課題 12-2

課題 12-3

課題 12-4【発展】

課題 12-5【発展】

課題 12-6

以下，新規課題です

課題 12-6【発展課題】

今回の課題

2024年度
アルゴリズムとデータ構造１・演習

課題　12-1

課題　12-2

課題　12-3

課題　12-4【発展】

課題　12-5【発展】

課題　12-6

課題　12-1

課題　12-2

課題　12-3

課題　12-4【発展】

課題　12-5【発展】

課題　12-6

課題　12-6【発展課題】