来自数字数组的表达式

Question

你会得到三样东西

1) 'n‘个正整数和负整数的数组。2)一个数字'x‘。3)运算符：'+'，'-'，'%'，'/‘

用数组组成一个表达式，这样当你计算它时，结果就变成了'x‘。

例如，考虑阵列5,3，-1,6,2,3和x=2，一种可能的解决方案是

5/3+ (-1) +6/2-1

假设5/3的结果为1(始终为整数除法)。

我有一个更复杂的变体。

在这个问题的复杂变体中，假设BODMASS规则不适用。所以，在任何时候，你遍历元素'm‘，你都会得到中间结果'y’。您可以将任何运算符应用于'y‘和am + 1。

例如，在变体1中，

5+3-2/2=7(首先计算2/2，因此为5+3- 1)

在变体2中，

5+3- 2 /2=3 (5 +3= 8。数组减少到8 -2 /2。现在，8-2= 6。数组减少到6/2，计算结果为3)。

Algo/Math/DS专家？

这是NP难吗？

Answer 1

有4个运算符，所以对于一组n项，您有4^(n-1)个可能的值。您可以构建搜索空间的图，其中每条路径表示一组运算符值，终点是计算的结果。

在所有这些端点中，只有那些给出正确答案的端点才会在正确的端点结束。

但是，请注意，如果从终点开始，则可以向后遍历；只有拥有一组有效的运算符，才能在第一个值处结束。

因此，从两端遍历它，两个计算将在中间相遇。这是一个小得多的空间，每个方向都有4^(n/2) = 2^n。为了匹配两组答案，您需要对中间获得的列表进行排序，尽管您可能更喜欢在每一步都这样做，以防止重复路径被遵循。在这一点上，它看起来很像迷宫遍历。

一个已知的NP-完全问题是Boolean satisfiability，它是“确定给定布尔公式的变量是否可以以使公式求值为真的方式赋值的问题”。我怀疑，由于搜索空间明显大于布尔可满足性问题的搜索空间，并且由于解决方案也将确定公式是可满足的(因此至少与求解可满足性一样难)，那么该问题应该是NP-完全的。

在迷宫意义上，值偏离零的部分解决方案不太可能是正确的解决方案，并且给定参数的初始扫描，应该清楚大小的限制(即所有乘法)，这在布尔问题中不是这种情况。

编辑:为了澄清我在开头提到的树。假设我们的列表是

 1 ? 2 ? 5 = X

那么这个图就是这样的：

 r1 -->  r2  ---> r3 (X)

 1  +2    3  +5    8
             -5   -2
             *5   15
             /5    0

    -2   -1  +5    4
             -5   -6
             *5   -5
             /5    0

    *2    2  +5    7
             -5   -3
             *5   10
             /5    0

    /2    0  +5    5
             -5   -5
             *5    0
             /5    0

如您所见，如果X是-5，那么它可能是1 -2 *5或1 /2 -5。向后工作，从-5开始：

-5 +5    0
   -5  -10
   *5  -25
   /5   -1

因此，如果我们从每一端开始，我们将在中间一列，唯一的公共值将是-1和0，产生两条路径，有8次计算，而不是16次只在一个方向上进行。

这引发了一个问题，我没有注意到，整数除法不是1:1映射，因此后退是不明确的；-4/5 -> 0，-3/5 -> 0等等，直到4/5 -> 0。0是最坏的情况，因为它是从0的任意一侧开始逼近的，但即使是20/10到29/10都映射到相同的值2。这是一个相当大的障碍；当按被除数的大小向后移动时，它增加了可能的节点数量，因此对于5，存在3+5 =8而不是4的可能状态。

Answer 2

下面是一个递归解决方案的尝试(对于简单版本)：

Gen {'x'} = {'x'}
Gen {'x', 'y'} = {'x + y', 'x - y', 'y - x', 'x / y', 'y / x', 'x % y', 'y % x'}
S0 = {a[0]}
Gen S(i + 1) = {j ∈ S(i) | Gen {j, a[i + 1]}}

最终答案是：∃ j ∈ S(n). x = [[ j ]]

也就是说，我们增量地构建所有可能的值(作为表达式)，然后最终评估所有这些值，看看它们中是否有一个可以产生x (也可以增量地进行评估)。

但是，在这里，我假设在构建表达式时线性地使用来自a的值。我意识到你的问题不是这样的。