algorithm - 从一组给定的数字中总计为给定数字的所有可能的操作组合

Question

我发现很多帖子非常相似(指的是换币问题)但仅使用求和运算符。 现在想象你可以加减乘除，有没有办法把所有的计算组合都变成一个给定的数？最好用 Java

例子: 给定 1 5 2 4 9 尝试得到 16

解决方案:

• 9+1+4+2=16
• 2*9-(5-4+1)=16
• 5*(4+1)-9=16
• 等等(我找到了其中的 20 个)。

谢谢。

Answer 1

由于您只有二进制操作，您可以将任何计算建模为二叉树，其中叶子是数字，所有其他节点代表操作，例如对于你的前两个例子:

  +                  -
 / \                / \
9   +              *   +
   / \            /|  / \
  1   +          2 9 -   1
     / \            / \
    4   2          5   4

因此您的算法需要以下部分:

• 一个树生成器，用于达到特定节点数的所有可能的二叉树:从一个数字节点开始，递归地用一个运算符节点和两个子节点(数字节点)替换每个数字节点(叶子)，从而生成一个树序列像这样

.

N   O       O       O       ...
   / \     / \     / \
  N   N   O   N   N   O
         / \         / \
        N   N       N   N

• 为给定的二叉树(如上)生成所有可能的操作和数字插入的“树填充器”，例如:

.

  O    :    +     +    ...  -  ...
 / \       / \   / \       / \
N   N     1   5 1   2     1   5

• 计算结果的树评估器

编程愉快! :-)