学步园

昨儿个群里面讨论一个算法，在

http://blog.csdn.net/v_JULY_v/archive/2011/01/10/6126444.aspx

中，第22题博主没有写出代码，表示代码不好写。我对于穷举算法不怎么会写，于是很差劲地写了下面的代码(循环太多），题目为：

有4张红色的牌和4张蓝色的牌，主持人先拿任意两张，
再分别在A、B、C三人额头上贴任意两张牌，

A、B、C三人都可以看见其余两人额头上的牌，
看完后让他们猜自己额头上是什么颜色的牌，
A说不知道，B说不知道，C说不知道，然后A说知道了。

请教如何推理，A是怎么知道的。如果用程序，又怎么实现呢？

 

 我的代码实现如下： 

// 假定0为红，1为蓝色
//

bool isknown(int* m, int* n)
{
int red = 0;
int blue = 0;

for (int i=0; i<2; ++i)
  {
if ( m[i] == 0 )
    {
      red++;
    }
else
    {
      blue++;
    }

if ( n[i] == 0 )
    {
      red++;
    }
else
    {
      blue++;
    }
  }

if ( red > 2 || blue > 2 )
  {
return true;
  }

return false;
}

bool get(int* a, int* b, int* c, int* d)
{
// 遍历所有的可能性
  bool found = false;
for (int a1=0; a1<2; ++a1)
  {
    a[0] = a1;
for (int a2=0; a2<2; ++a2)
    {
      a[1] = a2;

for (int b1=0; b1<2; ++b1)
      {
        b[0] = b1;
for (int b2=0; b2<2; ++b2)
        {
          b[1] = b2;

for (int c1=0; c1<2; ++c1)
          {
            c[0] = c1;
for (int c2=0; c2<2; ++c2)
            {
              c[1] = c2;

if ( !isknown(a,b) && !isknown(a,c) && !isknown(b,c) )
              {
return true;
              }

            }
          }
        }
      }
    }
  }

return true;
}

int main(int argc, char* argv[])
{
int a[2], b[2], c[2], d[2];
get(a,b,c,d);

  printf("a:%d,%d, b:%d,%d, c:%d,%d", a[0], a[1], b[0], b[1], c[0], c[1]);

return 0;
}

不知道还有没有更好的方法，请各位看官赐教了!

 /*
  * @   2011-3-10
  *
  * Copyright (c) 2011 Ubunoon.
  * All rights reserved.
  *
  * email: netubu#gmail.com  replace '#' to '@'

  * http://www.cnblogs.com/ubunoon
  */