c++ - 从一组给定的数字中求解所有可能的表达式

Question

最近我遇到了一个类似这样的问题。给定 n 个数字和三个运算符 +、- 和 *。使用第一个 n-1 数字和三个给定的运算符，您必须检查是否有办法将它们组合起来以给出“第 n 个”数字作为解决方案。

输入是一组数字，输出是Y或N。

例子

给定数字 10 9 7 1 10 8。我们可以使用 n-1 数字恰好一次。该示例的输出是 Y，因为存在一个解决方案，即 (10-10)*9+(7+1)=8。

到目前为止我的方法。

我很难找到解决问题的非蛮力方法。我使用的基本思想是这样的。我将首先计算 n-1 数字集的每个排列，然后在数字之间的每个 n-2 空格中插入所有可能的排列运算符并计算结果表达式。我无法对此进行编码，而且我怀疑这是否正确。请指导我如何解决问题。我正在使用 C++。

Answer 1

我认为基本上您将创建一组非常大的树。树的顶部有 n-1 个数字。您通过以下方式创建树的下一级:

• 排列数字
• 通过使用操作的排列组合相邻数字的子集来减少集合

重复该操作，直到集合的大小减少到 1。

以你的例子:10 9 7 1 10 8

• 创建 M 个数字的排列:10 10 9 7 1
• 选择大小为 Q 的相邻数字对的子集:10 10 和 7 1
• 创建大小为 Q 的操作的排列:* 和 *
• 通过以下操作组合相邻数字对来减少集合:10*10 => 100 和 7*1 ==> 7
• 您的新缩减集(我认为是树的下一层)是 100 9 7

重复。您将为数字的每个排列、相邻数字的每个子集以及操作的每个排列创建一棵新树。请记住，相邻数字子集的大小 Q 可以在 [1, M/2] 内。

对于“大”N，这将是内存和计算密集型。实际实现可能取决于您实际可用的硬件。一些优化可能是:

• 如果您使用的是蛮力方法，请从让大小 Q 尽可能接近 M/2 开始。这将减少中间集的数量。
• 记忆化可能会有帮助，但可能的组合如此之多，以至于只执行 int add/mul/sub 可能会更快，这(如果您使用的是 Intel)需要 1 个或 3 个周期。
• 由于有大量可能的归约树，我认为您需要使用遗传算法之类的东西来选择排列。

此外，这类问题并不是 C++ 的强项……用具有更多功能特性的语言(如 scala 甚至 ruby​​)编写它会更容易。

很酷的问题顺便说一句。