Question

一个微软公司的编程面试题

已知两个数字为1~30的，甲知道两数的和，乙知道两数的积，甲问乙：“你知道是那两个数吗？”乙说：“不知道”。乙问甲：“你知道是那两个数吗？”甲说：“也不知道”。于是，乙说 ：“那我知道了”随后甲也说：“那我也知道了”这两个数是'什么？ （无意间看到这个面试题 我看了半天 毫无头绪 大家来解答解答这个题吧 集思广益 c/c++/java 均可 最好先把程序思想用文字说一下）

Answer 1

为了容易说明，我们先做些字符上的约定。设两个数字分别为a和b。甲知道它们的和x = a + b，乙知道它们的积y = a * b。

首先，甲问乙：“你知道是那两个数吗？”乙说：“不知道”。这说明什么呢？
乙是知道两个数的积y的。如果这个数y分解为a和b的方式只有1种（比如34 = 2 * 17），那么乙显然就知道这两个数是什么了。因此，通过这句话，我们必须筛选出所有“有2种可能组合以上的y值”，我们称之为R1，乙知道的数字y肯定在R1这个集合里。同时，“有2种可能组合以上的y值”对应的分解后的a和b可以组成一个集合S1：因为有些数字乘起来根本无法组成R1里的数字。这个集合S1就是两个数字筛选一次后的结果。

然后乙又问甲：“你知道是那两个数吗？”甲说：“也不知道”。这又说明什么呢？
注意这句话已经是第2句话了，根据理性假设，甲现在已经和我们一样筛选出了集合S1。但是同样的，他虽然知道两个数的和x，但是在集合S1里却仍然有两种以上的组合可能性。我们可以筛选出“S1中有2种可能组合以上的x值”，称之为R2。同时，利用R2中的x值，可以在S1中再筛选出分解后的a和b组成的新集合S2。这个集合S2是第2次筛选后的结果。

然后乙立刻说：“那我知道了”。
这说明，在集合S2中，乘积y只有一种分解方法。我们只要找到这种分解就可以了。当然，这样做可能仍然有多个解，因为乙是知道y是几的，但我们并不知道。我们称这个y的集合（“S2中有1种可能组合的y值”）为R3，R3的可能分解为S3。

然后甲又说：“那我知道了”。
这说明，在集合S3中，他所知道的分解x = a + b也只有1种。这时计算得到的a和b就是我们所要的答案。

我写的比较啰嗦，不知道你能不能看懂…… 你先看着，我稍后把程序贴上。

追问

wonderful!

追答

程序附上。答案似乎简单的出奇，a是1，b是4，加起来是5，乘起来是4。。。

==========================

#include

bool PlusKnow(int value)
{
int c = 0;
int cyc = value < 30 ? value : 30;
for (int i = 1; i <= cyc; i++)
{
if (value % i == 0 && i <= value / i && value / i <= 30)
c++;
}

return (c == 1);
}

bool AddKnow(int value)
{
int c = 0, j = 0;
int cyc = value / 2;
for (int i = 1; i <= cyc; i++)
{
j = value - i;

if (j <= 30 && !PlusKnow(i * j))
c++;
}

return (c == 1);
}

bool PlusKnow2(int value)
{
int c = 0;
int cyc = value < 30 ? value : 30;

for (int i = 1; i <= cyc; i++)
{
if (value % i == 0 && i <= value / i && value / i <= 30)
{
if (!AddKnow(i + (value / i)))
c++;
}
}

return (c == 1);
}

int main(int argc, char* argv[])
{
int a, b, x, y;

for (a = 1; a <= 30; a++)
{
for (b = a; b <= 30; b++)
{
x = a + b;
y = a * b;

if (!PlusKnow(y) && !AddKnow(x) && PlusKnow2(y))
printf("%d\t%d\n", a, b);
}
}

getchar();

return 0;
}

Answer 2

#include "stdafx.h"
//自己编的不知道对不对，大家讨论一下
void main(int argc, char* argv[])
{int i,j,x=2,y=1;
for(i=1;i<=30;i++)
for(j=1;j<=30;j++)
{if(x!=(i+j))
{
if(y!=(i*j))
{if(x!=(i+j))
{ y=i*j;printf("%d\t%d\n",i,j);continue;}

}
}
}
}

追问

应该不会这么简单吧····我看了下一个VB的程序 那个是相当长的 这个题目 网上很多版本的推论 很复杂的

追答

额，我是随便编的
，没看网上的。我也不知道，等等看有没有高人解答！嘿嘿

追问

你楼下有位高人解决出来了~~·来看看吧