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

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大小为止。

使用您的示例：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，则可能需要一个或三个周期。
• 因为有这么多可能减少的树，我想你需要用一些像遗传算法来选择排列。

而且，这种类型的问题并不是真正的C++.用一种功能更强的语言(比如scala，甚至ruby )来编写它会更容易。

很酷的问题BTW。

Answer 2

人们想到了两种办法：

1. 使用约束编程(CP) (eclipse，gnu prolog，.)在整数域上。给出了数字和运算符，CP会穷尽地寻找所有可能的解，或者如果你有点聪明，或者你的n太大，你可以通过注意到如果运算符是交换的(+，*)你不需要改变X和Y来指导搜索。如果您需要完成任务，请使用此方法，因为代码大约为20行。
2. 道格拉斯·霍夫斯塔特( Douglas )的一本老书名为“流体概念和创造性类比”，书中有丹尼尔·德菲斯( Daniel )的第三章，其中描述了一种认知科学方法(Numbo:认知和认知研究)。复制可能会涉及到一些，但如果这本书是任何迹象，它将是纯粹的乐趣。