C語言每日一練——第74天：黑與白問題
C語言每日一練
2022年1月10日
題目描述
有A、B、C、D、E這5個人，每個人額頭上都帖了一張黑或白的紙。5人對坐，每個人都可以看到其他人額頭上紙的顏色。5人相互觀察後：
A說：「我看見有3人額頭上貼的是白紙，1人額頭上貼的是黑紙。」
B說：「我看見其他4人額頭上貼的都是黑紙。」
C說：「我看見1人額頭上貼的是白紙，其他3人額頭上貼的是黑紙 。」
D說：「我看見4人額頭上貼的都是白紙。」
E什麼也沒說。
現在己知額頭上貼黑紙的人說的都是謊話，額頭貼白紙的人說的都是實話。問這5人誰的額頭上貼的是白紙，誰的額頭上貼的是黑紙？
問題分析
個人思路：<僅供參考>
總共5個人，說話的只有4個，簡單分析我們可以得知：
4個人說的情況都不相同。A說看到3個人貼白紙，B看到0張白紙，C看到1張白紙，D看到4張白紙，假設他們說的都是真話，那麼他們4人所說的話對應的總白紙數依然不同（因為他們自己額頭上貼的都是白紙，並不會使其中兩人白紙總數相同）。
//4人貼白紙時，總白紙數
#define A_TRUE (3 + 1) //其他3人貼白紙，自己也貼白紙
#define B_TRUE (0 + 1)
#define C_TRUE (1 + 1)
#define D_TRUE (4 + 1)
所以我們可以得出一個隱藏條件——說話的4個人中只有1個人額頭上貼白紙，即只有一個人說的是真話。
利用上面這個條件，我們可以通過所有人額頭上的總白紙數來判斷哪個人說的是真話，例如：B額頭貼白紙，他說其他4人貼黑紙，在遍歷所有情況時，如果總白紙數為1，且只有B貼白紙時，可能就是正確情況。
為什麼說可能呢？由於每個人說的話中沒有考慮自己頭上的紙張顏色，所以可能會一種矛盾現象：
B額頭上貼了白紙，他看到其他4人都貼的是黑紙，C雖然頭上貼的的確是黑紙，但他的話是正確的：「我看見1人額頭上貼的是白紙，其他3人額頭上貼的是黑紙 」。這就和題目條件衝突了——額頭上貼黑紙的人說的都是謊話。
這樣一來，在遍歷時還需考慮當1個人貼白紙時，其他4個人都不能說真話這一條件，這一點依然可以通過總白紙數來判斷。例如：當遍歷到B說真話（額頭貼白紙）時，判斷5個人總白紙數是否等於A，C，D 3個人看到的白紙數（見下面的宏定義），如果有一個相等，說明該遍歷結果是錯誤的。
//4人貼黑紙時，總白紙數（假設它們仍然說真話）
#define A_FALSE (3) //自己貼黑紙，但說的是真話
#define B_FALSE (0)
#define C_FALSE (1)
#define D_FALSE (4)
程式實現上，定義a,b,c,d,e 5個變數，分別表示他們額頭上貼的紙張顏色，1表示白色。通過5層for迴圈，遍歷所以可能性，同時滿足上面兩種情況的，即為正確結果。
【注】我的思路可能推理得太深了，如果覺得處理得太麻煩，可以直接看下文網上參考的思路，該思路邏輯性更強，程式碼量更少。
程式碼實現
#include <stdio.h>
//4人貼白紙時，總白紙數
#define A_TRUE (3 + 1) //其他3人貼白紙，自己也貼白紙
#define B_TRUE (0 + 1)
#define C_TRUE (1 + 1)
#define D_TRUE (4 + 1)
//4人貼黑紙時，總白紙數（假設它們仍然說真話）
#define A_FALSE (3) //自己貼黑紙，但說的是真話
#define B_FALSE (0)
#define C_FALSE (1)
#define D_FALSE (4)
int main()
{
int A = 0, B = 0, C = 0, D = 0, E = 0;
int tmp = 0, flag = 0; //flag = 1表示找到正確結果
for(A = 0; A <= 1; A++)
for(B = 0; B <= 1; B++)
for(C = 0; C <= 1; C++)
for(D = 0; D <= 1; D++)
for(E = 0; E <= 1; E++)
{
//獲取貼白紙的人數
tmp = A + B + C + D + E;
flag = 0;
switch(tmp)
{
//4人只有A貼白紙，且貼黑紙的人說的話不能為真
case A_TRUE: if(A && !B && !C && !D &&
tmp != B_FALSE &&
tmp != C_FALSE &&
tmp != D_FALSE)
flag = 1;
break;
//4人只有B貼白紙，且貼黑紙的人說的話不能為真
case B_TRUE: if(B && !A && !C && !D &&
tmp != A_FALSE &&
tmp != C_FALSE &&
tmp != D_FALSE)
flag = 1;
break;
//4人只有C貼白紙，且貼黑紙的人說的話不能為真
case C_TRUE: if(C && !A && !B && !D &&
tmp != A_FALSE &&
tmp != B_FALSE &&
tmp != D_FALSE)
flag = 1;
break;
//4人只有D貼白紙，且貼黑紙的人說的話不能為真
case D_TRUE: if(D && !A && !B && !C &&
tmp != A_FALSE &&
tmp != B_FALSE &&
tmp != C_FALSE)
flag = 1;
break;
}
if(flag)
{
printf("A貼%s\n", A ? "白紙" : "黑紙");
printf("B貼%s\n", B ? "白紙" : "黑紙");
printf("C貼%s\n", C ? "白紙" : "黑紙");
printf("D貼%s\n", D ? "白紙" : "黑紙");
printf("E貼%s\n", E ? "白紙" : "黑紙");
}
}
return 0;
}
執行結果
後期完善
既然然已經推理出了A、B、C、D 4個人中只有一個人額頭貼白紙，這時只需用一個for迴圈就能遍歷出4個人中誰貼了白紙，迴圈次數為4次（0~3），分別表示A、B、C、D，這樣可以減少一些無效的迴圈次數。
#include <stdio.h>
//4人貼白紙時，總白紙數
#define A_TRUE (3 + 1) //其他3人貼白紙，自己也貼白紙
#define B_TRUE (0 + 1)
#define C_TRUE (1 + 1)
#define D_TRUE (4 + 1)
//4人貼黑紙時，總白紙數（假設它們仍然說真話）
#define A_FALSE (3) //自己貼黑紙，但說的是真話
#define B_FALSE (0)
#define C_FALSE (1)
#define D_FALSE (4)
int main()
{
//i表示A,B,C,D 4個人哪個貼白紙，j表示E是否貼白紙
int i = 0, j = 0;
int tmp = 0, flag = 0; //flag = 1表示找到正確結果
for(i = 0; i < 4; i++)
for(j = 0; j <= 1; j++)
{
flag = 0;
tmp = 1 + j; //總白紙數
switch(i)
{
//A說的是真話，其他人說假話？
case 0: if(tmp == A_TRUE && tmp != B_FALSE &&
tmp != C_FALSE && tmp != D_FALSE)
flag = 1; break;
//B說的是真話，其他人說假話？
case 1: if(tmp == B_TRUE && tmp != A_FALSE &&
tmp != C_FALSE && tmp != D_FALSE)
flag = 1; break;
//C說的是真話，其他人說假話？
case 2: if(tmp == C_TRUE && tmp != A_FALSE &&
tmp != B_FALSE && tmp != D_FALSE)
flag = 1; break;
//D說的是真話，其他人說假話？
case 3: if(tmp == D_TRUE && tmp != A_FALSE &&
tmp != B_FALSE && tmp != C_FALSE)
flag = 1; break;
}
if(flag)
{
printf("A貼%s\n", i == 0 ? "白紙" : "黑紙");
printf("B貼%s\n", i == 1 ? "白紙" : "黑紙");
printf("C貼%s\n", i == 2 ? "白紙" : "黑紙");
printf("D貼%s\n", i == 3 ? "白紙" : "黑紙");
printf("E貼%s\n", j == 1 ? "白紙" : "黑紙");
}
}
return 0;
}
網上參考
原文連結：http://c.biancheng.net/cpp/html/3357.html
原文部分思路：
我的思路有一個很大的缺點，那就是花太多心思去推理了（推理過深），好處就是理解起來會好一點。這份程式碼通過邏輯表示式的方法，一個if語句就得出了結果，優點是邏輯性強，程式碼量少，不過理解起來可能需要一定的邏輯思維能力
#include<stdio.h>
int main()
{
int a, b, c, d, e; /*0表示黑色，1表示白色*/
for(a=0; a<=1; a++) /*窮舉五個人額頭帖紙顏色的全部可能*/
for(b=0; b<=1; b++)
for(c=0; c<=1; c++)
for(d=0; d<=1; d++)
for(e=0; e<=1; e++)
if( (a&&b+c+d+e==3 || !a&&b+c+d+e!=3) &&
(b&&a+c+d+e==0 || !b&&a+c+d+e!=0) &&
(c&&a+b+d+e==1 || !c&&a+b+d+e!=1) &&
(d&&a+b+c+e==4 || !d&&a+b+c+e!=4)
)
{
printf("A額頭上的貼紙是%s色的.\n",a?"白":"黑");
printf("B額頭上的貼紙是%s色的.\n",b?"白":"黑");
printf("C額頭上的貼紙是%s色的.\n",c?"白":"黑");
printf("D額頭上的貼紙是%s色的.\n",d?"白":"黑");
printf("E額頭上的貼紙是%s色的.\n",e?"白":"黑");
}
return 0;
}