如何蛮力算术拼图？

问题描述：

朋友分享了此益生：如何蛮力算术拼图？

如何从数字1,5,6,7做出21？

您可以使用加法，减法，乘法和除法操作以及括号。您必须使用每个号码一次。

我终于在纸上解决了 - 两天后。毫无疑问，一台计算机可能会在一秒之内强行推行所有解决方案

虽然如何？我尝试生成所有字符串a.b.c.d为字母插入字母和操作的数字，但它错过了我的解决方案。

奖金困惑：

如何使从1,5,6,7- 11？
如何从1,5,6,7制作16个？

什么将是21的答案吗？（我似乎无法找到它） – AnT 2015-03-30 18:55:21

我很肯定[这个Python代码]（http://ideone.com/aTiMHK）实现AnT的算法。我发现'16'或'21'没有结果。 – 2015-03-30 18:55:51

你是否允许像15 + 67这样的废话？ – 2015-03-30 19:04:47

答

一个显而易见的方法将是folllwing：S = (1, 5, 6, 7)

选择任意两个数字a和Sb，从S

其删除：

开始时你有载体的四个数字S
对a和b应用任意算术运算，从而获得新的数字c（以c是由零，以避免分裂和验证实际的分频，如果问题需要它）
包括c成S，由此获得S'
从步骤1继续，但现在使用S'代替S

蛮力在步骤2（选择两个数字）和步骤3（选择操作）执行分支。循环应该重复，直到S减少到只有1个元素，这是这个特定的蛮力分支的结果。

括号没有明确使用，但它们隐含存在。

如果一个分支以S的21结尾，那么您有解决方案，此时您可以终止或继续分支以搜索其他解决方案。

很酷。这正是我最终写的算法。你解释清楚。 https://gist.github.com/hickford/56cc7e2b0c55c140a976 – 2015-03-31 10:07:51

答

下面是AnT建议的“pop two，combine，recurse”算法，用Python编码。最难的部分是在递归之后组装表达式。我使用了查找和替换。

#!python 
import operator 
import itertools 
from fractions import Fraction 

operations = dict() 
operations['+'] = operator.add 
operations['-'] = operator.sub 
operations['/'] = operator.truediv 
operations['*'] = operator.mul 

def solve(target, numbers): 
    """List ways to make target from numbers.""" 
    numbers = [Fraction(x) for x in numbers] 
    return solve_inner(target, numbers) 

def solve_inner(target, numbers): 
    if len(numbers) == 1: 
     if numbers[0] == target: 
      yield str(target) 
     return 

    # combine a pair of numbers with an operation, then recurse 
    for a,b in itertools.permutations(numbers, 2): 
     for symbol, operation in operations.items(): 
      try: 
       product = operation(a,b) 
      except ZeroDivisionError: 
       continue 

      subnumbers = list(numbers) 
      subnumbers.remove(a) 
      subnumbers.remove(b) 
      subnumbers.append(product) 

      for solution in solve_inner(target, subnumbers): 
       # expand product (but only once) 
       yield solution.replace(str(product), "({0}{1}{2})".format(a, symbol, b), 1) 

if __name__ == "__main__": 
    numbers = [1, 5, 6, 7] 
    target = 21 
    solutions = solve(target, numbers) 
    for solution in solutions: 
     print("{0}={1}".format(target, solution))

解三个难题：

>>> solve(21,[1,5,6,7]) 
6/(1-(5/7)) 
>>> solve(11,[1,5,6,7]) 
(6*(7-5))-1 
((7-5)*6)-1 
>>> solve(16,[1,5,6,7]) 
[]

（第三个谜题是不可能的）

如何蛮力算术拼图？

相关推荐