2005年5月16日第19期电脑报编程点将台

题目：三对情侣参加婚礼，三个新郎为A,B,C,三个新娘为X,Y,Z。有人不知道谁和谁结婚，于是询问了六

个新人中的三人，但是听到的回答是这样的：A说他将和X结婚；X说她将的未婚夫是C；C说他将的Z结婚。

这人听后知道他们在开玩笑，全是假话。请编程找出谁将和谁结婚。


我的程序：

/*算法思想：对三个新娘分别分别新郎，当满足以下条件时就输出：
X!='A'&&X!='C'&&Z!='C'表示三个假话，&&X!=Y&&X!=Z&&Y!=Z
表示每个新娘的新郎都不一样（^_^也就是没有一妻多夫）

  我的程序的时间复杂度是：n的三次方，所以不是很好，
  但是要是直接从题目中推理然后去掉一些可能性后再配对的话，
  那么其实马上可以得出答案，也就是这题其实出得很差得，完全没
  必要用计算机来推理。

  在我的程序的后面是那期获奖的两个程序。大家可以参考。不过，感觉我的程序
的可读性比较好，获奖的程序我也看了很久理解什么怎么得出来的。
*/
#include<iostream>
using namespace std;
void main()
{
    char X,Y,Z;
    for(X='A';X<='C';X++)
        for(Y='A';Y<='C';Y++)
            for(Z='A';Z<='C';Z++)
                if(X!='A'&&X!='C'&&Z!='C'
                    &&X!=Y&&X!=Z&&Y!=Z)
                    cout<<"X,Y,Z的未婚夫分别

是："<<X<<","<<Y<<","<<Z<<endl;
}



获奖程序一：

/*
编程思想：求出不结婚的，剩下的就是结婚的。
将3对情侣的关系用一个3*3的矩阵表示出，结婚值为0，不结婚值为1。
  a  b  c
x *  *  *
y *  *  *
z *  *  *
       
将限制条件输入，可以得到3个1。
  a  b  c
x 1  *  1
y *  *  *
z *  *  1
由于每个人只能与一个人有婚姻关系，因此每行（列）只能有1个0，2个1；即每行（列）之和为2。

*/
#include <stdio.h>
#define num 3

void main()
{
    int i,j;
    unsigned char marry[3][3]={0},out[6]={0};
    
    marry[0][0]=1;
    marry[0][2]=1;
    marry[2][2]=1;
  
    
    for(i=0;i<num;i++)
    {
        out[0]=out[0]+marry[0][i];
        out[1]=out[1]+marry[1][i];
        out[2]=out[2]+marry[2][i];
        out[3]=out[3]+marry[i][0];
        out[4]=out[4]+marry[i][1];
        out[5]=out[5]+marry[i][2];
    }
    
    for(i=0;i<num;i++)
    {
        if(out[i]==num-1) for(j=0;j<num;j++) if(marry[i][j]!=1) {marry[(i+1)%num]

[j]=1;marry[(i+2)%num][j]=1;}
        
    }



    for(i=0;i<num;i++)
    {
        if(out[i+3]==num-1) for(j=0;j<num;j++) if(marry[j][i]!=1) {marry[j][(i+1)%

num]=1;marry[j][(i+2)%num]=1;}
    }
    
    
    //////////打印结果
    printf("0表示结婚，1表示不结婚\n");
    printf("\n   A  B  C\n");
    for(i=0;i<3;i++)
    {
       if(i==0) printf(" X");
       if(i==1) printf(" Y");
       if(i==2) printf(" Z");
       for(j=0;j<3;j++)
       {
          printf(" %d ",marry[i][j]);
          if(j==2) printf("\n");
       }
    }

}


获奖程序二：
    我在程序中用0，1，2，4，8，16六个数分别表示A，B，C，X，Y，Z六人，这样任意两个人相加都会

得出不同的结果，那么，两人结婚则用他们的数字相加后保存在一个变量（数组c）中作为判断是否符合

题目要求的条件，最后在数组c中每行取一个数来组合，如果有不符合条件的数据（即出现题目中所说的

那三对新人结婚后的数据）即表明该组不符和条件。经过简单的计算，我们可知不满足条件的和（即数组

c中的元素值）有4--A和X结婚，6--C和X 结婚，18--C和Z结婚，筛选时选择不含有这些数据的组合即可。
    源程序如下：
1.  main()
2.  { char a[3]={'X','Y','Z'};
3.    int b[2][3]={0,1,2,4,8,16},c[3][3],i,j;
4.    for(i=0;i<=2;i++)
5.     for(j=0;j<=2;j++)
6.      c[i][j]=b[0][i]+b[1][j];
7.    for(i=0;i<=2;i++)
8.     {if(c[0][i]==4) continue;
9.      for(j=0;j<=2;j++)
10.      if((i==j)||(c[2][3-i-j]!=10)) continue;
11.      else
12.      { printf("A----%c\n",a[i]);
13.        printf("B----%c\n",a[j]);
14.        printf("C----%c\n",a[3-i-j]);
15.        break;
16.       }
17.    }}
注：8行的if(c[0][i]==4) continue表示A不能和X结婚。
    10行的c[2][3-i-j]!=10表示C只能和Y结婚。

评论