C趣味程序百例(15)

48.新娘和新郞
49.委派任务
50.谁在说谎



48.新娘和新郞
    三对情侣参加婚礼，三个新郞为A、B、C，三个新娘为X、Y、Z。有人不知道谁和谁结婚，于是询问了六位新人中的三位，但听到的回答是这样的：A说他将和X结婚；X说她的未婚夫是C；C说他将和Z结婚。这人听后知道他们在开玩笑，全是假话。请编程找出谁将和谁结婚。
*问题分析与算法设计
    将A、B、C三人用1,2，3表示，将X和A结婚表示为“X=1”，将Y不与A结婚表示为“Y!=1”。按照题目中的叙述可以写出表达式：
        x!=1        A不与X结婚
        x!=3        X的未婚夫不是C
        z!=3        C不与Z结婚
    题意还隐含着X、Y、Z三个新娘不能结为配偶，则有：
            x!=y且x!=z且y!=z
    穷举以上所有可能的情况，代入上述表达式中进行推理运算，若假设的情况使上述表达式的结果均为真，则假设情况就是正确的结果。
*程序与程序注释
#include<stdio.h>
void main()
{
    int x,y,z;
    for(x=1;x<=3;x++)          /*穷举x的全部可能配偶*/
        for(y=1;y<=3;y++)      /*穷举y的全部可能配偶*/
            for(z=1;z<=3;z++)    /*穷举z的全部可能配偶*/
                if(x!=1&&x!=3&&z!=3&&x!=y&&x!=z&&y!=z)  /*判定配偶是否满足题意*/
                {
                    printf("X will marry to %c.\n",'A'+x-1);    /*打印判定结果*/
                    printf("Y will marry to %c.\n",'A'+y-1);
                    printf("Z will marry to %c.\n",'A'+z-1);
                }
}
*运行结果
        X will marry to B.        (X与B结婚)
        Y will marry to C.        (Y与C结婚)
        Z will marry to A.        (Z与A结婚)

49.委派任务
    某侦察队接到一项紧急任务，要求在A、B、C、D、E、F六个队员中尽可能多地挑若干人，但有以下限制条件：
        1)A和B两人中至少去一人；
        2)A和D不能一起去；
        3)A、E和F三人中要派两人去；
        4)B和C都去或都不去；
        5)C和D两人中去一个；
        6)若D不去，则E也不去。
    问应当让哪几个人去？
*问题分析与算法设计 
    用A、B、C、D、E、F六个变量表示六个人是否去执行任务的状态，变量的值为1，则表示该人去；变量的值为0，则表示该人不参加执行任务，根据题意可写出表达式：
    a+b>1                A和B两人中至少去一人；
    a+d!=2               A和D不能一起去；
    a+e+f==2             A、E、F三人中要派两人去；
    b+c==0或b+c==2       B和C都去或都不去；
    c+d==1               C和D两人中去一个；
    d+e==0或d==1         若D不去，则E也不去(都不去；或D去E随便)。
    上述各表达式之间的关系为“与”关系。穷举每个人去或不去的各种可能情况，代入上述表达式中进行推理运算，使上述表达式均为“真”的情况就是正确的结果。
*程序与程序注释
#include<stdio.h>
void main()
{
    int a,b,c,d,e,f;
    for(a=1;a>=0;a--)           /*穷举每个人是否去的所有情况*/
        for(b=1;b>=0;b--)       /*1:去  0:不去*/
            for(c=1;c>=0;c--)
                for(d=1;d>=0;d--)
                    for(e=1;e>=0;e--)
                        for(f=1;f>=0;f--)
                            if(a+b>=1&&a+d!=2&&a+e+f==2
                                &&(b+c==0||b+c==2)&&c+d==1
                                &&(d+e==0||d==1))
                            {
                                printf("A will%s be assigned. \n",a?"":"not");
                                printf("B will%s be assigned. \n",b?"":"not");
                                printf("C will%s be assigned. \n",c?"":"not");
                                printf("D will%s be assigned. \n",d?"":"not");
                                printf("E will%s be assigned. \n",e?"":"not");
                                printf("F will%s be assigned. \n",f?"":"not");
                            }
}
*运行结果
        A will be assigned.         (去)
        B will be assigned.         (去)
        C will be assigned.         (去)
        D will not be assigned.     (不去)
        E will not be assigned.     (不去)
        F will be assigned.         (去)

*思考题
    某参观团按以下条件限制从A、B、C、D、E五个地方中选若干参观点：
        1)如去A，则必须去B；
        2)D、E两地只能去一地；
        3)B、C两地只能去一地；
        4)C、D两地都去或都不去；
        5)若去E地，A、D也必去。
    问该团最多能去哪几个地方？

50.谁在说谎
    张三说李四在说谎，李四说王五在说谎，王五说张三和李四都在说谎。现在问：这三人中到底谁说的是真话，谁说的是假话？
*问题分析与算法设计
    分析题目，每个人都有可能说的是真话，也有可能说的是假话，这样就需要对每个人所说的话进行分别判定。假设三个人所说的话的真假用变量A、B、C表示，等于1表示该人说的是真话； 表示这个人说的是假话。由题目可以得到：
    *张三说李四在说谎                张三说的是真话：a==1&&b==0
                                或   张三说的是假话：a==0&&b==1
    *李四说王五在说谎                李四说的是真话：b==1&&c==0
                                或   李四说的是假话：b==0&&c==1
    *王五说张三和李四都在说谎        王五说的是真话：c==1&&a+b==0
                                或   王五说的是假话：c==0&&a+b!=0
    上述三个条件之间是“与”的关系。将表达式进行整理就可得到C语言的表达式：
    (a&&!b||!a&&b)&&(b&&!c||!b&&c)&&(c&&a+b==0||!c&&a+b!=0)
    穷举每个人说真话或说假话的各种可能情况，代入上述表达式中进行推理运算，使上述表达式均为“真”的情况就是正确的结果。
*程序与程序注释
#include<stdio.h>
void 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&&!b||!a&&b)&&(b&&!c||!b&&c)&&(c&&a+b==0||!c&&a+b!=0))
                {
                    printf("Zhangsan told a %s.\n",a?"truth":"lie");
                    printf("Lisi told a %s.\n",b?"truch":"lie");
                    printf("Wangwu told a %s.\n",c?"truch":"lie");
                }
}
*运行结果
    Zhangsan told a lie           (张三说假话)
    Lisi told a truch.            (李四说真话)
    Wangwu told a lie.            (王五说假话)