在网上看到一篇文章,里面提到一个算法问题,刚看到不会做,没有头绪。后来在网上看到有人提出了使用三进制的思路,很受启发,于是自己按照思路用 Python 实现了一下,比起用 Java 解决简单了太多 。
题目如下:
编写一个在1,2,…,9(顺序不能变)数字之间插入+或-或什么都不插入,使得计算结果总是100的程序,并输出所有的可能性。例如:1 + 2 + 34 – 5 + 67 – 8 + 9 = 100。
代码如下:
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
s = '123456789'
operators = {'0': '+', '1': '-', '2': ''}
def decimal2triad(n):
"""
十进制转三进制
:param n:
:return:
"""
triad = []
def _process(m):
quotient, remainder = divmod(m, 3)
triad.insert(0, str(remainder))
if quotient < 3:
triad.insert(0, str(quotient))
else:
_process(quotient)
_process(n)
return (''.join(triad)).zfill(8) # 向左侧填充'0',且使字符串一共8位长度
def search():
"""
暴力检验
:return:
"""
for x in range(3 ** 8):
tmp = list(s)
triad = decimal2triad(x)
values = [operators[x] for x in triad]
for index, value in enumerate(values):
tmp.insert(index * 2 + 1, value) # 每个字符插入的位置为index*2+1,如index为0的插入到1,index为1的插入到3,index为2的插入到5...
expression = ''.join(tmp)
if eval(expression) == 100:
print('{0}{1}'.format(expression, '=100'))
if __name__ == '__main__':
search()
输出结果:
1
2
3
4
5
6
7
8
9
10
11
1+2+3-4+5+6+78+9=100
1+2+34-5+67-8+9=100
1+23-4+5+6+78-9=100
1+23-4+56+7+8+9=100
12+3+4+5-6-7+89=100
12+3-4+5+67+8+9=100
12-3-4+5-6+7+89=100
123+4-5+67-89=100
123+45-67+8-9=100
123-4-5-6-7+8-9=100
123-45-67+89=100