C言語プロジェクト演習課題　あみだくじ

windowsOS  coskx 20180301

１　あみだくじ概要とCプログラムでの表現
１．１　あみだくじ

あみだくじは10個の品物を10人で分ける際に，どの品物をだれに割り当てるかを決めるときなどに使われる。
10本の各縦棒の下に10個品物の名前を書き，縦棒の上に１０人の名前を書く。縦棒と縦棒の間に横棒を置きと横棒の両端にT字型の交点を作る。 このような横棒を複数本引く。ただし，交点は十字にならないようにする。 適当な本数の横棒が置けたところであみだくじが完成する。 各人がどの品物が当たったかを確定には，棒の上部から下方向に向かって縦棒をたどり，T字路にぶつかったら横棒に従って進み，再びT字路で縦棒にぶつかるので，そこから下向きに進む。 この作業を繰り返して，棒の下端にたどりつたところに書いてある品物がその人が獲得したしなものとなる。
図1.1.1 の例では０番君はＥが割り当てられ，１番君はＤが割り当てられている。

０　１　２　３　４　　　０　１　２　３　４
｜　｜　｜　｜　｜　　　｜□｜□｜□｜□｜　　　　　　　--- 第0行
｜－｜　｜－｜　｜　　　｜□｜□｜□｜□｜
｜　｜－｜　｜　｜　　　｜□｜□｜□｜□｜
｜－｜　｜　｜－｜　　　｜□｜□｜□｜□｜
｜　｜　｜－｜　｜　　　｜□｜□｜□｜□｜
｜　｜－｜　｜－｜　　　｜□｜□｜□｜□｜
｜－｜　｜－｜　｜　　　｜□｜□｜□｜□｜
｜　｜　｜　｜　｜　　　｜□｜□｜□｜□｜　　　　　　　--- 第7行
Ａ　Ｂ　Ｃ　Ｄ　Ｅ　　　Ａ　Ｂ　Ｃ　Ｄ　Ｅ

図1.1.1 あみだくじの例　　図1.1.2 □は横棒セルの位置を表す

手書きのあみだくじなら横棒の縦方向間隔は広いところや極端に狭いところを作ることができる。
プログラムで作成するとしたら，横棒は横棒セルにしか置けないことにする。 図1.1.1 のあみだくじでは横棒セルは横方向に４，縦方向に８並んでいるので，図1.1.2のように32個の横棒セルがあることになる。
ここでは，図1.1.1のように一番上の行（第0行）と一番下の行（第7行）には，横棒を置かないルールにしよう。

１．２　あみだくじの演習課題

ここで行うあみだくじの演習はつぎのような手順になる。
(1)既存のあみだくじの内部表現をあみだくじらしく表示する
(2)横棒なしの横棒セルだけでできた空白あみだくじを作る
(3)あみだくじ中の指定した横棒セルに，設置の可否判断をして横棒を設置する
(4)指定した本数の横棒を空白あみだくじにランダムに配置してあみだくじを完成する
(5)あみだくじで，指定した縦棒について，下方向にトレースした解を求める
(6)あみだくじで，指定した縦棒についての下方向トレースを可視化する

図1.1.1，図1.1.2は説明用の横棒セルのイメージであった。「｜」を縦棒セルと呼ぼう。 プログラムを作成するときは，プログラミングの便利さを考えて，両側に横棒セルを増やして，図1.2.1のように表現しよう。 （手順(3)からありがたみがわかる。）ただし，図1.2.2のよう最上行と最下行， 最左列と最右列の横棒セルには横棒は入れないことにする。

　０　１　２　３　４　
□｜□｜□｜□｜□｜□
□｜□｜□｜□｜□｜□
□｜□｜□｜□｜□｜□
□｜□｜□｜□｜□｜□
□｜□｜□｜□｜□｜□
□｜□｜□｜□｜□｜□
□｜□｜□｜□｜□｜□
□｜□｜□｜□｜□｜□
　Ａ　Ｂ　Ｃ　Ｄ　Ｅ　

図1.2.1 プログラム中でのイメージ

　０　１　２　３　４　
◇｜◇｜◇｜◇｜◇｜◇
◇｜□｜□｜□｜□｜◇
◇｜□｜□｜□｜□｜◇
◇｜□｜□｜□｜□｜◇
◇｜□｜□｜□｜□｜◇
◇｜□｜□｜□｜□｜◇
◇｜□｜□｜□｜□｜◇
◇｜◇｜◇｜◇｜◇｜◇
　Ａ　Ｂ　Ｃ　Ｄ　Ｅ　

図1.2.2 プログラム中でのイメージ
　　　「◇」と「□」は横棒セルであるが，
　　　「◇」には横棒を入れない。

あみだくじをプログラム中で表すときは，縦棒セルと横棒セルを同じ1つのセル扱いにして2次元配列と考える。
縦棒セルは「I」，横棒の入っていない横棒セルは「.」，横棒の入った横棒セルは「-」で表すものとすると図1.1.1のあみだくじは図1.2.3のような 8行×11列 のchar型2次元配列になる。
偶数列は横棒セルだけが，奇数列は縦棒セルだけが並んでいる。
第0行と第7行（最上行，最下行），第0列と第10列（最左列，最右列）には横棒は入ってはいけない。
縦棒番号0は第1列，縦棒番号1は第3列，縦棒番号2は第5列，・・・縦棒番号nは第2×n+1列　になっている。

  0   1   2   3   4      ← 縦棒番号はこのようになる

. I . I . I . I . I .    -- 第0行
. I - I . I - I . I .    -- 第1行
. I . I - I . I . I .    -- 第2行
. I - I . I . I - I .
. I . I . I - I . I .
. I . I - I . I - I .
. I - I . I - I . I .
. I . I . I . I . I .    -- 第7行

| | | |             |
| | | 第3列         第10列
| | 第2列
| 第1列
第0列

図1.2.3 プログラム中の2次元配列イメージ 　行と列の数え方の しきたり になれておこう！！

数学の座標系とプログラムの配列についての しきたり の違い　　

参考　配列に関する復習　　

１．３　あみだくじの作成と内部表現をそのまま表示するC言語プログラム

図1.1.1 のあみだくじをプログラムで表してみよう。
あみだくじを表す２次元配列を初期化代入で作成し，出来上がった２次元配列をそのまま画面表示する。
(まだ，あみだくじらしくない。)

List 1.3.1 あみだくじの作成と内部表現をそのまま表示するC言語プログラム amdexample.c

#include <stdio.h>

#define WORKSIZE 30

int main()
{
    //あみだくじの2次元配列記述
    char amidaex1[WORKSIZE][WORKSIZE]= {
        ".I.I.I.I.I.",
        ".I-I.I-I.I.",
        ".I.I-I.I.I.",
        ".I-I.I.I-I.",
        ".I.I.I-I.I.",
        ".I.I-I.I-I.",
        ".I-I.I-I.I.",
        ".I.I.I.I.I."
    };    //上記配列は30×30の要素の内8×11を使用している

    int nRows = 8;     //有効な行数　(number of rows の意味)
    int nColumns = 11; //有効な列数　(number of columns の意味)
   
    //2次元配列の有効な配列部分のみイメージ通り表示する
    int i,j;
    for (i=0; i<nRows; i++) {
        for (j=0; j<nColumns; j++) {
            printf("%c",amidaex1[i][j]);
        }
        printf("\n");
    }
    return 0;
}

補足説明

#define WORKSIZE 30
は，「プログラム中にWORKSIZEの語が現れたら，30と書いてあると思え」という意味である。
本演習ではすべての課題で30×30の配列を使う。 関数への受け渡しで，配列サイズの間違いが生じないように，すべてのプログラム中で，この定義された値を使うようにしている。

Screen 1.3.1 実行結果

.I.I.I.I.I.
.I-I.I-I.I.
.I.I-I.I.I.
.I-I.I.I-I.
.I.I.I-I.I.
.I.I-I.I-I.
.I-I.I-I.I.
.I.I.I.I.I.

参考
List 1.3.1 で，配列の初期化のところは次のように書いても実用上は同じ意味となる。

    char amidaex1[WORKSIZE][WORKSIZE]= {
        {'.','I','.','I','.','I','.','I','.','I','.'},
        {'.','I','-','I','.','I','-','I','.','I','.'},
        {'.','I','.','I','-','I','.','I','.','I','.'},
        {'.','I','-','I','.','I','.','I','-','I','.'},
        {'.','I','.','I','.','I','-','I','.','I','.'},
        {'.','I','.','I','-','I','.','I','-','I','.'},
        {'.','I','-','I','.','I','-','I','.','I','.'},
        {'.','I','.','I','.','I','.','I','.','I','.'}
    };    //上記配列は30×30の要素の内8×11を使用している

　課題１　　List 1.3.1 において，あみだくじを表す２次元配列を作成する機能， 作成された２次元配列を表示する機能をそれぞれ関数化する。 List 1.3.2において，関数printCharArray()ができていないので，List 1.3.1を参考に，完成させて，実行結果を確認する。 実行結果はScreen 1.3.1 の実行結果と同じになることが期待されている。 実行結果をコメントとしてプログラムソースファイルの末尾に貼り付けなさい。 (提出ファイル名amdprog1.c)

List 1.3.2 あみだくじの作成と内部表現表示するプログラム(未完成)

#include <stdio.h>

#define WORKSIZE 30

/*****
 * あみだくじex1を作成する関数makeAmidaex1()
 * と言ってもコピーしているだけ
 * 配列は初期化のときだけ直接代入が出来るようになっている
 * 与えられた配列に値を代入するように記述するのは面倒である
 * そのためコピーしている
 * char amd[][WORKSIZE] 持ち帰りのための２次元配列
 *      （2次元配列を引数で受けるときは1つ目の[]の中は空白で良い）
 * int sizes[] 持ち帰りのための配列
 * 　　sizes[0]には有効な行数を入れて返す
 * 　　sizes[1]には有効な列数を入れて返す
*****/
void makeAmidaex1(char amd[][WORKSIZE], int sizes[])
{
    char amidaex1[WORKSIZE][WORKSIZE]= {
        ".I.I.I.I.I.",
        ".I-I.I-I.I.",
        ".I.I-I.I.I.",
        ".I-I.I.I-I.",
        ".I.I.I-I.I.",
        ".I.I-I.I-I.",
        ".I-I.I-I.I.",
        ".I.I.I.I.I."
    };    //上記配列は30×30の要素の内8×11を使用している
    int nRows = 8;     //有効な行数　(number of rows の意味)
    int nColumns = 11; //有効な列数　(number of columns の意味)
    
    //有効な配列部分のみコピーする
    int i,j;
    for (i=0; i<nRows; i++) {
        for (j=0; j<nColumns; j++) {
            amd[i][j]=amidaex1[i][j];
        }
    }
    sizes[0]=nRows;
    sizes[1]=nColumns;
}

/*****
 * char型２次元配列の有効範囲を表示する関数printCharArray()
 * char amd[][WORKSIZE] 表示する２次元配列
 * int nRows 有効な行数
 * int nColumns 有効な列数
*****/
void printCharArray(char amd[][WORKSIZE], int nRows, int nColumns)
{
    /*  ----
   
    この部分を完成させる
   
    ----  */
}

int main()
{
    char amidamain[WORKSIZE][WORKSIZE]; //char型２次元配列の実体
    int sizes[2]; //２次元配列のサイズ
    //　　　　　　　第0要素 有効な行数，第1要素 有効な列数
    makeAmidaex1(amidamain,sizes);
    printCharArray(amidamain,sizes[0],sizes[1]);
    return 0;
}

補足説明

(1)関数の引数について
配列でない変数を関数の引数として与えた場合は，受け取った関数内で，その変数の値を変化させたとしても，呼び出し側の変数に影響をあたえることはない。
配列になっている変数を関数の引数として与えた場合は，受け取った関数内で，その変数の値を変化させると， 関数から戻るときに，その変数の値を呼び出し側に持ち帰ることになる。

(2)配列になっている変数を関数の引数として渡す場合の書き方
関数を呼び出すときに，配列になっている変数を引数とするときは，変数名のみ記述する。
  makeAmidaex1(amidamain,sizes);

呼び出される関数の定義部では配列であることを示す[]を記述する。（sizes）
また，2次元配列が渡される場合は1つ目のカッコ内は空白でよいが，2つ目のカッコ内は省略できない。（amd）
  void makeAmidaex1(char amd[][WORKSIZE], int sizes[])

　課題２　 　List 1.3.2 において，あみだくじを表す２次元配列を作成する関数makeAmidaex1() を，List 1.3.3 のmakeAmidaex2()に差し替えてプログラムを完成させなさい。 実行結果を確認し，実行結果をコメントとしてプログラムソースファイルの末尾に貼り付けなさい。 (提出ファイル名amdprog2.c)

List 1.3.3 関数makeAmidaex2()

/*****
 * あみだくじex2を作成する関数makeAmidaex2()
 * と言ってもコピーしているだけ
 * 配列は初期化のときだけ直接代入が出来るようになっている
 * 与えられた配列に値を代入するように記述するのは面倒である
 * そのためコピーしている
 * char amd[][WORKSIZE] 持ち帰りのための２次元配列
 *      （2次元配列を引数で受けるときは1つ目の[]の中は空白で良い）
 * int sizes[] 持ち帰りのための配列
 * 　　sizes[0]には有効な行数を入れて返す
 * 　　sizes[1]には有効な列数を入れて返す
*****/
void makeAmidaex2(char amd[][WORKSIZE], int sizes[])
{
    char amidaex2[WORKSIZE][WORKSIZE]= {
        ".I.I.I.I.I.I.",
        ".I-I.I-I.I-I.",
        ".I.I-I.I-I.I.",
        ".I-I.I-I.I.I.",
        ".I.I.I-I.I-I.",
        ".I.I-I.I-I.I.",
        ".I-I.I-I.I-I.",
        ".I.I-I.I-I.I.",
        ".I.I-I.I-I.I.",
        ".I.I.I.I.I.I."
    };    //上記配列は30×30の要素の内10×13を使用している
    int nRows = 10;    //有効な行数　(number of rows の意味)
    int nColumns = 13; //有効な列数　(number of columns の意味)
   
    //有効な配列部分のみコピーする
    int i,j;
    for (i=0; i<nRows; i++) {
        for (j=0; j<nColumns; j++) {
            amd[i][j]=amidaex2[i][j];
        }
    }
    sizes[0]=nRows;
    sizes[1]=nColumns;
}

１．４　あみだくじとして表示

List 1.3.1の実行結果は，あみだくじのプログラム内で用いた2次元配列をそのまま表示したものである。 デバッグには使えるが，このままではあみだくじにならない。 そこで次のような表示にしてあみだくじらしくする。ここでは「.」は空白「' '」に変換されており，横棒セルは3文字で表現されている。

Screen 1.4.1 「あみだくじ」らしい表示

   0   1   2   3   4
   I   I   I   I   I
   I---I   I---I   I
   I   I---I   I   I
   I---I   I   I---I
   I   I   I---I   I
   I   I---I   I---I
   I---I   I---I   I
   I   I   I   I   I
   A   B   C   D   E

　課題３　　List 1.3.4において，あみだくじをあみだくじらしく表す関数showAmidaLottery()を作成し，次のプログラムに埋め込みなさい。 この関数で出力されるあみだくじは，Screen 1.4.1のようになることが期待されている。
検査用mainでは2つのあみだくじ例を使っている。
実行結果を確認し，実行結果をコメントとしてプログラムソースファイルの末尾に貼り付けなさい。 (提出ファイル名amdprog3.c)

List 1.3.4 あみだくじらしい表示をするプログラム

#include <stdio.h>

#define WORKSIZE 30

/*次の3つの関数は前に作成した関数をそのままコピペする
void makeAmidaex1(char amd[][WORKSIZE], int sizes[])
void makeAmidaex2(char amd[][WORKSIZE], int sizes[])
void printCharArray(char amd[][WORKSIZE], int nRows, int nColumns)
*/

/*****
 * あみだくじらしい表示を行う関数showAmidaLottery()
 * char amd[][WORKSIZE] 表示する２次元配列
 * int nRows 有効な行数
 * int nColumns 有効な列数
 * 空白を表していた「.」は空白に変換される
 * 横棒セルは3文字に変換される
*****/
void showAmidaLottery(char amd[][WORKSIZE], int nRows, int nColumns)
{
    /*  ----
   
    この部分を完成させる
   
    ----  */
}

int main()
{
    char amidamain[WORKSIZE][WORKSIZE]; //char型２次元配列の実体
    int sizes[2]; //２次元配列のサイズ
    //　　　　　　　第0要素 有効な行数,第1要素 有効な列数
    makeAmidaex1(amidamain,sizes);
    showAmidaLottery(amidamain,sizes[0],sizes[1]);
    printf("\n");
    makeAmidaex2(amidamain,sizes);
    showAmidaLottery(amidamain,sizes[0],sizes[1]);
    return 0;
}

ヒント
横棒セルは同じ文字を３回表示するが，これは printf("%c%c%c",ch,ch,ch);でよい。
横棒セルは偶数列にあるので偶数列のときに同じ文字を３回表示するという考え方でプログラムすると，後で都合が良い。
int型変数jが偶数であるというのは，j%2==0 と表記される。（ if (j%2==0) {... ）

２　あみだくじの生成
２．１　空白あみだくじ

図2.1.1 のような横棒が1つも入っていない空白あみだくじ配列を作ってみよう。
これは，後から横棒追加であみだくじを作成するための準備の作業である。

. I . I . I . I . I .
. I . I . I . I . I .
. I . I . I . I . I .
. I . I . I . I . I .
. I . I . I . I . I .
. I . I . I . I . I .
. I . I . I . I . I .
. I . I . I . I . I .

図2.1.1 横棒が一本も入っていない2次元配列イメージ

　課題４　　List 2.1.1のプログラムで空白あみだくじを作成する関数makeBlankAmida()を作成する。ただし，この関数の仕様は次のとおりとする。 実行結果はScreen 2.1.1のとおりになることを確認しなさい。
検査用mainでは検査用の数値の組み合わせを構造体配列で記述している。
実行結果をコメントとしてプログラムソースファイルの末尾に貼り付けなさい。 (提出ファイル名amdprog4.c)

関数makeBlankAmida()仕様
指定された大きさの空白あみだくじを作成する。
関数の返す値はint型とし，空白あみだくじ作成成功の場合は0，失敗の場合は-1を返すものとする。
引数は次のとおりとする。
(1)char amd[][WORKSIZE] 持ち帰りのための２次元配列
(2)int sizes[] 持ち帰りのための配列
  　　sizes[0]には有効な行数を入れて返す
  　　sizes[1]には有効な列数を入れて返す
(3)int nRows 空白あみだの行数設定値（この関数への入力）
(4)int nVLines 空白あみだの縦棒本数設定値（この関数への入力）
ただし，次の場合は空白あみだくじ作成ができないので，作成失敗とする。
(1)出来上がりの空白あみだくじの大きさがWORKSIZE*WORKSIZEからはみ出る
(2)nRowsが2以下（横棒が一本も入らない）
(3)nVLinesが2未満（あみだくじにならない）

List 2.1.1 空白あみだくじの生成

#include <stdio.h>

#define WORKSIZE 30

/*****
 * 空白あみだくじを作成する関数makeBlankAmida()
 * char amd[][WORKSIZE] 持ち帰りのための２次元配列
 * int sizes[] 持ち帰りのための配列
 * 　　sizes[0]には有効な行数を入れて返す
 * 　　sizes[1]には有効な列数を入れて返す
 * int nRows 空白あみだの行数設定値（この関数への入力）
 * int nVLines 空白あみだの縦棒本数設定値（この関数への入力）
 * 関数の返す値　0:成功　-1:作成失敗
 * 失敗とは
 * (1)出来上がりの空白あみだくじの大きさがWORKSIZE*WORKSIZEからはみ出る
 * (2)nRowsが2以下（横棒が一本も入らない）
 * (3)nVLinesが2未満（あみだくじにならない）
*****/
int makeBlankAmida(char amd[][WORKSIZE], int sizes[], int nRows, int nVLines)
{
    /*  ----
   
    この部分を完成させる
   
    ----  */
}

/*次の関数は前に作成した関数をそのままコピペする
void printCharArray(char amd[][WORKSIZE], int nRows, int nColumns)
*/

typedef struct {
    int nRows;
    int nVLines;
} amidasize_t;

int main()
{
    char amidamain[WORKSIZE][WORKSIZE]; //char型２次元配列の実体
    int sizes[2]; //２次元配列のサイズ
    amidasize_t asizes[]={
        {5,5},     //asizes[0].nRows，asizes[0].nVLinesの値
        {10,12},   //asizes[1].nRows，asizes[1].nVLinesの値
        {1,10},    //asizes[2].nRows，asizes[2].nVLinesの値
        {2,10},    //asizes[3].nRows，asizes[3].nVLinesの値
        {3,10},    //   ：
        {10,14},
        {10,15},
        {30,8},
        {31,8}
    };
    int result;
    int i;
    int nRows,nVLines;
    int nDatas; //検査データの数
    nDatas=sizeof(asizes)/sizeof(amidasize_t);
    for (i=0; i<nDatas; i++) {
        nRows=asizes[i].nRows;
        nVLines=asizes[i].nVLines;
        result=makeBlankAmida(amidamain,sizes,nRows,nVLines);
        if (result==0) {
            printf("%d %d %s\n",nRows,nVLines,"DONE");
            printCharArray(amidamain,sizes[0],sizes[1]);
        } else {
            printf("%d %d %s\n",nRows,nVLines,"NG");
        }
    }
    return 0;
}

Screen 2.1.1　実行結果の予想

5 5 DONE
.I.I.I.I.I.
.I.I.I.I.I.
.I.I.I.I.I.
.I.I.I.I.I.
.I.I.I.I.I.
10 12 DONE
.I.I.I.I.I.I.I.I.I.I.I.I.
.I.I.I.I.I.I.I.I.I.I.I.I.
.I.I.I.I.I.I.I.I.I.I.I.I.
.I.I.I.I.I.I.I.I.I.I.I.I.
.I.I.I.I.I.I.I.I.I.I.I.I.
.I.I.I.I.I.I.I.I.I.I.I.I.
.I.I.I.I.I.I.I.I.I.I.I.I.
.I.I.I.I.I.I.I.I.I.I.I.I.
.I.I.I.I.I.I.I.I.I.I.I.I.
.I.I.I.I.I.I.I.I.I.I.I.I.
1 10 NG
2 10 NG
3 10 DONE
.I.I.I.I.I.I.I.I.I.I.
.I.I.I.I.I.I.I.I.I.I.
.I.I.I.I.I.I.I.I.I.I.
10 14 DONE
.I.I.I.I.I.I.I.I.I.I.I.I.I.I.
-- 途中省略8行 --
.I.I.I.I.I.I.I.I.I.I.I.I.I.I.
10 15 NG
30 8 DONE
.I.I.I.I.I.I.I.I.
-- 途中省略28行 --
.I.I.I.I.I.I.I.I.
31 8 NG

２．２　横棒を指定した横棒セルに置こう

空白あみだくじができたので，横棒を設置しよう。

　課題５　　List 2.2.1のプログラム内に関数insertLeg()を完成させる。 （あみだくじの横棒は英語ではlegと呼ばれている。）この関数の仕様は次のとおりとする。実行結果はScreen 2.2.1のとおりになることを確認しなさい。 実行結果をコメントとしてプログラムソースファイルの末尾に貼り付けなさい。 (提出ファイル名amdprog5.c)

関数insertLeg()仕様
あみだくじ２次元配列の指定した位置に横棒を入れる。
関数の返す値はint型とし，横棒設置成功の場合は0，失敗の場合は負のエラー番号を返すものとする。
引数は次のとおりとする。
(1)char amd[][WORKSIZE] 持ち帰りのための２次元配列
(2)int nRows amd[][WORKSIZE]中の有効な行数
(3)int nColumns amd[][WORKSIZE]中の有効な列数
(4)int row     横棒を置いて欲しい位置の行番号(0から数える)
(5)int column  横棒を置いて欲しい位置の列番号(0から数える)
ただし，次の場合は横棒設置ができないので，作成失敗とし，その原因をエラー番号で関数の返す値として返すこととする。
(1)nRowsがWORKSIZEより大きい　(エラー番号:-1)
(2)nRowsが2以下（横棒が一本も入らない）　(エラー番号:-1)
(3)nColumnsがWORKSIZEを超えている　　(エラー番号:-2)
(4)nColumnsが5未満（横棒が一本も入らない） 　(エラー番号:-2)
(5)rowで与えられた位置があみだくじ領域の外側 　(エラー番号:-3)
(6)columnで与えられた位置があみだくじ領域の外側 　(エラー番号:-4)
(7)row，columnで与えられた位置が縦棒セル 　(エラー番号:-5)
(8)row，columnで与えられた位置にすでに横棒が入っている 　(エラー番号:-6)
(9)row，columnで与えられた位置の左右の横棒セルのどちらかにすでに横棒が入っている 　(エラー番号:-7)

List 2.2.1 横棒を指定した横棒セルに置く

#include <stdio.h>

#define WORKSIZE 30

/*****
 * あみだくじ２次元配列の指定した位置に横棒を入れる関数insertLeg()
 * char amd[][WORKSIZE] 持ち帰りのための２次元配列
 * int nRows amd[][WORKSIZE]中の有効な行数
 * int nColumns amd[][WORKSIZE]中の有効な列数
 * int row     横棒を置いて欲しい位置の行番号(0から数える)
 * int column  横棒を置いて欲しい位置の列番号(0から数える)
 * 関数の返す値
 * 横棒が置けた場合には0を返す
 * 以下の場合は横棒が置けないので以下に与えるエラー番号（負の値）を返す
 * (1)nRowsがWORKSIZEより大きい　(エラー番号:-1)
 * (2)nRowsが2以下（横棒が一本も入らない）　(エラー番号:-1)
 * (3)nColumnsがWORKSIZEを超えている　　(エラー番号:-2)
 * (4)nColumnsが5未満（横棒が一本も入らない） 　(エラー番号:-2)
 * (5)rowで与えられた位置があみだくじ領域の外側 　(エラー番号:-3)
 * (6)columnで与えられた位置があみだくじ領域の外側 　(エラー番号:-4)
 * (7)row，columnで与えられた位置が縦棒セル 　(エラー番号:-5)
 * (8)row，columnで与えられた位置にすでに横棒が入っている 　(エラー番号:-6)
 * (9)row，columnで与えられた位置の左右の横棒セルのどちらかにすでに横棒が入っている 　(エラー番号:-7)
*****/
int insertLeg(char amd[][WORKSIZE], int nRows, int nColumns, int row, int column)
{
    /*  ----
   
    この部分を完成させる
   
    ----  */
}


/*次の2つの関数は前に作成した関数をそのままコピペする
int makeBlankAmida(char amd[][WORKSIZE], int sizes[], int nRows, int nVLines)
void printCharArray(char amd[][WORKSIZE], int nRows, int nColumns)
*/

typedef struct {
    int row;
    int column;
} coord_t;

int main()
{
    char amidamain[WORKSIZE][WORKSIZE]; //char型２次元配列の実体
    int sizes[2]; //２次元配列のサイズ
    coord_t coords[]={
        {1,2},     //coords[0].row，coords[0].columnの値
        {5,8},     //coords[1].row，coords[1].columnの値
        {0,6},     //coords[2].row，coords[2].columnの値
        {1,6},     //coords[3].row，coords[3].columnの値
        {2,6},     //   ：
        {2,6},     //   ：
        {2,8},     //   ：
        {6,4},
        {6,5},
        {7,4}
    };
    int result;
    int i;
    int row,column;
    int nRows=8;   //あみだくじの大きさ　行数
    int nVLines=5; //あみだくじの大きさ　縦棒本数
    int nDatas; //検査データの数
    result=makeBlankAmida(amidamain,sizes,nRows,nVLines);
    if (result==-1) return -1;
    printf("nRows,nColumns=%d %d\n",sizes[0],sizes[1]);
    printCharArray(amidamain,sizes[0],sizes[1]);
    nDatas=sizeof(coords)/sizeof(coord_t);
    for (i=0; i<nDatas; i++) {
        row=coords[i].row;
        column=coords[i].column;
        result=insertLeg(amidamain,sizes[0],sizes[1],row,column);
        if (result==0) {
            printf("%d %d %s\n",row,column,"DONE");
        } else {
            printf("%d %d %s %d\n",row,column,"NG",result);
        }
    }
    printCharArray(amidamain,sizes[0],sizes[1]);
    return 0;
}

関数insertLeg() 作成のヒント　

参考　構造体の復習　

Screen 2.2.1　実行結果の予想

nRows,nColumns=8 11
.I.I.I.I.I.
.I.I.I.I.I.
.I.I.I.I.I.
.I.I.I.I.I.
.I.I.I.I.I.
.I.I.I.I.I.
.I.I.I.I.I.
.I.I.I.I.I.
1 2 DONE
5 8 DONE
0 6 NG -3
1 6 DONE
2 6 DONE
2 6 NG -6
2 8 NG -7
6 4 DONE
6 5 NG -5
7 4 NG -3
.I.I.I.I.I.
.I-I.I-I.I.
.I.I.I-I.I.
.I.I.I.I.I.
.I.I.I.I.I.
.I.I.I.I-I.
.I.I-I.I.I.
.I.I.I.I.I.

２．３　あみだくじを作成する

空のあみだくじの作成が出来，指定した場所へ横棒を設置することが出来るようになった。 乱数発生器ライブラリ関数rand()を用いて，ランダムな設置位置を発生して，適当な数の横棒を設置して，あみだくじを作ろう。
List 2.3.1 は，すでにList 2.1.1の関数makeBlankAmida()を用いて作成された空白あみだくじが，2次元配列char amd[][WORKSIZE]にできている前提で，関数insertLeg()を使って横棒をnLegs本設置して， あみだくじを完成させる関数completeAmidaLottery()である。

乱数発生器ライブラリ関数rand()は，#include <stdlib.h>のもとで使う。この関数を呼び出すたびにランダムな0以上の整数が返される。 発生値の最大はコンパイラシステムによって異なるが，RAND_MAXという定数が関数rand()の発生する最大値になっている。

List 2.3.1 空白あみだくじに指定の本数の横棒を加えて，あみだくじを作る関数

/*****
 * 空白あみだくじに指定の本数の横棒を加えて，あみだくじを作る関数completeAmidaLottery()
 * char amd[][WORKSIZE] 持ち帰りのための２次元配列（空白あみだくじが入っている）
 * int nRows 有効な行数
 * int nColumns 有効な列数
 * int nLegs 横棒設置目標数
 * 関数の返す値　0:成功　-1:作成失敗（これはない）
*****/
int completeAmidaLottery(char amd[][WORKSIZE], int nRows, int nColumns, int nLegs)
{
    int count=0;          //設置した横棒数
    int row,column;       //横棒設置試行位置
    int result;
    while (count<nLegs) {
        row=rand()%nRows;           //rowは0≦row＜nRowsの値になる
        column=rand()%nColumns/2*2; //2で割って2をかけることで偶数化
        result=insertLeg(amd,nRows,nColumns,row,column);
        if (result==0) count++;
        //printf("row,column,count=%d %d %d\n",row,column,count);
    }
    return 0;
}

空のあみだくじを行数nRows（３以上），縦棒本数nVLines（2以上）で作成したとき，置くことの出来る横棒本数の最大値は決まっている。


 1行あたり横棒本数の
設置可能最大値		 あみだくじ全体での
横棒本数の設置可能最大値
nVLinesが偶数のとき nVLines/2 nVLines/2*(nRows-2)
nVLinesが奇数のとき (nVLines-1)/2 (nVLines-1)/2*(nRows-2)

どうしてそうなるのか考えてみよう。

演算が整数演算なのでnVLinesが偶数であっても奇数であっても結局　nVLines/2*(nRows-2)　が横棒本数の設置可能最大値となる。
ランダムに横棒を設置すると最大値まで設置できるとは限らないので，横棒設置目標本数をその半分にして
nVLines/2*(nRows-2)/2
を使うことにする。（計算順序が大事，変更してはならない。）
List 2.3.2 は関数completeAmidaLottery()などを使ってあみだくじを作成し，表示するmainプログラムである。
作成するあみだくじの大きさは行数(nRows)15，縦棒本数(nVLines)10であり，横棒設置本数はnVLines/2*(nRows-2)/2になっている。
関数 makeBlankAmida() で空のあみだくじを作り，うまく作れたら空のあみだくじを関数 printCharArray() でそのまま表示し， 関数 completeAmidaLottery() で横棒を指定本数設置している。そしてうまくできたら， 関数showAmidaLottery() であみだくじとして表示している。

List 2.3.2 検証用main

int main()
{
    char amidamain[WORKSIZE][WORKSIZE]; //char型２次元配列の実体
    int sizes[2]; //２次元配列のサイズ
    int nRows=15;   //あみだくじの大きさ　行数
    int nVLines=10; //あみだくじの大きさ　縦棒本数
    int nLegs; //設置する横棒の数
    int result;
    nLegs=nVLines/2*(nRows-2)/2;  //設置可能最大値/2を設定
    result=makeBlankAmida(amidamain,sizes,nRows,nVLines);
    if (result==-1) return -1;
    printf("nRows,nColumns,nLegs=%d %d %d\n",sizes[0],sizes[1],nLegs);
    printCharArray(amidamain,sizes[0],sizes[1]);
    result=completeAmidaLottery(amidamain,sizes[0],sizes[1],nLegs);
    if (result==0) {
        printf("DONE\n");
        showAmidaLottery(amidamain,sizes[0],sizes[1]);
    } else {
        printf("NG\n");
    }
    return 0;
}

Screen 2.3.1　実行結果の予想　（作成されたあみだくじの形は乱数列に依存する）

nRows,nColumns,nLegs=15 21 32
.I.I.I.I.I.I.I.I.I.I.
.I.I.I.I.I.I.I.I.I.I.
.I.I.I.I.I.I.I.I.I.I.
.I.I.I.I.I.I.I.I.I.I.
.I.I.I.I.I.I.I.I.I.I.
.I.I.I.I.I.I.I.I.I.I.
.I.I.I.I.I.I.I.I.I.I.
.I.I.I.I.I.I.I.I.I.I.
.I.I.I.I.I.I.I.I.I.I.
.I.I.I.I.I.I.I.I.I.I.
.I.I.I.I.I.I.I.I.I.I.
.I.I.I.I.I.I.I.I.I.I.
.I.I.I.I.I.I.I.I.I.I.
.I.I.I.I.I.I.I.I.I.I.
.I.I.I.I.I.I.I.I.I.I.
DONE
   0   1   2   3   4   5   6   7   8   9
   I   I   I   I   I   I   I   I   I   I
   I   I   I---I   I---I   I   I   I---I
   I   I   I---I   I   I---I   I   I   I
   I---I   I   I   I   I---I   I   I   I
   I   I   I---I   I---I   I   I   I---I
   I   I---I   I---I   I   I---I   I   I
   I   I---I   I---I   I   I   I---I   I
   I   I   I   I   I   I---I   I   I---I
   I---I   I   I---I   I   I   I   I---I
   I   I---I   I   I   I   I---I   I---I
   I---I   I   I   I   I   I---I   I   I
   I   I---I   I---I   I---I   I---I   I
   I   I   I---I   I   I   I   I   I---I
   I   I   I   I   I   I   I   I   I   I
   I   I   I   I   I   I   I   I   I   I
   A   B   C   D   E   F   G   H   I   J


　課題６　　List 2.3.2 はmainだけであるが，必要な関数を集めて1つのプログラムとして動作するようにしなさい。実行結果はScreen 2.3.1のとおりになることを確認しなさい。実行結果をコメントとしてプログラムソースファイルの末尾に貼り付けなさい。 (提出ファイル名amdprog6.c)

ヒント
(1)次の3行を先頭に忘れないこと
#include <stdio.h>
#include <stdlib.h>
#define WORKSIZE 30
(2)使われる関数は使っている行よりも前に書かれていなければならないことに注意すること
(3)使っているに，その関数がプログラム中にない場合にはリンクエラーが起きる。エラーメッセージ中に見つからない関数の名前が表示されている。

参考１
ここで作成されたプログラムは，何回実行しても同じあみだくじしか作成できない。これは，関数rand()が，毎回同じ出発点を持つ乱数列を発生するためである。 プログラム起動ごとに異なるあみだくじを生成するためには，次のようにする。
(1) プログラムの先頭部の#include <stdio.h>が書いてある付近に
#include <time.h>
を加える。
(2)mainの中の先頭部に
srand((unsigned)time(NULL));
を加える。こうすることで，出発点に使われる数に，現在時刻を表す数が使われることになり，毎回異なる乱数列の発生が期待できる。

参考２
List 2.3.1に示した関数completeAmidaLottery()には実は欠点がある。 もし横棒設置目標数（nLegs）に設置可能最大値くらいの値が入力されたなら， ランダムな横棒設置試行をしているので，よほど運が良くなければ，その数まで横棒を置くことが出来ない。 そうすると，whileループから抜け出せなくなる。 そこでwhileループを繰り返す回数を制限しておくのがよい。
whileループ繰返し回数制限のある関数completeAmidaLottery()

３　あみだくじを解く
３．１　縦棒指定に対する解

あみだくじにおいて，縦棒番号を指定し，その縦棒の最上行からあみだくじのルール通りに下方へトレースして， 最下行にたどり着いたときに縦棒番号は何番になっているか求めてみよう。List 1.3.1の関数makeAmidaex1()で作成したあみだくじを作業対象としよう。

　課題７　　List 3.1.1のプログラム内に関数followAmidaLottery()を完成させる。この関数の仕様は次のとおりとする。List 3.1.1は不完全なプログラムなので必要な記述を補いなさい。 関数followAmidaLottery()は指定した縦棒番号に対する解の縦棒番号を求めるものなので， 1回の呼び出しでは1つの解しか求められないので， すべての縦棒に関する解を並べるには，main側から複数回呼び出すことになる。
実行結果は Screen 3.1.1 のとおりになることを確認しなさい。実行結果をコメントとしてプログラムソースファイルの末尾に貼り付けなさい。 (提出ファイル名amdprog7.c)

関数followAmidaLottery()仕様
指定した縦棒番号に対する解の縦棒番号を求める
関数の返す値はint型とし，解が求められた場合は解番号（0以上の値），失敗の場合は-1を返すものとする。
この関数内では画面への出力はしない。 （作成段階で動作を確認するために挿入したprintfなどはコメントアウトすること）
引数は次のとおりとする。
(1)char amd[][WORKSIZE] 対象とする２次元配列
(2)int nRows amd[][WORKSIZE]中の有効な行数
(3)int nColumns amd[][WORKSIZE]中の有効な列数
(4)int vline スタートすべき縦棒番号(0から数える)
ただし，与えられた縦棒番号vlineが存在しないときは，作業失敗となる。

List 3.1.1 指定された縦棒番号から解を求める

/*****
 * 指定した縦棒番号に対する解となる縦棒番号を求める関数followAmidaLottery()
 * char amd[][WORKSIZE] 対象とする２次元配列
 * int nRows 有効な行数
 * int nColumns 有効な列数
 * int vline スタートすべき縦棒番号(0から数える)
 * 関数の返す値　たどり着いた縦棒番号(0以上の値)
 * ただし与えられた縦棒番号vlineが存在しないときは-1を返す
*****/
int followAmidaLottery(char amd[][WORKSIZE], int nRows, int nColumns, int vline)
{
    /*  ----
   
    この部分を完成させる
   
    ----  */
}

int main()
{
    char amidamain[WORKSIZE][WORKSIZE]; //char型２次元配列の実体
    int sizes[2]; //２次元配列のサイズ
    //　　　　　　　第0要素 有効な行数,第1要素 有効な列数
    int vline; //縦棒番号
    int result;
    int checkinglimit; //検査の上限
    makeAmidaex1(amidamain,sizes);
    showAmidaLottery(amidamain,sizes[0],sizes[1]);
    printf("\n");
    checkinglimit=sizes[1]/2+1; //縦棒本数+1
    for (vline=-1; vline<checkinglimit; vline++) {
        result=followAmidaLottery(amidamain,sizes[0],sizes[1],vline);
        if (0<=result) {
            printf("top,bottom= %d %c\n",vline,'A'+result);
        } else {
            printf("top= %d failed\n",vline);
        }
    }
    return 0;
}

Screen 3.1.1　実行結果の予想

   0   1   2   3   4
   I   I   I   I   I
   I---I   I---I   I
   I   I---I   I   I
   I---I   I   I---I
   I   I   I---I   I
   I   I---I   I---I
   I---I   I---I   I
   I   I   I   I   I
   A   B   C   D   E

top= -1 failed
top,bottom= 0 E
top,bottom= 1 D
top,bottom= 2 C
top,bottom= 3 B
top,bottom= 4 A
top= 5 failed

ヒント
この関数の大枠は次のようになる。

rowを0からnRows-1まで変化させながらその行内で必要な左右方向の動きを記述する
左右方向の動きとは，現在の左右方向の位置表しているcolumnの値の変化である。
あみだの1行内（あるrowの位置）での作業は次の3つの内のどれか１つである
  (1)左に行くことができたら左へ移動する
  (2)右に行くことができたら右へ移動する
  (3)左右方向へは動かない

空白の横棒セルが両端に加えられているので，現在のcolumnの左右のチェックが簡単になっている。
もし，無かったら，左端では左をチェックしてはならないなど，条件が複雑になっていた。

int followAmidaLottery(char amd[][WORKSIZE], int nRows, int nColumns, int vline)
{
    現在位置をrow,columnで表すほうが便利なのでこの２つの変数を使う
    vline値から対応するcolumn値を計算する
    得られたcolumn値がこのあみだくじの領域外だったら return -1;
    rowを0からnRows-1まで変化させながらループ {
        //次の3つの内のどれか１つを行う
        //現在のcolumnの左に横棒があったら左へ移動する（column=column-2;）
        //現在のcolumnの右に横棒があったら右へ移動する（column=column+2;）
        //現在のcolumnの左右に横棒がないので，左右方向へは動かない（columnは変化なし）
    }
    最後までたどり着いた時のcolumnから対応する縦棒番号を求める
    return 縦棒番号;
}


３．２　あみだくじの解の可視化

あみだくじで解を求めるのに通過した経路を見えるように表示してみよう。次の2段階に分けると見通しの良いプログラムとなる。
(1)縦棒番号を指定し，その縦棒の最上行からあみだくじのルール通りに下方へトレースして， 最下行にたどり着くまでに通過したセルに「＊」を書き込んで足跡とする。（まだ表示はしない）
(2)すでに作成されているあみだくじ表示関数で表示する。
ある縦棒番号を指定した可視化作業が終わり，続けてる別な縦棒番号を指定した作業を行うと，２つの足跡が混ざってしまう。
そのため，作業を行う場合には，毎回あみだくじを作っている。
List 1.3.1の関数makeAmidaex1()で作成したあみだくじを作業対象としよう。

　課題８　　List 3.2.1のプログラム内に関数leaveFootprints()を完成させる。この関数の仕様は次のとおりとする。List 3.2.1は不完全なプログラムなので必要な記述を補いなさい。 関数leaveFootprints()は指定した縦棒番号に対する足跡を求めるものなので， 1回の呼び出しでは1つの解しか求められないので， すべての縦棒に関する解を並べるには，main側から複数回呼び出すことになる。
実行結果は Screen 3.2.1 のとおりになることを確認しなさい。 実行結果をコメントとしてプログラムソースファイルの末尾に貼り付けなさい。 (提出ファイル名amdprog8.c)

関数leaveFootprints()仕様
指定した縦棒番号からたどった足跡を残す。
たどる時に通過したセルに「＊」を書き込むことによって足跡が残ったものとする。
この関数内では画面への出力はしない。 （作成段階で動作を確認するために挿入したprintfなどはコメントアウトすること）
関数の返す値はint型とし，求められた場合は解番号（0以上の値），失敗の場合は-1を返すものとする。
引数は次のとおりとする。
(1)char amd[][WORKSIZE] 対象とする２次元配列
(2)int nRows amd[][WORKSIZE]中の有効な行数
(3)int nColumns amd[][WORKSIZE]中の有効な列数
(4)int vline スタートすべき縦棒番号(0から数える)
ただし，与えられた縦棒番号vlineが存在しないときは，作業失敗となる。

List 3.2.1 指定された縦棒番号から解を求める

/*****
 * あみだくじで指定した縦棒番号からたどった足跡を残す関数leaveFootprints()
 * char amd[][WORKSIZE] 対象とする２次元配列
 * int nRows 有効な行数
 * int nColumns 有効な列数
 * int vline スタートすべき縦棒番号(0から数える)
 * 通過したamd[][WORKSIZE]のセルには'*'を代入する。
 * 関数の返す値　たどり着いた縦棒番号(0以上の値)
 * ただし与えられた縦棒番号vlineが存在しないときは-1を返す
*****/
int leaveFootprints(char amd[][WORKSIZE], int nRows, int nColumns, int vline)
{
    /*  ----
   
    この部分を完成させる
   
    ----  */
}

int main()
{
    char amidamain[WORKSIZE][WORKSIZE]; //char型２次元配列の実体
    int sizes[2]; //２次元配列のサイズ
    //　　　　　　　第0要素 有効な行数,第1要素 有効な列数
    int vline; //縦棒番号
    int result;
    int checkinglimit; //検査の上限
    makeAmidaex1(amidamain,sizes);
    checkinglimit=sizes[1]/2+1; //縦棒本数+1
    for (vline=-1; vline<checkinglimit; vline++) {
        makeAmidaex1(amidamain,sizes);
        result=leaveFootprints(amidamain,sizes[0],sizes[1],vline);
        if (0<=result) {
            showAmidaLottery(amidamain,sizes[0],sizes[1]);
        } else {
            printf("top= %d failed\n",vline);
        }
        printf("\n");
    }
    return 0;
}

Screen 3.2.1　実行結果の予想

top= -1 failed

top,bottom= 0 E
   0   1   2   3   4
   *   I   I   I   I
   *****   I---I   I
   I   *****   I   I
   I---I   *   I---I
   I   I   *****   I
   I   I---I   *****
   I---I   I---I   *
   I   I   I   I   *
   A   B   C   D   E

top,bottom= 1 D
   0   1   2   3   4
   I   *   I   I   I
   *****   I---I   I
   *   I---I   I   I
   *****   I   I---I
   I   *   I---I   I
   I   *****   I---I
   I---I   *****   I
   I   I   I   *   I
   A   B   C   D   E

top,bottom= 2 C
   0   1   2   3   4
   I   I   *   I   I
   I---I   *****   I
   I   I---I   *   I
   I---I   I   *****
   I   I   I---I   *
   I   I---I   *****
   I---I   *****   I
   I   I   *   I   I
   A   B   C   D   E

top,bottom= 3 B
   0   1   2   3   4
   I   I   I   *   I
   I---I   *****   I
   I   *****   I   I
   *****   I   I---I
   *   I   I---I   I
   *   I---I   I---I
   *****   I---I   I
   I   *   I   I   I
   A   B   C   D   E

top,bottom= 4 A
   0   1   2   3   4
   I   I   I   I   *
   I---I   I---I   *
   I   I---I   I   *
   I---I   I   *****
   I   I   *****   I
   I   *****   I---I
   *****   I---I   I
   *   I   I   I   I
   A   B   C   D   E

top= 5 failed