一个微软公司的编程面试题已知两个数字为1~30的,甲知道两数的和,乙知道两数的积,甲问乙:“你知道是那两个数吗?”乙说:

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就是我们所要的答案.

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