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结婚。

评论