一个数字题

72 阅读 0 评论 48 点赞

我是靠谱客的博主痴情向日葵，最近开发中收集的这篇文章主要介绍一个数字题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

[2，100]中的两个整数a,b,把a+b的结果告诉A,把A*b的结果告诉B,然后两人有如下对话:

B:我算不出两个数

A:我就知道你算不出

B:我现在算出来了

A:我也算出来了

问这两个数是多少？

分析:

B说我算不出来，说明这两个数不全是素数

A说我知道你算不出来，说明这两个数的和不可能分解为两个素数之和

由此，设一个数组，为所有可能的a+b(candidates)

B从A那儿得到信息，知道两个数的和只可能在candidates中，于是他算出来那两个数，而A知道B算出来了以后A也算出来了，说明a+b只能有一种分解a0,b0,使a0*b0分解成的两个因子,它们的和在candidates中。

由此给出程序

std::vector<unsigned int> prims;//0-200的素数列表,从小到大排
std::vector<unsigned int> candidates;//和的候选者
//找出0-200中所有的素数
void findPrims(std::vector<unsigned int> &p)
{
p.clear();
p.reserve(200);
p.push_back(2);
for(unsigned int i = 3; i < 200; ++i)
{
  bool bprim = true;
  for(std::vector<unsigned int>::size_type j = 0; p[j] <= i / 2; ++j)
   if(i % p[j] == 0)
   {
    bprim = false;
    break;
   }
  if(bprim)
   p.push_back(i);
}
}

bool isPrim(unsigned int num)
{
std::vector<unsigned int>::iterator pos = std::lower_bound(prims.begin(), prims.end(), num);
return *pos == num;
}

bool isCandidate(unsigned int num)
{
std::vector<unsigned int>::iterator pos = std::lower_bound(candidates.begin(), candidates.end(), num);
return *pos == num;
}

//处理一个积，返回它分解为两个因子，这两个因子的和在候选者中的分解种数
unsigned int processMulti(unsigned int num)
{

unsigned int f1 = 2, f2 = 1;
unsigned int count = 0;
for(; f1 <= pow(num, 0.5); ++f1)
{
  if(num % f1 == 0)
  {
   if(f1 > 100)
    break;
   f2 = num / f1;
   if(f2 > 100)
    continue;
   if(isCandidate(f1 + f2))
     ++count;

  }
}
return count;
}

int _tmain(int argc, _TCHAR* argv[])
{
findPrims(prims);
for(unsigned int i = 5; i < 200; i += 2)
{
  bool bdel = false;
  for(unsigned int j = 2; j < i / 2; ++j)
  {
   if(isPrim(j) && isPrim(i - j))
   {
    bdel = true;
    break;
   }
  }
  if(!bdel)
   candidates.push_back(i);
}
for(std::vector<unsigned int>::size_type i = 0; i < candidates.size(); ++i)
  std::cout<<candidates[i]<<std::endl;
std::cout<<"共"<<candidates.size()<<"个候选者"<<std::endl;

for(std::vector<unsigned int>::size_type i = 0; i < candidates.size(); ++i)
{
  unsigned int count = 0;
  unsigned int one = 0;
  std::cout<<"process2:"<<candidates[i]<<std::endl;
  for(unsigned int j = 2; j < candidates[i] / 2; ++j)
  {
   unsigned int n = processMulti(j * (candidates[i] - j));
   if(n == 1)
   {
    one = j;
    ++count;
   }
  }
  if(count == 1)
   std::cout<<"find it:"<<one<<','<<candidates[i] - one<<std::endl;
}