使用给定数量的数字 2，求表达式的唯一值

Question

假设有n个数字2，最多只能使用这些数字进行加法或乘法运算，那么我们能够得到多少个不同的结果呢？

例如，当n = 2时，我们可以得到两个不同的结果：

2 + 2 = 4
2 * 2 = 4
2     = 2

当n = 3时，我们可以形成4个不同的值（2、4、6和8）：

2 * 2 * 2 = 8
2 * 2 + 2 = 6
2 + 2 * 2 = 6
2 + 2 + 2 = 6
2 * 2     = 4
2 + 2     = 4
2         = 2

我希望了解任意整数 n 的不同可能值的数量。

我尝试了所有可能的组合并将它们添加到哈希表中，但是随着 n 增加，组合数量呈指数级增长，因此暴力破解行不通。我需要另一种计算方式或一个通用的数学公式。

是否可以使用动态规划来解决，因为我看到许多重复使用的子问题。

- coder hacker

---

你问“可以形成多少个独特的表达式”，但是你第二和第三段中的例子似乎在计算独特值 - 到底是哪一个？ - A. I. Breveleri

出于好奇，这个编程竞赛的问题是什么？ - rici

Answer 1

到目前为止，其他答案都假定我们想要计算不同的表达式数量。而这个答案假设我们正在寻找这些表达式可以求值的不同值的数量。

假设您有一个大小不超过n的表达式。那么我们可以将其重写为2^e[1]+2^e[2]+...+2^e[m]，其中e[i] >= 1且e[1]+e[2]+...+e[m] <= n。

让我们假设e[1] <= e[2] <= ... <= e[m]。如果对于某些i，e[i] = e[i+1]，那么我们可以用单个指数e[i]+1替换两个相等的指数，因为2^e[i]+2^e[i+1]=2*2^e[i]=2^e[i]+1。由于e[i]+1 <= e[i]+e[i+1]，新序列得到相同的值，并且仍满足所有指数之和小于或等于n的条件。

因此，我们只需要计算不同指数序列的数量0 < e[1] < e[2] < ... < e[m]。很明显，每个序列都代表一个不同的值，因为数字的二进制表示是唯一的（而不同的指数恰好代表二进制表示）。

我们可以使用动态规划来计算这些序列，例如按从高到低的顺序选择指数。

让我们定义f(n,hi)为选择总和不超过n且最高指数<= hi的不同指数的数量。在每个步骤中，我们可以任意选择下一个最高指数，在1和min(hi,n)之间，或停止选择指数。因此，我们有以下递归关系式。

f(0, hi) = 1  for all hi >= 0
f(n, hi) = 1 + sum(e = 1 to min(hi, n), f(n - e, e - 1))

这导致了一个简单的动态规划来解决问题。答案是f(n,n) - 1。我们需要减去一个，因为我们还计算了不选择任何指数的可能性，这会导致总和为0。然而，根据问题陈述，这是不允许的。

以下是一些结果：

f(1,1) - 1 = 1
f(2,2) - 1 = 2
f(3,3) - 1 = 4
f(4,4) - 1 = 6
f(5,5) - 1 = 9
f(6,6) - 1 = 13
f(7,7) - 1 = 18
f(8,8) - 1 = 24
f(9,9) - 1 = 32
f(10,10) - 1 = 42
f(11,11) - 1 = 54
f(12,12) - 1 = 69
f(13,13) - 1 = 87
f(14,14) - 1 = 109

- Niklas B.

---

你的逻辑是正确的。但是，你能解释一下你的递归关系吗？ - Abhishek Bansal

@AbhishekBansal：我修改了它，因为它是错误的。现在应该是正确的，并且我添加了一个解释。 - Niklas B.

+1 分数给你的逻辑。然而，我对你的 DP 公式仍然有些不清楚。 - Abhishek Bansal

@AbhishekBansal：我已经证明我们只需要计算不同序列e[1] < ... < e[m]的数量，其中e[1] + ... + e[m] <= n。递归正是这样做的。我们从高到低选择指数。hi是下一个指数的上限，以强制执行<关系。可能会出现hi > n的情况，但显然选择大于n的指数是没有意义的，因为我们永远不会得到<= n的总和。 - Niklas B.

这是Sloane序列http://oeis.org/A026906，它反过来是http://oeis.org/A000009的部分和序列。请参见后者页面以获取各种计算可能性。请参见http://oeis.org/A000009/b000009.txt以获取A000009列表，最高可达N=1999，您可以轻松地计算部分和。 - rici

@rici：我也发现了，但我仍然认为看到如何推导递归公式很有用（这也可以用来计算结果）。 - Niklas B.

Answer 2

如果没有括号参与，则：

这不是一个编程问题，而是一个组合数学问题。操作数是固定的，你只需从2个运算符（+和*）中选择N-1个运算符来放置它们之间。有2^(N-1)种选择操作数的方式。

N=2: 2^(2-1) = 2^1 = 2 (+, *)
N=3: 2^(3-1) = 2^2 = 4 (++, +*, *+, **)

无需编程，只需要数学。

编辑：正如Niklas B.指出的那样，您自己的示例与您设置的标准不匹配。上面的公式是针对“恰好N个2”的情况。如果您要寻找“最多N个2”，并将其解释为“1到N个2之间”（因为我不确定如果您有0个2时结果会是什么），那么答案是2^N-1：

N=2: 2^2-1 = 4-1 = 3 (+, *, none)
N=3: 2^3-1 = 8-2 = 7 (++, +*, *+, **, +, *, none)

进一步编辑：如果你要计算值，那么你需要一些编程。最简单的解决方案是使用哈希映射，将值作为键，并在暴力搜索组合时计算频率。在这种情况下，动态规划可能会更麻烦，因为复杂度为O(N^2)，而且你可能不想计算百万操作数的公式，而运算符优先级的部分会导致算法不太直观。

- Amadan

---

我不知道，这似乎与示例不一致。我认为在写答案之前询问澄清是一个好主意。 - Niklas B.

@NiklasB：它为什么不一致？他还说“如果n=2，那么只有2个...”和“对于n=3，...所以总共4个”，与我的结果相同。编辑：哦，我错过了“至少”和他没有计算的较小的n...我会添加的。 - Amadan

是的，现在与OP期望结果不一致的矛盾已经显而易见：3！= 2和7！= 4。不幸的是，OP表达得非常混乱。 - Niklas B.

@NiklasB.：是的，我同意。 - Amadan

@NiklasB。我认为2^(n-1)不会在检查n=4时得到结果，因为在n=4时会有[8,10,16]，我们知道当n=3时，会有[2,4,6,8]，所以n=4的所有值都是[2,4,6,8,10,16]六个不同的值。 - Tim

@Tim：是的，我意识到了。我之前的循环有误，但现在我在我的答案中已经纠正了。 - Niklas B.