IT Notes‎ > ‎Algorithms‎ > ‎

谁和谁结婚了?

按:这也是个来源于网络的老问题。

题目

三对情侣参加婚礼,三个新郞为A、B、C,三个新娘为X、Y、Z。有人不知道谁和谁结婚,于是询问了六位新人中的三位,但听到的回答是这样的:A说他将和X结婚;X说她的未婚夫是C;C说他将和Z结婚。这人听后知道他们在开玩笑,全是假话。请编程找出谁将和谁结婚。

要求答案输出
X will marry to B.
Y will marry to C.
Z will marry to A.

分析

三句话可以如此理解:
  1. A说他将和X结婚为假,那么可能的组合就是:A-Y, A-Z
  2. X说她的未婚夫是C为假,那么可能的组合就是:A-X, B-X
  3. C说他将和Z结婚为假,那么可能的组合就是:C-X, C-Y
以上,1已经说明 A-X 不可能,所以2仅剩下 B-X,
由此,又推得3仅剩下 C-Y
剩下的组合便是:A-Z
综上,这三对夫妻是:A-Z, B-X, C-Y

如果画表格,这更容易理解,可将某人问到的三句话转化成如下表格:
  X Y Z
 A ×  
 B   
 C ×  ×

很明显,B, C, X 都只剩下唯一选项,可以填入如下内容:
  X Y Z
 A ×  
 B   
 C ×  ×

那么剩下的就只有A-Z了,所以配对最后结果就是:
  X Y Z
 A   
 B   
 C   

程序解法

将此问题转化成程序解答,关键在于如何将此转化为计算机可理解的方式。实在是难!这里给出学到的方式:
  • 将新郎赋值到一个数组,这样表示新郎的字符就和下标关联在一起了。
  • 将新郎和结婚用等式来表示,比如 A-Z 结婚表示为 z==1,1为A对应的下标+1。
代码如下:
        // A, B, C 编号 1, 2, 3
        char[] brides = { 'A', 'B', 'C' };
        // A-Z结婚表示为 z==1
        for (int x = 1; x < 4; x++) {
            for (int y = 1; y < 4; y++) {
                for (int z = 1; z < 4; z++) {
                                  //x, y, z 不能相等,因为X, Y, Z 之间不能组合
                    if ((x != 1) && (x != 3) && (z != 3) && (x != y)
                            && (y != z) && (z != x)) {
                        System.out.println("X will marry to " + brides[x-1]);
                        System.out.println("Y will marry to " + brides[y-1]);
                        System.out.println("Z will marry to " + brides[z-1]);
                    }
                }
            }
        }

详细的可运行代码参这里


Comments