S先生-P先生问题:C++解决和扩展思考

题目:两个自然数X、Y，2<=X<=Y<=99,S先生知道两个数的和，P先生知道两个数的积，二人进行了如下对话：
S:我不知道这两个数,但我知道你也不知道
P:现在我知道这两个数是什么了
S:我也知道了
问：这两个数是什么?

求解这是一个很有意思的问题，其妙处在于：不断使用别人推理的结论，继续自己的推理得到新的结论,而要想使用别人的结论，你必须猜测别人的推理过程。

其实这个推理的过程中有三个参与者。P先生,S先生和在思考这个题目的你，可以称为C先生(Clever).C先生拥有最少的信息，根据P和S先生的推理过程，得出全部的结论.----如果你完成这个题目，说明你是比P和S先生都聪明的C先生，呵呵.

强烈建议第一次碰到这个题的同志独立思考一段时间,然后再看下面的源代码.

下面是解决这个问题的C++的源代码:linux平台下，g++编译通过.

/**
 *sp.cpp - 解决S先生P先生问题
 *author: [e-mail]
 *
 */
#include <iostream>
#include <cassert>
#include <cmath>
using namespace std;

const int MAX_NUM=99;


//判断一个数是否是素数

bool is_prime(int num);
//满足条件1

bool by_condition_1(int x, int y);
//满足条件2

bool by_condition_2(int x, int y);
//满足条件3

bool by_condition_3(int x, int y);

int main()
{
  for(int x=2;x<=MAX_NUM;x++)
    for(int y=x;y<=MAX_NUM;y++)
      if( by_condition_1(x,y) &&
          by_condition_2(x,y) &&
          by_condition_3(x,y))
        {
          cout<<"X = "<<x<<", ";
          cout<<"Y = "<<y<<endl;
        }
  return 0;
}

/**
 *判断是否是[2,MAX_NUM]间的素数,为了提高效率，生成素数表.
 *@param num 要判断的数
 *@return 是否是素数
 *
 */
  
bool is_prime(int num)
{
  assert(num >=2);
  assert(num <=MAX_NUM);

  static bool table[MAX_NUM+1];
  static bool is_ready = false;
  if(!is_ready)
    {
      table[0] = false;
      table[1] = false;
      table[2] = true;

      for(int i = 3; i<=MAX_NUM; i++)
        {
          bool prime_flag = true;
          for(int j=2; j<=sqrt(i); j++)
            if(table[j] && i%j == 0)
              {
                prime_flag = false;
                break;
              }
          table[i] = prime_flag;
        }
      is_ready = true;
    }
  return table[num];
}
/**
 * 满足条件1
 * S:我不知道这两个数,但我知道你也不知道
 *=>把X+Y拆分成设定范围内两个正整数的和,猜测这两个数，拆分方法不是唯一的;
 * 并且,S可以看出,P看到的肯定不能是两个素数的积
 *=> X+Y不是4,并且,X+Y不可能是两个素数的和
 */
bool by_condition_1(int x, int y)
{
  assert(x<=y);
  int sum = x+y;
  if(sum == 4)
    return false;
  for(int i=2; i<=sum/2; i++)
    {
      if(sum-i<=MAX_NUM && is_prime(i) && is_prime(sum -i))
        return false;
    }
  return true;
}

/**
 * 满足条件2
 * P:现在我知道这两个数是什么了
 * =>把X*Y分解成设定范围内的两个正整数的积,猜测两个数，分解方法虽然不唯一
 * 但,能够满足条件1情况的，只有一种分解方法，所以P能够推理出这两个数
 */
bool by_condition_2(int x, int y)
{
  assert(x<=y);
  int product =x*y;

  //统计满足条件1的分解可能

  int count_condition_1 =0;
  
  for(int i =2; i<=sqrt(product); i++)
    {
      if(product %i == 0 && (product/i) <= MAX_NUM)
        {
          if(by_condition_1(i,product/i))
            if(++count_condition_1 >=2)
              break;
        }
      
    }
  if( count_condition_1 == 1)
    return true;
  return false;
}

/**
 *满足条件3
 * S:我也知道了
 *=>把X+Y拆分成两个正整数的和,猜测这两个数，拆分方法虽然不是唯一的
 * 但满足条件2的，只有一种拆分方法.
 */
bool by_condition_3(int x, int y)
{
  int sum = x+y;

  //统计所有满足条件2的拆分可能

  int count_condition_2 = 0;
  
  for(int i=2; i<=sum/2; i++)
    {
      if(by_condition_2(i,sum-i))
        if(++count_condition_2 >= 2)
          break;
    }

  if(count_condition_2 == 1)
    return true;
  return false;
}

执行结果：
cuichao@doom:~/cc-work/sp-problem$ time ./sp
X = 4, Y = 13

real    0m0.031s
user    0m0.024s
sys     0m0.000s
代码执行效率很高. 0.031秒, 这与我的代码编写很有关系
答案：两个数分别是4和13

问题的扩展思考:如果修改数字的范围为[2,499]，直接修改源代码中的常量: MAX_NUM=499,如果MAX_NUM太大，最好吧素数表(table变量)改成动态申请内存,因为许多系统上默认的静态存储区比较小，执行时可能发生内存错误。
执行结果如下：

cuichao@doom:~/cc-work/sp-problem$ time ./sp
X = 4, Y = 13
X = 4, Y = 61

real    0m2.513s
user    0m2.348s
sys     0m0.004s
范围增加了5倍，执行时间却多了接近100被.

这次多了一个答案，奇怪的是这个新答案竟然也在[2,99]的范围内。这是为什么?难道我的代码有问题。仔细想一下才明白，其实是因为：4×61=244.当P先生看到244时，可以在[2,99]范围唯一的分解成4和61的乘积，不满足P开始不知道的题目条件。而在更大的范围内，P先生看到244的时候,不能确定这两个数是4和61,还是2和122 -这能够满足题目条件.

如果在[0,999]的范围内，更有下面的情况.

cuichao@doom:~/cc-work/sp-problem$ time ./sp
X = 4, Y = 13
X = 4, Y = 61
X = 16, Y = 73
X = 32, Y = 131

real    0m19.339s
user    0m16.945s
sys     0m0.048s
cuichao@doom:~/cc-work/sp-problem$
到了更大范围，答案却仅限于较小的数字。这是因为，太大的数，拆分或分解的可能快速增加，使S，P先生的推理不再容易成立。


在[0,9999]范围内，执行了39分钟也没有全部执行完。

cuichao@doom:~/cc-work/sp-problem$ time ./sp
X = 4, Y = 13
X = 4, Y = 61
X = 4, Y = 181
X = 4, Y = 229
X = 8, Y = 239
X = 13, Y = 256
X = 16, Y = 73
X = 16, Y = 111
X = 16, Y = 163
X = 32, Y = 131
X = 32, Y = 311
X = 32, Y = 641
X = 32, Y = 821
X = 64, Y = 73
X = 64, Y = 127
(手工终止运行)

real    39m12.013s
user    34m52.599s
sys     0m2.816s
cuichao@doom:~/cc-work/sp-problem$

执行效率的进一步提高，
bool by_condition_1(int x, int y)函数，返回值决定与x+y，在执行过程中有大量重复计算,如果为每一个计算过的x+y进行缓存,大大的提高了计算的效率.效率至少提高了一倍.

文件:	sp-problem-src-1.0.tar.gz
大小:	46KB
下载:	下载