C語言誰是竊賊問題程式碼及解析
問題描述
警察審問4名竊賊嫌疑犯。現在已知,這4人當中僅有一名是竊賊,還知道這4個人中的每個人要麼是誠實的,要麼總是說謊。
這4個人給警察的回答如下。
- 甲說:“乙沒有偷,是丁偷的。”
- 乙說:“我沒有偷,是丙偷的。”
- 丙說:“甲沒有偷,是乙偷的。”
- 丁說:“我沒有偷。”
請根據這4個人的回答判斷誰是竊賊。
問題分析
顯然該題是一個邏輯推斷問題。已知4個人中的每個人要麼是誠實的,要麼總是說謊,那麼如何來判斷他們到底誰是竊賊呢?
由問題描述可知,甲、乙、丙、丁4人中僅有一名竊賊,且這4個人中每個人要麼是誠實的,要麼總是說謊。分析甲、乙、丙3人所說的話可以發現,他們每人都說了兩句話,即:“X沒有偷,是Y偷的(其中,X、Y指代甲、乙、丙、丁中的某一個)”,因此,不論這3人是否說謊,他們所提到的這兩個人中必有一個是竊賊。而丁只說了他自己沒有偷,所以無法判斷其真假。
假設用變數A、B、C、D分別代表4個人,變數的值為1代表該人是竊賊,則根據4個人的說法可列出下面的4個條件:
- 甲說:“乙沒有偷,是丁偷的。” —— B+D=1 ①
- 乙說:“我沒有偷,是丙偷的。” —— B+C=1 ②
- 丙說:“甲沒有偷,是乙偷的。” —— A+B=1 ③
- 丁說:“我沒有偷。” —— A+B+C+D=1 ④
由於甲、乙、丙3人的話中都提到了2個人,其中必有一人是小偷,所以在根據他們的話列出條件表示式時,可以不關心誰說的是真話,誰說的是假話。
由於丁的話無法判斷真假,所以根據丁的話列出的表示式只反映了4人中僅有一名是竊賊的條件。
演算法設計
該問題的關鍵是使用C語言中的邏輯表示式將問題分析中得到的4個條件表達出來,邏輯表示式如下:
B+D==1 && B+C==1 && A+B==1 ⑤
條件④表示A、B、C、D中必有一個為1。
在程式中可依次假定甲、乙、丙、丁分別為竊賊,帶入⑤進行測試,滿足條件⑤的那個人為竊賊,具體如下:
- 先假定甲為竊賊,即A=1,B=0,C=0,D=0,帶入條件⑤測試是否成立,若成立則不再對乙、丙、丁進行測試。
- 若不成立,則再假定乙為竊賊,即A=0,B=1,C=0,D=0,帶入條件⑤測試是否成立,若成立則可確定乙為竊賊,不再對丙、丁進行測試。
- 若不成立,再假定丙為竊賊,即A=0,B=0,C=1,D=0,帶入條件⑤測試是否成立,若成立則可確定丙為竊賊,不再對丁進行測試。
- 若不成立,再假定廠為竊賊,即A=0,B=0,C=0,D=1,帶入條件⑤測試是否成立,若成立則確定丁為竊賊。
下面是完整的程式碼:
#include<stdio.h>
int main()
{
int i, A=1, B=0, C=0, D=0; /*先假定甲是竊賊*/
for(i=1; i<=4; i++)
if(B+D==1 && B+C==1 && A+B==1) /*測試甲乙丙丁誰是竊賊,符合該條件的即為竊賊*/
break;
else
{
if(i == 1)
{
A=0; /*甲不是竊賊,測試乙是否是竊賊*/
B=1;
}
if(i == 2)
{
B=0; /*甲乙均不是竊賊,測試丙是否是竊賊*/
C=1;
}
if(i == 3)
{
C=0; /*甲乙丙都不是竊賊,測試丁是否是竊賊*/
D=1;
}
}
/*輸出結果*/
printf("判斷結果:\n");
if(i == 1)
printf("甲是竊賊\n");
if(i == 2)
printf("乙是竊賊\n");
if(i == 3)
printf("丙是竊賊\n");
if(i == 4)
printf("丁是竊賊\n");
return 0;
}
執行結果:
判斷結果:
乙是竊賊
Linux公社的RSS地址 : https://www.linuxidc.com/rssFeed.aspx
本文永久更新連結地址: https://www.linuxidc.com/Linux/2019-01/156479.htm