25

我正在寻找一种相当快的算法来计算 OEIS 序列A002845的项。让我在这里重申它的定义。

让 ^ 表示幂运算符。考虑 2^2^...^2 形式的表达式，其中有 n 2 个括号，括号以所有可能的方式插入（可能的括号数量由Catalan numbers给出）。其中一些表达式将具有相同的值，例如 (2^2)^2=2^(2^2)。我们对给定 n 的不同值的数量感兴趣。

通过直接计算这些表达式有一个明显的蛮力解决方案，但很明显，即使对于相对较小的 n，所需的时间和空间也会很快超过所有合理的限制。我对这个问题的多项式时间解决方案感兴趣。

4

3 回答 3

3

仅表示迭代基数 2 中的数字： aNum有一个（可能为空）x1,...,xp类型为 的不同子项的列表Num，因此Num([x1,...,xp]) == 2^x1 + ... + 2^xp.

这定义了一种写入非负整数的独特方法；请记住对指数进行排序，以便比较有意义。平等：

  • 2^x + 2^x == 2^(x+1) == Num([x+1])
  • 2^x + 2^y == Num([x,y])什么时候x != y
  • (2^2^x)^2^y == 2^2^(x+y) == Num([Num([x+y])])

与加法的结合性/交换性一起，您可以添加任意数字并计算x^y2^2^k 形式的数字；这类数字包含 2（k=0）并且是封闭的，^因此这保证了我们需要操作的每个数字都是这种形式。

此外，上面定义的等式永远不会增加树中节点的数量，所以所有的Num都是 size O(n)。

所以时间复杂度实际上O(C * n^k)是 C 中的准线性（C 是第 (n-1) 个加泰罗尼亚数）。

于 2012-08-01T16:29:27.003 回答
1

我认为这里最好的解决方案涉及动态编程，这是一个难以掌握的概念，但如果操作正确，将非常有效。这个想法是通过记住您已经完成的计算结果，然后使用这些知识将问题拆分为更简单问题的子集，从而最大限度地减少您必须进行特定计算的次数。

例如，在您的 2^(2^2) = (2^2)^2 示例中，我们现在可以将其记住为等于 16 的值的两件事。所以现在当我们看到这附加到 2^ (2^(2^2)) = 2^((2^2)^2) 我们可以很快将其中的每一个识别为 2 ^ 16，计算一次，我们现在有两个新方程要添加到我们永远不必再次计算的值列表。

这似乎没有多大帮助，但是，当您最终遇到很长的括号问题，甚至更长的等价集时，它将为您节省时间和复杂性，因为计算机要做的计算很长在非常大的数字上。下面是伪代码，对不起，这真的是很宽泛的伪代码，这个问题很粗糙，所以我不想写出一个完整的算法。只是更详细地概述了这个概念

 sortedEquivalencyVector;  //Sorted greatest first, so we are more likely to se longest matches

 function(expression)

    if(portion of expression exists)  //Remember, you can only do this from the end of the expression in toward the middle!
         replace value at end of expression that matches with its already computed value

    if(simplified version exists in vector) add original expression to vector
    else compute value and add it to the vector
 end
于 2013-05-03T14:38:54.737 回答
0

一种比蛮力好得多的方法（但诚然仍然很昂贵）是在第一篇链接的论文中使用“标准形式”的概念。给定一个n，生成每个标准形式的 degree n，评估它，并将所有值保存在一个集合中。最后，检查集合的大小。

标准形式的语法是

S -> (2 ^ P)
P -> (S * P)
P -> S
S -> 2

你从一个开始S，最后你应该有n终端（即2s）。

于 2013-05-03T20:07:23.270 回答