25

OEIS シーケンスA002845の項を計算するためのかなり高速なアルゴリズムを探しています。ここでその定義を再掲します。

^ は累乗演算子を表します。n 個の 2 を含む 2^2^...^2 という形式の式を考えてみましょう。括弧はすべて可能な方法で挿入されます (可能な括弧の数はカタロニア語の数字で与えられます)。これらの式の一部は、(2^2)^2=2^(2^2) のように同じ値になります。与えられた n の異なる値の数に関心があります。

これらの式を直接計算することによる明白な力ずくの解決策がありますが、必要な時間とスペースが、比較的小さな n の場合でも、すべての合理的な制限をすぐに超えてしまうことは明らかです。この問題に対する多項式時間の解法に興味があります。

4

3 に答える 3

3

反復された基数 2 で数値を表すだけNumです。x1,...,xpNumNum([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^y、2^2^k の形式の数値を計算できます。このクラスの数値には 2 (k=0) が含まれ、閉じて^いるため、操作する必要があるすべての数値がこの形式であることが保証されます。

さらに、上記で定義された等式は、ツリー内のノードの数を増やすことはないため、すべてNumのサイズは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 として非常に迅速に識別することができ、計算を 1 回行うと、二度と計算する必要のない値のリスト。

これはあまり役に立たないように見えるかもしれませんが、非常に長い一連の括弧で囲まれた質問、さらに長い同値セットを使用することになった場合、コンピューターが実行する非常に長い計算で、時間と複雑さを節約できます。非常に大きな数で。以下の疑似コード、お詫び申し上げます。これは非常に広範な疑似コードであり、この問題は非常に大雑把であるため、アルゴリズム全体を書きたくありませんでした。コンセプトをより詳細に概説しただけです

 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

力ずくよりもはるかに優れた (ただし、確かにまだ費用がかかる) アプローチの 1 つは、最初にリンクされた論文で「標準形式」の概念を使用することです。を指定してn、各標準形式の degree を生成しn、それを評価して、すべての値をセットに保持します。最後に、セットのサイズを確認します。

標準形の文法は

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

で始まりS、最後にn端末 (つまり2s) が必要です。

于 2013-05-03T20:07:23.270 に答える