プログラミング言語 I 第 12 回 パズル 1
埼玉大学工学部 電気電子システム工学科 伊藤 和人
問題
ある雨の日、こういち君たち5
人は自分の 傘をどこかに置き忘れてしまいました。傘 の色と忘れた場所は全員違います。5
人の 話からそれぞれの傘の色と置き忘れた場 所を推理してください。
傘の色:
白、赤、黄、緑、黒
場所:
学校、塾、公園、電車、バス出典
:
朝日新聞5 人の話
こういち:
ボクは白い傘を忘れたんだけど、場所は 塾ではないよ。
あさこ:
バスに傘を置き忘れちゃった。黒い傘は私 のじゃないよ。
ひろこ:
私の傘は緑色なんだけど、電車には置き忘 れていないの。
しょうご:
黒い傘を学校に置き忘れた人はいないよ。
しんぞう:
黄色い傘は公園に置き忘れていたんだっ て。その傘はボクのではないよ。ボクは電車に乗っ ていないから、電車に置き忘れることもないよ。出典
:
朝日新聞解き方のヒント
表を使って解く
正しいところに○
ありえなければ×こういちあさこ しょうごひろこ しんぞう学校 公園塾 電車バス
赤白 黄 緑 黒 学校 塾 公園 電車 バス
名前忘れた場所
傘の色 忘れた場所
こういちあさこ しょうごひろこ しんぞう学校 公園塾 電車バス
学校 塾 公園 電車 バス
○ ×
× ○
○ ×
× ×
×
○
名前忘れた場所
忘れた場所
赤白 黄 緑 黒
傘の色
与えられた条件を表に記入
条件に従い、○または ×を記入
こういち
:
ボクは白い傘を 忘れたんだけど、
場所は塾ではないよ。
表の最終形
例えば名前と傘の色について、1
対1
に対 応するから、各行、各列に○は1
つ、他は 全て×
名前と場所、場所と色についても同様名前と傘の色の 対応の例
こういちあさこ しょうごひろこ しんぞう
○××××
×○×××
×××○×
××○××
××××○
名前 赤白 黄 緑 黒傘の色
各行、列について
○は
1
つだけプログラムで解くための考え方
答えの組み合わせは何通り?
名前と置き忘れた場所の組み合わせ⇒ 5
の順列⇒ 5!=120
通り
名前と傘の色の組み合わせ⇒ 5
の順列⇒ 5!=120
通り
組み合わせは120 × 120=14400
通りだけ
全ての組み合わせを列挙し、条件に矛盾 しないものを選べばよい全体のアルゴリズム
名前と場所の組み合わせ
(120
通り)
を順に 発生名前と色の組み合わせ
(120
通り)
を順 に発生名前・場所・色の組み合わせが条 件を満たすか
・
Yes ⇒
終了プログラム化 ( その 1)
名前、場所、色を番号(
整数)
で区別する
名前0:
こういち、1:
あさこ、2:
ひろこ、3:
しょうご、4:
しんぞう
置き忘れた場所0:
学校、1:
塾、2:
公園、3:
電車、4:
バス
傘の色0:
白、1:
赤、2:
黄、3:
緑、4:
黒プログラム化 ( その 2)
名前と場所の対応⇒
配列B
を使用名前
0:
こういち、1:
あさこ、2:
ひろこ、3:
しょうご、4:
しんぞう 置き忘れた場所0:
学校、1:
塾、2:
公園、3:
電車、4:
バスB[0]=0
B[1]=4 B[2]=1 B[3]=3 B[4]=2
こういち
:
学校 あさこ:
バス ひろこ:
塾しょうご
:
電車 しんぞう:
公園例
配列インデクス が名前、値が 場所に対応
プログラム化 ( その 3)
名前と色の対応⇒
配列C
を使用名前
0:
こういち、1:
あさこ、2:
ひろこ、3:
しょうご、4:
しんぞう 傘の色0:
白、1:
赤、2:
黄、3:
緑、4:
黒C[0]=0 C[1]=2 C[2]=3 C[3]=4 C[4]=1
こういち
:
白 あさこ:
黄 ひろこ:
緑 しょうご:
黒 しんぞう:
赤例
配列インデクス が名前、値が 色に対応
int B[5], C[5];
int n, n0;
n = 0;
B[n] = -1;
while( 1 ){
B[n]++;
if( B[n] >= 5 ){
if( -- n < 0 ) break;
}else{ /* B[n]
が割り当て済みの値でないか*/
for( n0 = 0 ; n0 < n ; n0++ ){
if( B[n] == B[n0] ) break;
} if( n0 < n ) continue; /* B[n]
は割り当てできない*/
if( n == 4 ){ /* B
割り当て完了*/
if( EnumerateC() ) break;
}else{
B[++n] = -1;
} } }
A-C
間組み合わせを列挙A-B
間組み合わせ列挙以下の
B[n]++
と組み合わせてB[n]=0
から開始するようにするA-B( 名前 - 場所 ) の組み合わせ 1
1 4 0
配列
B 0 1 2 3 4
ここ
(n=3)
に入れる値を決める候補
B[3]=0
B[2]=0
で既に使用済み⇒ n0=2 < n ⇒×
候補
B[3]=1
B[0]=1
で既に使用済み⇒ n0=0 < n ⇒ ×
候補B[3]=2
n0=3 >= n ⇒
未使用なので割り当て可⇒
++n
を行い、次のn=4
の割り当てへ進むA-B( 名前 - 場所 ) の組み合わせ 2
1 4 0 2
配列
B 0 1 2 3 4
ここ
(n=4)
に入れる値を決める割り当て
B[4]=3
1 4 0 2 3
配列
B A-C
組み合わせ列挙 へ進むバックトラック
: -- n (n=3) 1 4 0 3
配列
B 0 1 2 3 4
候補
B[3]=3
他に可能な割り当てなしA-B( 名前 - 場所 ) の組み合わせ 3
0 1 2 3 4
配列B 0 1 2 3 4 0 1 2 4 3 0 1 3 2 4 0 1 3 4 2 0 1 4 2 3 0 1 4 3 2 0 2 1 3 4 0 2 1 4 3 0 2 3 1 4
組み合わせが 得られる順
int EnumerateC( void ){
int n, n0;
n = 0;
C[n] = -1;
while( 1 ){
C[n]++;
if( C[n] >= 5 ){
if( -- n < 0 ) break;
}else{ /* C[n]
が割り当て済みの値でないか*/
for( n0 = 0 ; n0 < n ; n0++ ){
if( C[n] == C[n0] ) break;
} if( n0 < n ) continue; /* C[n]
は割り当てできない*/
if( n == 4 ){ /* C
割り当て完了*/
if( CheckAssignment() ) return 1;
}else{
C[++n] = -1;
} }
} return 0;
}
A-B-C
間組み合わせが得られたので条件に矛盾 しないか検査する
A-C
間組み合わせ列挙A-C
間組み合わせを全て 調べたら0
を返す解候補 ( 組み合わせ ) の検査 1
3
つの割り当ての組み合わせ 名前×場所、名前×色、場所×色
3
つのint
型2
次元配列で条件を表すint AB[5][5];
int AC[5][5];
int BC[5][5];
A:
名前、B:
場所A:
名前、C:
色B:
場所、C:
色 要素の値1:
確定している割り当て-1:
ありえない割り当て0:
どちらでもない解候補 ( 組み合わせ ) の検査 2
条件違反の検出int i, j, k;
for( i=0 ; i<5 ; i++ ){
for( j=0 ; j<5 ; j++ ){
if( AB[i][j] > 0 && B[i] != j ) return 0;
if( AC[i][j] > 0 && C[i] != j ) return 0;
if( AB[i][j] < 0 && B[i] == j ) return 0;
if( AC[i][j] < 0 && C[i] == j ) return 0;
} }
名前
i
は場所j
矛盾B[i] != j
名前
i
は色j
でない 矛盾C[i] == j
解候補 ( 組み合わせ ) の検査 3
複合条件違反の検出for( i=0 ; i<5 ; i++ ){
for( k=0 ; k<5 ; k++ ){
if( B[k] == i ) break;
} for( j=0 ; j<5 ; j++ ){
if( BC[i][j] > 0 && C[k] != j ) return 0;
if( BC[i][j] < 0 && C[k] == j ) return 0;
} }
場所
i
は色j
矛盾C[k] != j (
名前k
は色j
でない)
名前k
は場所i
場所
i
は色j
でない 矛盾C[k] == j (
名前k
は色j)
int CheckAssignment( void ) { int i, j, k;
for( i=0 ; i<5 ; i++ ){
for( j=0 ; j<5 ; j++ ){
if( AB[i][j] > 0 && B[i] != j ) return 0;
if( AC[i][j] > 0 && C[i] != j ) return 0;
if( AB[i][j] < 0 && B[i] == j ) return 0;
if( AC[i][j] < 0 && C[i] == j ) return 0;
} }
for( i=0 ; i<5 ; i++ ){
for( k=0 ; k<5 ; k++ ){
if( B[k] == i ) break;
} for( j=0 ; j<5 ; j++ ){
if( BC[i][j] > 0 && C[k] != j ) return 0;
if( BC[i][j] < 0 && C[k] == j ) return 0;
} }
return 1;
}
A-B-C
間組み合わせ検査違反・矛盾のない組み合わせ
与えられた条件の いずれかに違反
矛盾
int EnumerateC( void ){
int n, n0;
n = 0;
C[n] = -1;
while( 1 ){
C[n]++;
if( C[n] >= 5 ){
if( -- n < 0 ) break;
}else{ /* C[n]
が割り当て済みの値でないか*/
for( n0 = 0 ; n0 < n ; n0++ ){
if( C[n] == C[n0] ) break;
} if( n0 < n ) continue; /* C[n]
は割り当てできない*/
if( n == 4 ){ /* C
割り当て完了*/
if( CheckAssignment() ) return 1;
}else{
C[++n] = -1;
} }
} return 0;
}
A-B-C
間組み合わせが得られたので条件に矛盾 しないか検査する
A-C
間組み合わせ列挙A-C
間組み合わせを全て 調べたら0
を返すint B[5], C[5];
int n, n0;
n = 0;
B[n] = -1;
while( 1 ){
B[n]++;
if( B[n] >= 5 ){
if( -- n < 0 ) break;
}else{ /* B[n]
が割り当て済みの値でないか*/
for( n0 = 0 ; n0 < n ; n0++ ){
if( B[n] == B[n0] ) break;
} if( n0 < n ) continue; /* B[n]
は割り当てできない*/
if( n == 4 ){ /* B
割り当て完了*/
if( EnumerateC() ) break;
}else{
B[++n] = -1;
} } }
A-C
間組み合わせを列挙A-B
間組み合わせ列挙以下の
B[n]++
と組み合わせてB[n]=0
から開始するようにする問題の入力
こういち(0):
ボクは白い傘(0)
を忘れたん だけど、場所は塾(1)
ではないよ。
方法1:
プログラムの先頭に書く方法
2:
データファイルを読み込むAC[0][0] = 1;
AB[0][1] = -1;
こういち(A:0)
、白(C:0)
こういち(A:0)
、塾(B:1)
どのようにデータとしてプログラムに入力するか
新しい問題のたびに、
プログラムの再コンパイルが必要
データファイルの記述ルール
こういち(A0):
ボクは白い傘(C0)
を忘れた んだけど、場所は塾(B1)
ではないよ。
あさこ(A1):
バス(B4)
に傘を置き忘れちゃっ た。黒い傘(C4)
は私のじゃないよ。
しょうご(A3):
黒い傘(C4)
を学校(B0)
に置 き忘れた人はいないよ。A0 and C0 A0 not B1 A1 and B4 A1 not C4
C4 not B0
残りの条件も同様に記述こういち
(A0)
は白い(C0)
傘あさこ
(A1)
は黒い(C4)
傘でないファイル
‘data.txt’
に保存データファイルの読み出し
fopen
で開き、fclose
で閉じるchar buf[256], *p;
FILE *fp;
fp = fopen( "data.txt", "r" );
while( 1 ){
fgets( buf, 256, fp );
if( feof(fp) ) break;
…/*
データを処理*/
}
fclose( fp );
ファイルを読み出し
(read)
モードで開くファイルが終了
(End-Of-File)
したら ループを抜け出し ファイルが不要になったら閉じる1
行読み出し読み出したデータを処理 (1)
int A,B,C,nA,nB,nC,n,logic;
char c;
fgets( buf, 256, fp );
if( feof(fp) ) break;
A = B = C = 0;
p = strtok( buf, " " );
c = *p++;
n = atoi(p);
switch( c ){
case 'A': A = 1; nA = n; break;
case 'B': B = 1; nB = n; break;
default: C = 1; nC = n; break;
}
p
が指す先頭文字を変数c
に代入 さらに、p
を1
増やすbuf: " A0 and C0 "
p → "A0"
p → "0"
p
が指す文字列を10
進数に変換 最初の項目 を記録読み出したデータを処理 (2)
/*
前ページから続く*/
p = strtok( NULL, " " );
if( *p == 'n' ) logic = -1;
else logic = 1;
p = strtok( NULL, " " );
c = *p++;
n = atoi(p);
switch( c ){
case 'A': A = 1; nA = n; break;
case 'B': B = 1; nB = n; break;
default: C = 1; nC = n; break;
} if( A && B ) AB[nA][nB] = logic;
if( A && C ) AC[nA][nC] = logic;
if( B && C ) BC[nB][nC] = logic;
p → "C0"
2
番目の項目 を記録p → "and"
‘and’
と‘not’
を区別buf: " A0 and C0 "
条件として
配列を初期化
文字列を扱う関数
トークン切り出しp = strtok( buf, " " ) ;
1
番目の引数(char
型配列)
を2
番目の引数の 文字で複数の部分文字列に切り分ける。最初の部分文字列を指すポインタを返す。
p = strtok( NULL, " " ) ;
直前に
strtok
で切り分けた部分文字列のうち、次の部分文字列を指すポインタを返す。
利用するには
#include <string.h>
が必要
例
p0 = strtok( "A0 and C2", " " ) ; p1 = strtok( NULL, " " ) ;
p2 = strtok( NULL, " " ) ;
p0 → "A0"
p1 → "and"
p2 → "C2"
文字列を扱う関数
ファイルから1
行読み出し
文字列⇒
整数変換char buf[256];
fgets( buf, 256, fp );
ファイル
fp
から改行で区切られた1
行を読み出し、char
型配列に記録する読み出し最大文字数を指定する
int n;
n = atoi(buf);
文字列が表す
10
進数を整数値に変換する 利用するには#include <stdlib.h>
が必要
Copyright © 2008 Kazuhito Ito
問題 : 5 人の話
そうた:
ボクはジャガーズに入っています。野 球のチームではありません。
こうじ:
リーブズはバスケットボールのチーム ですが、ボクはそのチームにはいません。
まさし:
私はラグビーをやっています。
あつし:
プラネッツはサッカーのチームです。でもボクはプラネッツでもブルーズでもないよ。
よしと:
スパローズは野球のチームではない し、ボクも野球のチームには属していません。他にスポーツの種類としてバレーボール
出典
:
朝日新聞データファイルを作る
名前(A)
0:
そうた、1:
こうじ、2:
まさし、3:
あつし、4:
よしと
チーム名(B)
0:
ジャガーズ、1:
リーブズ、2:
プラネッツ、3:
ブルーズ、4:
スパローズ
スポーツの種類(C)
0:
野球、1:
バスケットボール、2:
ラグビー、3:
サッカー、4:
バレーボールA0 and B0
A0 not C0
B1 and C1
A1 not B1
A2 and C2
B2 and C3
A3 not B2
A3 not B3
B4 not C0
A4 not C0
実行結果
× × × × ○ |○ × × × × |
○ × × × × |× × × ○ × |
× × ○ × × |× × × × ○ |
× ○ × × × |× ○ × × × |
× × × ○ × |× × ○ × × | ---|---
× × × × ○ |
× ○ × × × |
× × × ○ × |
○ × × × × |
× × ○ × × | ---
チーム スポーツの種類
名前チーム そうた
=
ジャガーズ=
バレーB
こうじ
=
ブルーズ=
野球まさし
=
スパローズ=
ラグビー あつし=
リーブズ=
バスケットB
よしと=
プラネッツ=
サッカー答え合わせ
そうた
:
ボクはジャガーズに入っています。野球のチームではありません。
こうじ
:
リーブズはバスケットボールのチームですが、ボクはそのチームにはいません。
まさし
:
私はラグビーをやっています。 あつし
:
プラネッツはサッカーのチームです。でもボクはプラネッツでもブルーズでもないよ。
よしと
:
スパローズは野球のチームではないし、ボクも野球のチームには属していません。
そうた
=
ジャガーズ=
バレーボール こうじ=
ブルーズ=
野球まさし
=
スパローズ=
ラグビーあつし
=
リーブズ=
バスケットボールよしと
