文章目錄

知道这个题目,是在任晓祎的博客里,据悉是加德纳改编的。题目如下:

某天, 老师召集了他最聪明的两个学生P和S, 递给每人一张纸条, 然后说, 有两个不小于2的整数x和y,满足x != y, 且x+y < 100. 给P的纸条上写有两个数的乘积p = x * y, 给S的纸条上写有两个数的和s = x+y, 请他们确定这两个数具体的值是多少. 于是P和S进行对话:

  1. P: 我无法确定这两个数是多少.
  2. S: 我知道你无法确定这两个数是多少.
  3. P: 既然这样, 那我知道这两个数是多少了.
  4. S: 既然这样, 那我也知道这两个数是多少了.
    请读者根据以上信息确定这两个数是多少.

当时看到这个题目后,和绍祝师兄一起做这道题,同时告诉海龙同学。和师兄讨论后,知道了题意,于是着手写代码,师兄用C++,我用C,结果两人都没写出来。很快海龙同学就得到了一个答案,是用手算得到的。我和师兄两人都汗颜了,有趣的是,这个答案就是唯一解。

回顾这道题,理清题意,大致如下:

1.P:我无法确定这两个数是多少。从这里可以得到,乘积p的分解不只一种,如12,可以分解成2 6, 3 4。

2.S:我知道你无法确定这两个数是多少。从这里可以得到,和s的分解中,x和y得到的乘积的分解不只一种,所有分解都满足条件1.如s为11时,可以分成2 + 9, 3 + 8, 4 + 7, 5 + 6,其中2和9的乘积为18,可以分解成2 9, 3 6; 对于3和8,4和7,5和6也是类似。

3.P: 既然这样, 那我知道这两个数是多少了。从这里可以得到乘积p的所有分解中,只有一个分解满足条件2。如18,18可以分解成2 9, 3 6,只有2和9的和11满足条件2,3和6的乘积不满足条件2.类似的还有24,28.

4.S: 既然这样, 那我也知道这两个数是多少了. 从这里可以得到s的所有分解中只有一组满足条件3.所以11不满足这个条件,因为11的分解中2 + 9, 3 + 8, 4 + 7,分别得到的18,24,28都满足条件3.

对于这种题目,还是用Python写比较方便。写成代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#coding:utf-8
from math import sqrt

def pone(p, u):
c = 0
for x in xrange(2, int(sqrt(p)) + 1):
if p % x == 0 and x + p / x < u:
c += 1
return c >= 2

def sone(s, u):
for x in xrange(2, s / 2):
y = s - x
if not pone(x * y, u):
return False
return True

def ptwo(p, u):
c = 0
for x in xrange(2, int(sqrt(p)) + 1):
if p % x == 0 and x + p / x < u:
y = p / x
if sone(x + y, u):
c += 1
return c == 1
def stwo(s, u):
c = 0
for x in xrange(2, s / 2):
y = s - x
if ptwo(x * y, u):
c += 1
return c == 1

if __name__ == "__main__":
u = 100
for x in xrange(2, u / 2):
for y in xrange(x + 1, u - x):
p = x * y
s = x + y
if pone(p, u) and sone(s, u) and ptwo(p, u) and stwo(s, u):
print "x:%d, y:%d, p:%d, s:%d " % (x, y, p, s)
文章目錄