八卦镜 透视镜 偷窥镜

个人资料

日志分类

转世的忧郁的日志

解了一道难题(续)

收藏 366 次阅读 | 0 个评论 2007-12-19 15:27
那第二道应该是什么知名公司的面试题,不过现场能解出的大概不多,应该只是让说下思路……

分析:
(第一句甲说的)甲手中的和表明没有一种可能乙从仅知道积就推出两数。
(第二句乙说的)甲说出第一句之前乙手中的积推出的不只一种情况,而甲了后等于给了乙一定和的信息,那么乙便把可能性排除到只剩一种。
(第三句甲说的)简单理解甲手中的和表明能分解出的解只有一种情况能乙能确定。

计算步骤:

首先,用排除法对和进行排除:情况1,积的分解只有两个质数(在2-100内);情况2,分解出3个质数,但只有一种可能的组合,比如2*2*53其和57则排除;情况3,积可分解为多个素数但只有一组满足,例如2*2*2*61其和69排除(上述情况不全,需在排除过程中找到其他情况进行排除)通过排除一部分后我们可知和比较大的数基本上都能找出组合来排除,最后通过排除4-200这些和数中只剩下了11,17,23,27,29,35,37,47,53,这9个数,那么甲说完第一句话后等于把这9个和数告诉了乙

然后,条件1,对于乙来说分解出的只有一种和组合在这9个数中;条件2,对于甲来说9个数中每个数只有一组分界满足条件1。此步只能逐一分解,从小数开始,因为数越大分解情况越多,计算越复杂,同时也越可能不满足条件。观察上述9数均为奇,则两数一定为一奇一偶。

例如11:
11-2=9;2*3*3;和9或11;满足条件1
11-4=7;2*2*7;和16或11;满足条件1
这时有两组满足条件1则条件2不再满足11排除

正确的17:
17-2=15;2*3*5;和11或13或17;不满足条件1
17-4=13;2*2*13;和28或17;满足条件1
17-6=11;2*3*11;和17或25或35;不满足条件1
17-8=9;2*2*2*3*3;和17或27;不满足条件1
17-10=7;2*5*7;和37;不满足条件1
17-12=5;2*2*3*5;和23;不满足条件1
17-14=3;2*7*3;和23;不满足条件1
只有一种分解满足则17满足条件2

过程不严密( 很可能其中某些数排除有误),但逻辑应该没错,答案也是正确的,但有没有简单的方法呢?

评论 (0 个评论)

涂鸦板