我如何通过编程解决九九之谜？

Question

如何通过编程解决这个谜语？有人能帮我处理一些伪代码什么的吗？

9s

将9个9与任意数目的运算符+，-，*，/，(，)组合在一起，什么是最小的不能表示的正整数？

提示：

1. 答案不是零。你可以这样表示零：(9-9)* (9 +9+9+9+9+9+9+ 9)。而且，零不是正整数，

，

1. ，答案不是一个。你可以这样表达:9- (9 *9- 9)/9 +9-9+9-9
2. 这不是刁钻的问题。
3. 一定要正确处理括号。

备注：

不能使用exponentiation.

• You的
• 不能连接(例如，将两个9放在一起以生成99)。
• -运算符可以以二进制形式或一元形式使用。
• 假定基数为10.

。

这实际上是一个著名的谜题，可能有许多解决方案徘徊在互联网上。我不确定其中任何一个是正确的或不正确的。有谁有解释得很好的解决方案吗？

Answer 1

答案是195，下面是一些Python代码，它通过从exp1 OP exp2生成新表达式来构建所有可能的表达式。它在我的电脑上运行在0.165秒内。

exp = [set() for _ in xrange(10)]
exp[0].add(0)
exp[1].update([9, -9])
for i in xrange(1, 10):
  for a in list(exp[i]):
    for j in xrange(i, 10):
      for b in list(exp[j-i]):
        exp[j].update([a+b, a-b, a*b])
        if b != 0:
          exp[j].add(a/b)

n = 0
while n in exp[9]:
  n += 1
print n

编辑:如果答案必须是精确整数(而不仅仅是整数除法的四舍五入结果)，那么在进行除法时必须进行检查。

    if ((b != 0) and ((a/b) == float(a)/b)):
      exp[j].add(a/b)

根据对规则的这种解释，新的答案是138。(现有版本计算1386/10或-1386/-10，并得到138)

Answer 2

195号，http://members.iinet.net.au/~tmorrow/mathematics/ninenines/ninenines.html