By

文章目錄

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

某天, 老师召集了他最聪明的两个学生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)

打赏作者

文章目錄