鬼谷子猜数问题

题目

鬼谷子是孙膑、庞涓的老师,他从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
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
# 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
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新增解
624, 13
16814, 61
196616, 73
251816, 111
471467, 82
  1. Max增大时,原来的解一定还会是解吗?
  2. 解有什么规律吗?
  3. 有没有更快的搜寻方法?

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

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