0

一个完全没用的问题：我买了一个数字游戏，它是由两个黑色骰子加上 5 个彩色骰子组成的。两个黑色的组成一个 2 位数字，范围从 11 到 66，另外 5 个是您可以使用的数字，将它们以所有可能的数字表达式与任务结合以获得目标数字。

比如黑40+2：目标42

彩色 5 3 6 2 4，可以通过 5 3 + 6 * 4 2 + - 获得目标（使用 RPN，因为它避免了括号）。

现在我想用我的袖珍电脑在我们玩游戏的时候找到最佳答案。

我必须说我还没有真正考虑过解决方案，我只是寻找关于寻找参数排列的部分，但是如何从中生成可能的表达式？我会使用 RPN 并枚举所有可能的表达式“形状”，然后用 +-*/ 填充空格。

我不认识枚举表达式形状的问题。

输出将是这样的： .....xxxx ....x.xxx ...x..xxx ..x...xxx ....xx.xx ...xxxx ..x..x .xx ...xx..xx ..xx.xx ....xxx.x ...x.xx.x ..x..xx.x ...xx.xx ..xxxx

像： ..xx...xx ...xxx..x ..x.xx..x ..x.xx..x 是无效的，因为第二个或第三个运算符会找到一个操作数。

我可以使用硬编码列表，但它看起来真的很难看！

4

2 回答 2

7

我认为您正在寻找的是大小为 5 的完整二叉树的枚举。（此类对象的计数是第五个加泰罗尼亚数字，即 14。）。枚举是直截了当的，基于加泰罗尼亚数的标准递归：
http://upload.wikimedia.org/math/2/f/1/2f17435a71394ce667ab694b27341560.png
对于每个 (i, 5-i)，生成所有带i叶子的树和所有带5-i叶子的树，以及每个集合中一棵树的每个组合，通过创建一个根节点来构造一棵新树，该根节点的左孩子来自第一个集合，右孩子来自第二个集合。如果不想使用树，直接使用 RPN：

# Produces all possible RPN layouts with n values and n-1 binary operators,
# representing values as '#' and operators as '+'
def RPN(n):
  if n == 1:
    yield '#'
  for i in range(1,n):
    for left in RPN(i):
      for right in RPN(n - i):
        yield left + right + '+'

当然，也有一元运算符。如果你允许这些，它会变得更加复杂。

请注意，您可以直接修改上述内容以直接插入参数；不是将 n 划分为 (i, ni)，而是将 n 值集合的所有分区划分为两个非空子集。（否则，您可以找到一组数字的所有排列，并将它们插入生成的 RPN 表达式。）

然后“所有”您需要做的是插入所有可能的运算符序列（如果您只允许 +、-、* 和 / 那么您有 4 4 = 256 种可能性）。

因此，如果这五个数字不同，您将得到 14 * 5！* 4 4 = 430080 个要测试的表达式。

于 2013-01-14T00:20:59.303 回答
0

枚举不同数字块数量的问题是您可以应用于集合的分区数http://en.wikipedia.org/wiki/Partition_of_a_set

于 2013-01-13T23:49:07.603 回答