鬼谷子猜数问题

发表于 更新于 分类于 阅读次数： 本文字数： 6k 阅读时长 ≈ 5 分钟

题目

鬼谷子是孙膑、庞涓的老师，他从2到99中选出两个不同的整数，把两数之和S告诉了庞涓、把两数的乘积M告诉了孙膑。

  1. 庞涓对孙膑说：虽然我无法确定这两个数是什么，但我肯定你也不知道这两个数是什么。
  2. 孙说：我本来不知道，但是你这么说，我就知道了。
  3. 庞说：既然你知道了，那我也就知道了。

问：这两个数字是什么？

分析

老实说这题的思维含量并不高，不过是枯燥的筛选求解而已。比较令我感兴趣的是其筛选方式十分有趣，短短的几个条件竟然能筛出唯一解。下面介绍一下怎么把题目翻译成代码。

首先是准备工作。我们需要两个迭代器，能在已知和或积的情况下，返回所有可能的整数对。

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
import math

Min = 2
Max = 99

def SumOfGenerator(n):
    maxValue = n >> 1
    minValue = max(Min, n - Max)
    if n & 1:   # 两个数不会相同
        maxValue += 1
    for i in range(minValue, maxValue):
        yield (i, n - i)
        
def MulOfGenerator(n):
    _maxValue = math.sqrt(n)
    _minValue = n / Max
    minValue, maxValue = int(_minValue), int(_maxValue)
    if maxValue != _maxValue: # 两个数不会相同
        maxValue += 1
    if minValue != _minValue:
        minValue += 1
        
    minValue = max(Min, minValue)
    
    for i in range(minValue, maxValue):
        if n % i == 0: # 由于Max不大，这里没必要用质因数来做
            yield(i, n // i)

特别注意边界不能有任何差池。接着我们一步步对问题进行描述：

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
# 1. 庞涓对孙膑说：虽然我无法确定这两个数是什么，但我肯定你也不知道这两个数是什么。 
def Step1(s): #庞涓视角，拿到两个数的和s
    for (a, b) in SumOfGenerator(s): #对于任何可能的组合
        m = a * b
        if len(list(MulOfGenerator(m))) == 1: #若某个组合只有一种分解情况
            return False            #那你就知道这两个数是什么了，所以这是不可能的
    return s > Min * 2 + 1     #且我不知道这两个数是什么


# 2. 孙说：我本来不知道，但是你这么说，我就知道了。
def Step2(m): #孙膑视角，他知道两个数的积m
    solveNum = 0
    for (a, b) in MulOfGenerator(m): #对于任何可能的组合
        if Step1(a + b):            #经过前一个条件的筛选
            solveNum += 1
            if solveNum >= 2:    #如果还有至少两个解，那我没法确定这两个数，矛盾
                return False
    return solveNum == 1        # 当然，没解也是不行的
    
# 3. 庞说：既然你知道了，那我也就知道了。
def Step3(s): #庞涓视角，他知道两个数的和s
    solveNum = 0
    for (a, b) in SumOfGenerator(s): #对于任何可能的组合
        if Step1(a + b) and Step2(a * b):
            solveNum += 1
            if solveNum >= 2: #如果还有至少两个解，那我没法确定这两个数，矛盾
                return False
    return solveNum == 1    # 当然，没解也是不行的

哈，原来挺简单的嘛。接下来，只要全面筛选就行啦！

1
2
3
4
for a in range(Min, Max):
    for b in range(a + 1, Max + 1):
        if Step1(a + b) and Step2(a * b) and Step3(a + b):
            print("a = %d, b = %d" % (a, b))

果然，我们得到了唯一解：a = 4, b = 13。将Max往前回溯一下发现，Max最小为62时有解；往前拓展发现一直都是这一个解，但当Max比较大（比如你可以试试700）的时候需要跑上几分钟了。

那么到底啥时候有两个解呢？能不能对算法进行一下优化？

优化

稍微分析一下算法可以发现，算法对三个Step函数其实有大量的重复调用。例如，Step3(2 + 8)和Step3(4 + 6)其实是相同的结果，但我们计算了两遍。容易想到，如果我们把已经计算的结果给存储下来，再次调用时直接获取结果，则可以省去大量时间。比如对于Step3，我们可以：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Step3Table = [None] * (Max * 2 + 1)
def Step3(n):
    if Step3Table[n] is None:
        solveNum = 0
        flag = True
        for (a, b) in SumOfGenerator(s): #对于任何可能的组合
            if Step1(a + b) and Step2(a * b):
                solveNum += 1
                if solveNum >= 2: #如果还有至少两个解，那我没法确定这两个数，矛盾
                    flag = False
                    break
        Step3Table[n] = flag and solveNum == 1    # 当然，没解也是不行的

    return Step3Table[n]

那对于Step2呢？我们的列表长度可能要扩展到Max * Max + 1，这实在是太占用空间了，而中间其实有很多用不到的下标。为此，我们采用字典方式存储。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Step2Table = {}
def Step2(n):
    if not n in Step2Table.keys():
        solveNum = 0
        flag = True
        for (a, b) in MulOfGenerator(m): #对于任何可能的组合
            if Step1(a + b):            #经过前一个条件的筛选
                solveNum += 1
                if solveNum >= 2:    #如果还有至少两个解，那我没法确定这两个数，矛盾
                    flag = False
                    break
        Step2Table[n] = flag and solveNum == 1        # 当然，没解也是不行的

    return Step2Table[n]

我们可以写一个类来专门处理这种存储数据节省时间的缓存类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class MemoryCache:
    
    def __init__(self, default_function, store_in_list = False, max_index = 0, min_index = 0):
        self.StoreInList = store_in_list # 是存在dict里面还是list
        self.DefaultFunction = default_function
        if store_in_list:
            assert(max_index > min_index)
            self.IndexRange = max_index - min_index + 1
            self.IndexOffset = min_index
            self.Cache = [None] * self.IndexRange
        else:
            self.Cache = {}

    def __getitem__(self, key): # 取下标运算重载
        index = key
        if self.StoreInList:
            index -= self.IndexOffset
            assert(0 <= index < self.IndexRange)
            if self.Cache[index] is None:
                self.Cache[index] = self.DefaultFunction(key)
        elif not key in self.Cache.keys():
                self.Cache[index] = self.DefaultFunction(key)
                
        return self.Cache[index]

这样可以更方便地处理三个Step函数。

再考虑到MulOfGenerator也是相当耗时间的工作，因为它涉及遍历和取余。如果把一个数的所有因子对（实际上只要存较小的那个就行）都存下来，也能节约不少时间，但这样消耗的空间也会较多。之后的分析可以看到，我们的Max在1600~2000范围时结果变化较大，若限定Max不超过2000，那么这样的空间消耗是一般可以接受的。

总代码

最后，我们将猜数封装成类，以最小值和最大值作为类的成员参数。

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
import math

class MemoryCache:
    
    def __init__(self, default_function, store_in_list = False, max_index = 0, min_index = 0):
        self.StoreInList = store_in_list
        self.DefaultFunction = default_function
        if store_in_list:
            assert(max_index > min_index)
            self.IndexRange = max_index - min_index + 1
            self.IndexOffset = min_index
            self.Cache = [None] * self.IndexRange
        else:
            self.Cache = {}

    def __getitem__(self, key):
        index = key
        if self.StoreInList:
            index -= self.IndexOffset
            assert(0 <= index < self.IndexRange)
            if self.Cache[index] is None:
                self.Cache[index] = self.DefaultFunction(key)
        elif not key in self.Cache.keys():
                self.Cache[index] = self.DefaultFunction(key)
                
        return self.Cache[index]

class GuiGuZiGuess:

    def __init__(self, minValue, maxValue):
        assert(0 < minValue < maxValue)
        self.Min, self.Max = minValue, maxValue
        self.MulOfCache = MemoryCache(lambda n: self.MulOf(n))
        self.Step1Cache = MemoryCache(lambda s: self.Step1(s), True, maxValue * 2, minValue * 2)
        self.Step2Cache = MemoryCache(lambda s: self.Step2(s))
        self.Step3Cache = MemoryCache(lambda s: self.Step3(s), True, maxValue * 2, minValue * 2)

    def SolveGenerator(self):
        for a in range(self.Min, self.Max + 1):
            for b in range(a + 1, self.Max + 1):
                if self.Step1Cache[a + b] and self.Step2Cache[a * b] and self.Step3Cache[a + b]:
                    yield (a, b)

    def GetSolveNum(self):
        return len(list(self.SolveGenerator()))

    def SumOfGenerator(self, n):
        maxValue = n >> 1
        minValue = max(self.Min, n - self.Max)
        if n & 1:
            maxValue += 1
        for i in range(minValue, maxValue):
            yield (i, n - i)

    def MulOf(self, n):
        mulOf = []
        _maxValue = math.sqrt(n)
        _minValue = n / self.Max
        minValue, maxValue = int(_minValue), int(_maxValue)
        if maxValue != _maxValue:
            maxValue += 1
        if minValue != _minValue:
            minValue += 1
            
        minValue = max(self.Min, minValue)
        
        for i in range(minValue, maxValue):
            if n % i == 0:
                mulOf.append(i)
                
        return mulOf

    def Step1(self, s):
        for (a, b) in self.SumOfGenerator(s):
            m = a * b
            if len(self.MulOfCache[m]) == 1:
                return False           
        return s > self.Min * 2 + 1     


    def Step2(self, m):
        solveNum = 0
        for a in self.MulOfCache[m]:
            b = m // a
            if self.Step1Cache[a + b]:
                solveNum += 1
                if solveNum >= 2:
                    return False
                
        return solveNum == 1
        
    def Step3(self, s):
        solveNum = 0
        for (a, b) in self.SumOfGenerator(s):
            if self.Step1Cache[a + b] and self.Step2Cache[a * b]:
                solveNum += 1
                if solveNum >= 2:
                    return False
        return solveNum == 1

这样一来，对于Max = 2000的情况，我这里约2秒可以计算完成，存储MulOfCache的部分占用约2.5MB内存。

再思考

经过简单的计算，解的数量有以下关系：

最小Max 新增解
62 4, 13
1681 4, 61
1966 16, 73
2518 16, 111
4714 67, 82
… …
  1. Max增大时，原来的解一定还会是解吗？
  2. 解有什么规律吗？
  3. 有没有更快的搜寻方法？

补充：
关于第一个问题，发现Max达到5482时解(67,82)会消失，具体原因可以自行思考，但注意以下几个式子：

8* 2741= 4* 5482
8+2741= 2+2747
67 * 82 = 2* 2747