用数字 1, 2, 3, 4, 5, 6, 7, 8, 9 组合计算得到值为 100 的所有可能
在 Quora 上看到一个问题： Mathematical Puzzles: Can you make 100 out of the digits 1,2,3,4,5,6,7,8,9, in order?
觉得颇有意思，现在问题来了，如何利用计算机实现
用数字
1, 2, 3, 4, 5, 6, 7, 8, 9组合计算，最终结果为 100
的所有可能？就是能知道有多少种实现方式，想想都很有趣 :D
更新： 原想法是不按顺序，评论有提醒和原问题不一样，那就精确下：
- 按顺序来（1-9），有多少种方式？
- 不按顺序来，有多少种方式？
所有数字均只可使用一次。
snike
12 years, 1 month ago
Answers
import itertools
def sdyxss(pattern):
if len(pattern) == 17:
try:
e = ''.join(pattern)
if eval(e) == 100:
print(e)
except Exception as e:
pass
else:
x = int(pattern[-1])
for czf in list('+-*/'):
pattern.append(czf)
pattern.append(str(x + 1))
sdyxss(pattern)
pattern.pop(-1)
pattern.pop(-1)
pattern.append('')
pattern.append(str(x + 1))
sdyxss(pattern)
pattern.pop(-1)
pattern.pop(-1)
sdyxss(['1'])
最后得到的结果如下：
1+2+3+4+5+6+7+8*9
1+2+3-4+5+6+78+9
1+2+3-4*5+6*7+8*9
1+2+3-45+67+8*9
1+2+3*4-5-6+7+89
1+2+3*4*5/6+78+9
1+2+3*4*56/7-8+9
1+2+34-5+67-8+9
1+2+34*5+6-7-8*9
1+2-3*4+5*6+7+8*9
1+2-3*4-5+6*7+8*9
1+2*3+4+5+67+8+9
1+2*3+4*5-6+7+8*9
1+2*3-4+56/7+89
1+2*3-4-5+6+7+89
1+2*3*4*5/6+7+8*9
1+2*34-56+78+9
1+23-4+5+6+78-9
1+23-4+56+7+8+9
1+23-4+56/7+8*9
1+23-4-5+6+7+8*9
1+23*4+5-6+7-8+9
1+23*4+56/7+8-9
1+23*4-5+6+7+8-9
1+234-56-7-8*9
1+234*5*6/78+9
1+234*5/6-7-89
1-2+3+45+6+7*8-9
1-2+3*4+5+67+8+9
1-2+3*4*5+6*7+8-9
1-2+3*4*5-6+7*8-9
1-2-3+4*5+67+8+9
1-2-3+4*56/7+8*9
1-2-3+45+6*7+8+9
1-2-3+45-6+7*8+9
1-2-3+45-6-7+8*9
1-2-34+56+7+8*9
1-2*3+4*5+6+7+8*9
1-2*3-4+5*6+7+8*9
1-2*3-4-5+6*7+8*9
1-23+4*5+6+7+89
1-23-4+5*6+7+89
1-23-4-5+6*7+89
1*2+3+4*5+6+78-9
1*2+3+45+67-8-9
1*2+3-4+5*6+78-9
1*2+3*4+5-6+78+9
1*2+34+5+6*7+8+9
1*2+34+5-6+7*8+9
1*2+34+5-6-7+8*9
1*2+34+56+7-8+9
1*2+34-56/7+8*9
1*2-3+4+56/7+89
1*2-3+4-5+6+7+89
1*2-3+4*5-6+78+9
1*2*3+4+5+6+7+8*9
1*2*3-4+5+6+78+9
1*2*3-4*5+6*7+8*9
1*2*3-45+67+8*9
1*2*3*4+5+6+7*8+9
1*2*3*4+5+6-7+8*9
1*2*3*4-5-6+78+9
1*2*34+56-7-8-9
1*2/3+4*5/6+7+89
1*23+4+5+67-8+9
1*23+4+56/7*8+9
1*23-4+5-6-7+89
1*23-4-56/7+89
1*23*4-56/7/8+9
1*234+5-67-8*9
1/2*3/4*56+7+8*9
1/2*34-5+6-7+89
1/2/3*456+7+8+9
12+3+4+5-6-7+89
12+3+4-56/7+89
12+3-4+5+67+8+9
12+3*4+5+6+7*8+9
12+3*4+5+6-7+8*9
12+3*4-5-6+78+9
12+3*45+6*7-89
12+34+5*6+7+8+9
12+34-5+6*7+8+9
12+34-5-6+7*8+9
12+34-5-6-7+8*9
12-3+4*5+6+7*8+9
12-3+4*5+6-7+8*9
12-3-4+5-6+7+89
12-3-4+5*6+7*8+9
12-3-4+5*6-7+8*9
12*3-4+5-6+78-9
12*3-4-5-6+7+8*9
12*3-4*5+67+8+9
12/3+4*5-6-7+89
12/3+4*5*6-7-8-9
12/3+4*5*6*7/8-9
12/3/4+5*6+78-9
123+4-5+67-89
123+4*5-6*7+8-9
123+45-67+8-9
123-4-5-6-7+8-9
123-45-67+89
总共101条，应该是没有遗漏的，计算耗时12.777秒。
------------------------以上是按照Quora上的题目题意的解法---------------------------------------
如果1到9可以任意变化顺序耗时很长，当然，我算法很差，不一定剪枝完全了。
以上耗时12.777秒，而1到9的全排列有9!=362880种，则总共大约需要时间4636518秒，54天，太难算了。
有没有大神解决一下全排列的优化算法？
kaien
answered 12 years, 1 month ago
