C语言谜语博士的难题

谜语博士遇到了两个难题，先看第一个难题。

谜语博士的难题（一）

问题描述

诚实族和说谎族是来自两个岛屿的不同民族，已知诚实族的人永远说真话，而说谎族的人永远说假话。

一天，谜语博士遇到3个人，知道他们可能是来自诚实族或说谎族的。为了调查这3个人到底来自哪个族，博士分别问了他们问题，下面是他们的对话：

• 博士问：“你们是什么族的？ ”
• 第1个人回答说：“我们之中有2个来自诚实族。”
• 第2个人说：“不要胡说，我们3个人中只有一个是来自诚实族的。”
• 第3个人接着第2个人的话说：“对，确实只有一个是诚实族的。”

请根据他们的回答编程判断出他们分别是来自哪个族的。

问题分析

假设这3个人分别用d、B、C这3个变量来代表，若某个人说谎则其对应的变量值为0,若诚实则其对应的变量值为1，根据题目中这3个人的话分析如下：

(1) 第1个人回答说：“我们之中有两个来自诚实族。”

因此如果第一个人（用A代表第一个人）说的是真话，则A来自诚实族，另两个人中一个来自诚实族，一个来自说谎族。则有表达式：

A&&A+B+C==2

如果A说的是假话，则A来自说谎族，A的话也一定是假话，因此3个人中来自诚实族的人必定不是两个。则有表达式：

!A&&A+B+C!=2

(2) 第2个人说：“不要胡说，我们3个人中只有一个是来自诚实族的。”

如果第2个人（用B来代表第2个人）说的是真话，则B来自诚实族，而另两个人都来自说谎族。则有表达式：

B&&A+B+C==1

如果第2个人B说的是假话，则B来自说谎族，且3个人中来自诚实族的人数必定不是一个。则有表达式：

!B&&A+B+C!=1

(3) 第3个人说：“对，确实只有一个是诚实族的。”

如果第3个人（用C代表第3个人）说的是真话，则C来自诚实族，另两个人都来自说谎族。则有表达式：

C&&A+B+C==1

如果C说的是假话，则C来自说谎族，且有表达式：

!C&&A+B+C!=1

算法设计

在问题分析中已经列出了各种可能情况，接下来就可以使用穷举法来获得最终的判断结果了。

下面使用C语言中的逻辑表达式将问题分析中得到的6个条件表达出来，逻辑表达式如下：

(A&&A+B+C==2 || !A&&A+B+C!=2) &&
(B&&A+B+C==1 || !B&&A+B+C!=1) &&
(C&&A+B+C==1 || !C&&A+B+C!=1)

在程序中穷举每个人的各种可能情况，并代入上面的逻辑表达式中进行推理运算，能使该逻辑表达式的值为真的结果就是正确的结果。

下面的是完整代码：

#include<stdio.h>
int main()
{
    int A, B, C;
    {
        for(A=0; A<=1; A++)
            for(B=0; B<=1; B++)
                for(C=0; C<=1; C++)
                    if( (A && A+B+C==2 || !A && A+B+C!=2) &&
                        (B && A+B+C==1 || !B && A+B+C!=1) &&
                        (C && A+B+C==1 || !C && A+B+C!=1) )
                    {
                        printf("第一个人来自%s\n",A?"诚实族":"说谎族");
                        printf("第二个人来自%s\n",B?"诚实族":"说谎族");
                        printf("第三个人来自%s\n",C?"诚实族":"说谎族");
                    }
    }
    return 0;
}

运行结果：
第一个人来自说谎族
第二个人来自说谎族
第三个人来自说谎族
知识点补充
还可以将上面程序中的逻辑判断条件分开判断，即使用多个if语句：

if(A && A+B+C==2 || !A && A+B+C!=2)
    if(B && A+B+C==1 || !B && A+B+C!=1)
        if(C && A+B+C==1 || !C && A+B+C!=1)

谜语博士的难题（二）

问题描述

两面族是岛屿上的一个新民族，他们的特点是说话时一句真话一句假话，真假交替。即如果第一句说的是真话，则第二句必为假话；如果第一句说的是假话，则第二句必然是真话。但第一句话到底是真是假却不得而知。

现在谜语博士碰到了3个人，这3个人分别来自3个不同的民族，诚实族、说谎族和两面族。谜语博士和这3个人分别进行了对话。

首先，谜语博士问左边的人：“中间的人是哪个族的？”，左边的人回答说：“是诚实族的”。

谜语博士又问中间的人：“你是哪个族的？”，中间的人回答说：“两面族的”。

最后，谜语博士问右边的人：“中间的人到底是哪个族的？”，右边的人回答说：“是说谎族的”。

现在请编程求出这3个人各自来自哪个族。

问题分析

由于现在不仅需要判断3个人的民族，而且这3个人还存在相对的位置关系，因此像谜语博士的难题(一）中那样简单的定义3个变量还不足以描述难题（二）中的情况。

首先还是用变量将3个民族表示出来，表示的时候还要考虑到他们之间的位置关系。可以采用如下方式来定义变量：

• 变量L=1：   表不左边的人来自诚实族
• 变量M=1：  表示中间的人来自诚实族
• 变量R=1：  表示右边的人来自诚实族
• 变量LL=1：  表示左边的人来自两面族
• 变量MM=1：表示中间的人来自两面族
• 变量RR=1： 表示右边的人来自两面族

根据上述变量定义方式，有：

• 左边的人来自说谎族：L!=1且LL!=1
• 中间的人来自说谎族：M!=1且MM!=1
• 右边的人来自说谎族：R!=1且RR!=1

从上述变量定义可以看到，为解决第二个难题，变量的数目已经变为6个。下面分析题目中谜语博士与3个人的对话。

根据题目中3个人的回答做分析如下。

(1) 左边的人说中间的人是诚实族的。

若左边的人说的是真话，则他来自诚实族，且中间的人也是诚实族的。这种情况可用表达式表达为：

L && !LL && M && !MM

上面表达式的含义为左边及中间的人是诚实族的同时，不可能是两面族的。

若左边的人说的是假话，则可以肯定他不是诚实族的，且中间的人也不是诚实族的。这种情况可用表达式表达为：

!L && !M

上面表达式的含义为左边及中间的人肯定不是诚实族的，但不能确定他们到底来自说谎族还是两面族。

综合起来，根据左边人的回答可得到逻辑表达式：

(L && !LL && M && !MM) || (!L && !M)

(2) 中间的人说自己是两面族的。

若中间的人说的是真话，则他来自两面族；若中间的人说的是假话，则他来自说谎族。因此，可以判断出，中间的人肯定不是诚实族的。这种情况可用表达式表达为：

!M

(3) 右边的人说中间的人是说谎族的。

若右边的人来自诚实族，则中间的人是说谎族的。这种情况可用表达式表达为：

R && !M && !MM

若右边的人来自两面族，则无法判断其话的真假，即无法确定中间的人来自哪个族。这种情况可用表达式表达为：

RR && !R

若右边的人来自说谎族，且中间的人不是说谎族的，而是诚实族或两面族的。这种情况可用表达式表达为：

!R && !RR && (M || MM)

综合起来，根据右边人的回答可得到逻辑表达式：

R && !M && !MM || (RR && !R) || (!R && !RR && (M || MM))

（4）由于题目中说“三个人分别来自三个不同的民族”，因此可以得出如下表达式：

L+LL != 2 && M+MM != 2 && R+RR != 2 且 L+M+R==1 && LL+MM+RR==1

算法设计

在问题分析中已经列出了各种可能情况，接下来仍然使用穷举法来获得最终的判断结果。

下面使用C语言中的逻辑表达式将问题分析中得到的全部逻辑条件表达出来，逻辑表达式如下：

(L && !LL && M && !MM || !L && !M) &&
!M &&
(R && !M && !MM || (RR && !R) ||
(!R && !RR && (M||MM)) ) &&
L+LL!=2 &&
M+MM!=2 &&
R+RR!=2 &&
L+M+R==1 &&
LL+MM+RR==1

在程序中穷举每个人的各种可能情况，并代入上面的逻辑表达式中进行推理运算，能使该逻辑表达式的值为真的结果就是正确的结果。

下面是完整的代码：

#include<stdio.h>
int main ()
{
    int L, M, R, LL, MM, RR;
    for(L=0; L<=1; L++)
        for (M=0; M<=1; M++)
            for(R=0; R<=1; R++)
                for(LL=0; LL<=1; LL++)
                    for(MM=0; MM<=1; MM++)
                        for(RR=0; RR<=1; RR++)
                            if( (L && !LL && M && !MM || !L && !M) &&
                                !M &&
                                (R && !M && !MM || (RR && !R) ||
                                (!R && !RR && (M||MM)) ) &&
                                L+LL!=2 &&
                                M+MM!=2 &&
                                R+RR!=2 &&
                                L+M+R==1 &&
                                LL+MM+RR==1
                            )
                            {
                                printf("左边的人来自%s\n",LL?"两面族":(L?"诚实族":"说谎族"));
                                printf("中间的人来自%s\n",MM?"两面族":(M?"诚实族":"说谎族"));
                                printf("右边的人来自%s\n",RR?"两面族":(R?"诚实族":"说谎族"));
                            }
    return 0;
}

运行结果：
左边的人来自两面族
中间的人来自说谎族
右边的人来自诚实族