区分旅客国籍

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

1)A和美国人是医生。

2)E和俄罗斯人是教师。

3)C和德国人是技师。

4)B和F曾经当过兵，而德国人从未参过军。

5)法国人比A年龄大；意大利人比C年龄大。

6)B同美国人下周要去西安旅行，而C同法国人下周要去杭州度假。

试问由上述已知条件，A、B、C、D、E和F各是哪国人？

分析可得以下条件矩阵：

.
美(医生)
英
法
德(技师)
意大利
俄(教师)
A(医生)
X
.
X
X
.
X
B
X
.
X
X
.
.
C(技师)
X
.
X
X
X
X
D
.
.
.
.
.
.
E(教师)
X
.
.
X
.
X
F
.
.
.
X
.
.

#include<stdio.h>

const int N=6;
int mat[N+1][N+1],res[N+1];
char *name[]={"","American","English","French","German","Italy","Russia"};

int main()
{
    for(int i=0;i<=N;i++)
        for(int j=0;j<=N;j++)
        {
            if(i==0||j==0) //mat[0][j]标识国籍是否被选，mat[i][0]标识某人是否选定国籍
            {
                mat[i][j]=0;                                                        
            }
            else                                                                    
            {
                mat[i][j]=1; //mat[i][j]=1表示存在可能性  
            }
        }

    mat[1][1]=0;mat[1][3]=0;
    mat[1][4]=0;mat[1][6]=0;                    
    mat[2][1]=0;mat[2][3]=0;
    mat[2][4]=0;mat[3][1]=0;
    mat[3][3]=0;mat[3][4]=0;
    mat[3][5]=0;mat[3][6]=0;
    mat[5][1]=0;mat[5][4]=0;
    mat[5][6]=0;mat[6][4]=0;

    while(mat[1][0]+mat[2][0]+mat[3][0]+mat[4][0]+mat[5][0]+mat[6][0]!=6)
    {
        for(int i=1;i<=N;i++)
        {
            if(mat[i][0]==0)                                                        
            {
                int x,y,acount=0;

                for(int j=1;j<=N;j++)
                    if(mat[i][j]!=0&&mat[0][j]==0)
                    {
                        x=i;y=j;acount++;
                    }

                if(acount==1)                                                        
                {
                    mat[0][y]=1;
                    mat[x][0]=1;
                    res[x]=y;
                }
            }
        }
    }

    for(int i=1;i<=N;i++)
        printf("%c is %s\n",'A'+i-1,name[res[i]]);

    return 0;
}