C趣味程序百例(16)

51.谁是窃贼
52.黑与白
53.迷语博士的难题(1)
54.迷语博士的难题(2)




51.谁是窃贼
    公安人员审问四名窃贼嫌疑犯。已知，这四人当中仅有一名是窃贼，还知道这四人中每人要么是老实的，要么总是说谎的。在回答公安人员的问题中：
        甲说：“乙没有偷，是丁偷的。”
        乙说：“我没有偷，是丙便的。”
        丙说：“甲没有偷，是乙偷的。”
        丁说：“我没有偷。”
    请根据这四人的答话判定谁是盗窃者。
*问题分析与算法设计
    假设A、B、C、D分别代表四个人，变量的值为1代表该人是窃贱。
    由题目已知：四人中仅有一名是窃贱，且这四个人中的每个人要么说真话，要么说假话，而由于甲、乙、丙三人都说了两句话：“X没偷，X偷了”，故不论该人是否说谎，他提到的两人中必有一人是小偷。故在列条件表达式时，可以不关心谁说谎，谁说实话。这样，可以列出下列条件表达式：
        甲说：”乙没有偷，是丁偷的。”        B+D=1
        乙说：“我没有偷，是丙偷有。”        B+C=1
        丙说：“甲没有偷，是乙偷的。”        A+B=1
        丁说：“我没有偷。”                  A+B+C+D=1
    其中丁只说了一句话，无法判定其真假，表达式反映了四人中仅有一名是窃贱的条件。
*程序与程序注释
#include<stdio.h>
void main()
{
    int i,j,a[4];
    for(i=0;i<4;i++)            /*假定只有第i个人为窃贱*/
    {
        for(j=0;j<4;j++)        /*将第i个人设置为1表示窃贱，其余为0*/
            if(j==i)a[j]=1;
            else a[j]=0;
        if(a[3]+a[1]==1&&a[1]+a[2]==1&&a[0]+a[1]==1)   /*判定条件是否成立*/
        {
            printf("The thief is  ");              /*成立*/
            for(j=0;j<=3;j++)                   /*输出计算结果*/
                if(a[j])printf("%c.",j+'A');
            printf("\n");
        }
    }
}
*运行结果
The thief is B.       (乙为窃贱。)

----------------------------------------------------

52.黑与白
    有A、B、C、D、E五人，每人额头上都帖了一张黑或白的纸。五人对坐，每人都可以看到其它人额头上的纸的颜色。五人相互观察后，
    A说：“我看见有三人额头上帖的是白纸，一人额头上帖的是黑纸。”
    B说：“我看见其它四人额头上帖的都是黑纸。”
    C说：“我看见一人额头上帖的是白纸，其它三人额头上帖的是黑纸。”
    D说：“我看见四人额头上帖的都是白纸。”
    E什么也没说。
    现在已知额头上帖黑纸的人说的都是谎话，额头帖白纸的人说的都是实话。问这五人谁的额头是帖白纸，谁的额头是帖黑纸？
*问题分析与算法设计
    假如变量A、B、C、D、E表示每个人额头上所帖纸的颜色，0 代表是黑色，1 代表是白色。根据题目中A、B、C、D四人所说的话可以总结出下列关系：
    A说： a&&b+c+d+e==3||!a&&b+c+d+e!=3
    B说： b&&a+c+d+e==0||!b&&a+c+d+e!=0
    C说： c&&a+b+d+e==1||!c&&a+b+d+e!=1
    D说： d&&a+b+c+e==4||!d&&a+b+c+e!=4
    穷举每个人额头所帖纸的颜色的所有可能的情况，代入上述表达式中进行推理运算，使上述表达式为“真”的情况就是正确的结果。
*程序与程序注释
#include<stdio.h>
void main()
{
    int a,b,c,d,e;
    for(a=0;a<=1;a++)            /*黑色：0   白色：1*/
        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 is pasted a piece of %s paper on his forehead.\n",
                                                            a?"white":"black");
                            printf("B is pasted a piece of %s paper on his forehead.\n",
                                                            b?"white":"black");
                            printf("C is pasted a piece of %s paper on his forehead.\n",
                                                            c?"white":"black");
                            printf("D is pasted a piece of %s paper on his forehead.\n",
                                                            d?"white":"black");
                            printf("E is pasted a piece of %s paper on his forehead.\n",
                                                            e?"white":"black");
                       }
}

*运行结果
    A is pasted a paper of black paper on his forehead.         (黑)
    B is pasted a paper of black paper on his forehead.         (黑)
    C is pasted a paper of white paper on his forehead.         (白)
    D is pasted a paper of black paper on his forehead.         (黑)
    E is pasted a paper of white paper on his forehead.         (白)

-------------------------------------------------------------

53.迷语博士的难题(1)
    老实族和说谎族是来自两个荒岛的不同民族，老实族的人永远说真话，而说谎族的人永远说假话。迷语博士是个聪明的人，他要来判定所碰到的人是来自哪个民族的。
    迷语博士碰到三个人，知道他们可能是来自老实族或说谎族的。为了调查这三个人是什么族的，博士分别问了他们的问题，这是他们的对话：
    问第一个人：“你们是什么族？”，答：“我们之中有两个来自老实族。”第二个人说：“不要胡说，我们三个人中只有一个是老实族的。”第三个人听了第二个人的话后说：“对，就是只有一个老实族的。”
    请根据他的回答判定他们分别是哪个族的。
*问题分析与算法设计
    假设这三个人分别为A、B、C，若说谎其值为0，若老实，其值为1。根据题目中三个人的话可分别列出：
        第一个人： 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>
void main()
{
    int a,b,c;
    for(a=0;a<=1;a++)       /*穷举每个人是说谎还是老实的全部情况*/
        for(b=0;b<=1;b++)    /*说谎：0   老实：1*/
            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("A is a %s.\n",a?"honest":"lier");    /*输出判定结果*/
                    printf("B is a %s.\n",b?"honest":"lier");
                    printf("C is a %s.\n",c?"honest":"lier");
                }
}
*运行结果
    A is a lier      (说谎族)
    B is a lier      (说谎族)
    C is a lier      (说谎族)

*思考题
    迷语博士碰到四个人，知道他们可能是来自老实族和说谎族的。为了调查这四个人是什么族的，博士照例进行询问：”你们是什么族的？“
    第一人说：”我们四人全都是说谎族的。“
    第二人说：”我们之中只有一人是说谎族的。“
    第三人说：”我们四人中有两个是说谎族的。“
    第四人说：”我是老实族的。“
问自称是“老实族”的第四个人是否真是老实族的？
    (答案：第四个人是老实族的。)

------- ---------------------------------------------------

54.迷语博士的难题(2)
    两面族是荒岛上的一个新民族，他们的特点是说话真一句假一句且真假交替。假如第一句为真，则第二句是假的；假如第一句为假的，则第二句就是真的，但是第一句是真是假没有规律。
    迷语博士碰到三个人，知道他们分别来自三个不同的民族：老实族、说谎族和两面族。三人并肩站在博士前面。
    博士问左边的人：“中间的人是什么族的？”，左边的人回答：“老实族的”。
    博士问中间的人：“你是什么族的？”，中间的人回答：“两面族的”。
    博士问右边的人：“中间的人究竟是什么族的？”，右边的人回答：“说谎族的”。
    请问：这三个人都是哪个民族的？
*问题分析与算法设计
    这个问题是两面族问题中最基本的问题，它比前面只有老实族和说谎族的问题要复杂。解题时要使用变量将这三个民族分别表示出来。
    令：变量A=1表示：左边的人是老实族的(用C语言表示为A)；
        变量B=1表示：中间的人是老实族的(用C语言表示为B)；
        变量C=1表示：右边的人是老实族的(用C语言表示为C)；
        变量AA=1表示：左边的人是两面族的(用C语言表示为AA)；
        变量BB=1表示：中间的人是两面族的(用C语言表示为BB)；
        变量CC=1表示：右边的人是两面族的(用C语言表示为CC)；
    则左边的人是说谎族可以表示为：A!=1且AA!=1        (不是老实族和两面族的人)
                用C语言表示为：!A&&!AA
      中间的人是说谎族可以表示为：B!=1且BB!=1
                用C语言表示为：!B&&!BB
      右边的人是说谎族可以表示为：C!=0且CC!=1
                用C语言表示为：!C&&!CC
    根据题目中“三人来自三个民族”的条件，可以列出：
    a+aa!=2&&b+bb!=2&&c+cc!=2 且 a+b+c==1&&aa+bb+cc==1
    根据左边人的回答可以推出：若他们是老实族，则中间的人也是老实族；若他不是老实族，则中间的人也不是老实族。以上条件可以表示为：
    c&&!b&&!bb||(!c&&!cc)&&(b||bb)||!c&&cc
    将全部逻辑条件联合在一起，利用穷举的方法求解，凡是使上述条件同时成立的变量取值就是题目的答案。
*程序与程序注释
#include<stdio.h>
void main()
{
    int a,b,c,aa,bb,cc;
    for(a=0;a<=1;a++)            /*穷举全部情况*/
      for(b=0;b<=1;b++)
        for(c=0;c<=1;c++)
          for(aa=0;aa<=1;aa++)
            for(bb=0;bb<=1;bb++)
              for(cc=0;cc<=1;cc++)
                if(a+aa!=2&&b+bb!=2&&c+cc!=2&&       /*判定逻辑条件*/
                    a+b+c==1&&aa+bb+cc==1   &&
                    (a&&!aa&&b&&!bb||!a&&!b)&&
                      !b                    &&
                    (c&&!b&&!bb||(!c&&!cc)&&(b||bb)||!c&cc))
                {
                  printf("The man stand on left is a %s.\n",
                          aa?"double--dealer":(a?"honest":"lier"));
                  printf("The man stand on left is a %s.\n",
                          bb?"double--dealer":(b?"honest":"lier"));
                  printf("The man stand on left is a %s.\n",
                          cc?"double--dealer":(c?"honest":"lier"));    
                                                          /*输出最终的推理结果*/
                }
}
*运行结果
    The man stand on left is a double--dealer.       (左边的人是两面族的)
    The man stand on center is a lier.               (中间的人是说谎族的)
    The man stand on right is a honest.              (右边的人是老实族的)

*思考题
    迷语博士碰到三个人，便问第一个人：“你是什么族的？”，回答：“老实族的。”问第二个人：“你是什么族的？”，答：“说谎族的。”博士又问第二个人：“第一个人真的是老实族的吗？”，答：“是的。”问第三个人：“你是什么族的？”，答：“老实族的。”博士又问第三个人：“第一个人是什么族的？”，答：“两面族的。”
    请判定这个人到底是哪个民族的？
    (答案：第一个人是老实族的，第二个人是两面族的，第三人是说谎族。)