プログラムの実行結果は以下の通り。
正直者の数が 5 人の場合
正直者が5人,嘘つきが5人の場合,どんな並びになっていても,他の人数の組み合わせの回答と一致する場合はない。
プログラムのソースは以下の通り。
#include "puzutl.h" map<string,int> pattern; // 答えのパターンと正直者の数(-1の場合,正直者の数は特定できなかった) YesNo unknown[11]; // YES:正直者の数が特定できない,NO:正直者の数は特定できている void ans( int user) { char ans[9+1/*NIL*/]; // 9人の質問の答え, Y:はい, N:いいえ YesNo honest; // 答える人は正直者? int num_honest = 0; // 10人中の正直者の数 for( int i=0; i< 9; i++) { // 先頭から9人に答えを聞く honest = user&1; // 次に答える人は正直者? if( honest) num_honest++; // 正直者の数を勘定する user >>= 1; // 次の人 if( honest) { // 正直者は「次の人は嘘つきか?」に対し正しく答える if( user&1) ans[i] = 'N'; // 次の人は正直者 else ans[i] = 'Y'; // 次の人は嘘つき } else { // 嘘つき,逆を答える if( user&1) ans[i] = 'Y'; // 次の人は正直者 else ans[i] = 'N'; // 次の人は嘘つき } } if( user&1) num_honest++; // 10番目の人は正直者? ans[i] = NIL; // 質問の答えをASCIZにする map<string,int>::iterator ite = pattern.find( ans); if( ite == pattern.end()) { // 初めて出現する答えのパターン pattern.insert( pair<string,int>(ans, num_honest)); } else { // 既に出現した答えのパターン if( (*ite).second != num_honest) { // 前回と答えのパターンが同じなのに正直者の数が異なる。 // ということはこのパターンでは正直者の数を確定できない。 unknown[(*ite).second]= YES; unknown[num_honest] = YES; (*ite).second = -1; // 特定できない } } } int main( int argc, cstring argv[]) { // 10人分の全てのパターンを洗い出す for( int user=0; user< 1024; user++) { ans( user); } // 正直者の数が0〜10までの可能性があるので調べてみる。 for( int i=0; i<= 10; i++) { if( unknown[i] == NO) ps( "正直者の数が %d 人の場合\n", i); // 正直者の数が特定できる場合 } return 0; }