C语言旅客国籍问题

问题描述

在一个旅馆中住着6个不同国籍的人，他们分别来自美国、德国、英国、法国、俄罗斯和意大利这几个国家。他们的名字分别叫A、B、C、D、E和F，要说明的是名字的顺序与前面提到的国籍不一定是相互对应的。现在已知：

• A和美国人是医生。
• E和俄罗斯人是教师。
• C和德国人是技师。
• B和F曾经当过兵，而德国人从未参过军。
• 法国人比A年龄大，意大利人比C年龄大。
• B同美国人下周要去西安旅行，而C同法国人下周要去杭州度假。

现要求根据上述已知条件，编程求出A、B、C、D、E和F各是哪国人。

问题分析

根据问题描述中给定的条件可进行如下的分析：

• 由“A和美国人是医生”可知A不是美国人。
• 由“E和俄罗斯人是教师”可知E不是俄罗斯人。
• 由“C和德国人是技师”可知C不是德国人。
• 又因为A的职业是医生，与俄罗斯人和德国人的职业不同，所以A不是俄罗斯人也不是德国人。E的职业是教师，与美国人和德国人的职业不同，所以E不是美国人也不是德国人。C的职业是技师，与美国人和俄罗斯人不同，所以C不是美国人也不是俄罗斯人。
• 由“B和F曾经当过兵，而德国人从未参过军”可知，B和F不是德国人。
• 由“法国人比A年龄大，意大利人比C年龄大”可知A不是法国人，C不是意大利人。
• 由“B同美国人下周要去西安旅行，而C同法国人下周要去杭州度假”可知，B不是美国人，也不是法国人，C不是法国人。

用条件矩阵将上面的分析结果表示出来：

	美国人	英国人	法国人	德国人	意大利人	俄罗斯人
A	0		0	0		0
B	0		0	0
C	0		0	0	0	0
D
E	0			0		0
F				0

根据上面的条件矩阵使用消去法，即可得到问题的结果。

算法设计

下面给出从条件矩阵初始化到完成消去得到结果的整个过程中条件矩阵每一步的变化，具体变化过程如下：

1) 初始化条件矩阵

状态(a)

2) 将问题分析中得出的结果在条件矩阵中表示出来，条件矩阵中为0的项表示不是该国的人。同时将条件矩阵中每一列的0号元素都置位用来表示该列尚未进行处理。

状态(b)

3) 第4列只有一个元素为非0，执行消去操作执行消去操作时，从只有一个元素为非0的列开始消去。

将条件矩阵中非零元素所在行的其他元素都置为0，同时置a[0][4]为0，表示条件矩阵中第4列已处理完毕。

状态(c)

4) 第1列只有一个元素为非0，执行消去操作。

显然，当条件矩阵位于状态（c）时，第1列中只有一个元素非0，可执行消去操作。

状态(d)

5) 第3列只有一个元素为非0，执行消去操作。

显然，当条件矩阵位于状态（d）时，第3列中只有一个元素非0，可执行消去操作。

状态(e)

6) 第6列只有一个元素为非0，执行消去操作。

显然，当条件矩阵位于状态（e）时，第6列中只有一个元素非0，可执行消去操作。

状态(f)

7) 第5列只有一个元素为非0，执行消去操作。

显然，当条件矩阵位于状态（f）时，第5列只有一个元素非0，可执行消去操作。

状态(g)

8) 第2列只有一个元素为非0，执行消去操作。

当条件矩阵位于（g）状态时，只有第2列还未被处理，经观察发现，该非0元素所在行（第3行）的所有其他元素都已经为0了，但在我们编程实现时，程序还是会对该行的每个元素都检查一遍。

状态(h)

执行消去操作后的矩阵状态（h）所示。该矩阵中除了第0列以外每列都只有一个元素非0，由此就可推断出A、B、C、D、E、F到底是哪国人。

下面是完整的代码：

#include <stdio.h>

int main()
{
    char *m[7]={" ","美国","英国","法国","德国","意大利","俄罗斯"};  /*国名*/
    int a[7][7], i, j, t, e, x, y;
    for(i=0; i<7; i++)  /*初始化条件矩阵*/
        for(j=0; j<7; j++)  /*行为人，列为国家，元素的值表示某人是该国人*/
            a[i][j]=j;
            for(i=1; i<7; i++)  /*条件矩阵每一列的第0号元素作为该列数据处理的标记*/
                a[0][i]=1;  /*标记该列尚未处理*/
                a[1][1]=a[2][1]=a[3][1]=a[5][1]=0;  /*输入条件矩阵中的各种条件*/
                a[1][3]=a[2][3]=a[3][3]=0;  /*0表示不是该国的人*/
                a[1][4]=a[2][4]=a[3][4]=a[5][4]=a[6][4]=0;
                a[3][5]=0;
                a[1][6]=a[3][6]=a[5][6]=0;
                while(a[0][1]+a[0][2]+a[0][3]+a[0][4]+a[0][5]+a[0][6]>0)
                {  /*当所有六列均处理完毕后退出循环*/
                    for(i=1; i<7; i++)  /*i:列坐标*/
                        if( a[0][i] ) /*若该列尚未处理，则进行处理*/
                        {
                            for(e=0,j=1; j<7; j++)  /*j:行坐标 e:该列中非0元素计数器*/
                                if( a[j][i] )
                                {  /*统计每列中的非0元素个数*/
                                    x=j;  /*x变量保存行坐标*/
                                    y=i;  /*y变量保存列坐标*/
                                    e++;
                                }
                            if( e==1 )  /*若该列只有一个元素为非零，则进行消去操作*/
                            {
                                for(t=1; t<7; t++)
                                    if( t!=i )
                                        a[x][t]=0;  /*将非零元素所在的行的其它元素置0*/
                                        a[0][y]=0;  /*设置该列已处理完毕的标记*/
                            }
                        }
                }
    printf("矩阵最终状态为：\n");
    for(i=0; i<7; i++)  /*初始化条件矩阵*/
    {
        for(j=0; j<7; j++)  /*行为人，列为国家，元素的值表示某人是该国人*/
            printf("%d ", a[i][j]);
            printf("\n");
            }
    printf("\n");
    printf("推断结果为：\n");
    for(i=1; i<7; i++)  /*输出推理结果*/
    {
        printf("%c来自",'A'-1+i);
        for(j=1; j<7; j++)
            if( a[i][j] != 0 )
            {
                printf("%s。\n", m[a[i][j]]);
                break;
            }
    }
    return 0;
}

运行结果：
矩阵最终状态为：
0 0 0 0 0 0 0
0 0 0 0 0 5 0
0 0 0 0 0 0 6
0 0 2 0 0 0 0
0 0 0 0 4 0 0
0 0 0 3 0 0 0
0 1 0 0 0 0 0

推断结果为：
A来自意大利。
B来自俄罗斯。
C来自英国。
D来自德国。
E来自法国。
F来自美国。