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

Question

给定2的个数,通过构建最多给定数量2的表达式可以形成多少个唯一值,包括加法或乘法.

例如,如果n = 2,我们可以形成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的增加,comibnations呈指数级增长,因此暴力无效.我需要另一种计算方法或广义数学公式.

可以使用动态编程解决,因为我看到许多子问题被重复使用.

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