3

正の整数 A が与えられます。目標は、次の規則を使用して、A で終わる整数の可能な限り短いシーケンスを構築することです。

  1. シーケンスの最初の要素は 1 です
  2. 連続する各要素は、先行する任意の 2 つの要素の合計です (それ自体に 1 つの要素を追加することもできます)。
  3. 各要素は、先行するすべての要素よりも大きくなります。つまり、シーケンスは増加しています。

たとえば、A = 42 の場合、考えられる解決策は次のとおりです。

[1, 2, 3, 6, 12, 24, 30, 42]

A = 42 の別の可能な解決策は次のとおりです。

[1, 2, 4, 5, 8, 16, 21, 42]

問題文を読んで真っ先に頭に浮かんだのは動的計画法(DP) だったので、探索問題として表現し、再帰的な解法を書いてみました。

A = 8 までの探索空間は次のとおりです。

                1
                |
                2
               / \
              /   \            
             3     4
            /|\   /|\
           / | \ 5 6 8
          /  |  \
         4   5   6
       /| |\  
      5 6 7 8

4 が 2 つの場所で発生することがわかりますが、どちらの場合も 4 の子は異なります。あるケースでは、前のシーケンスは [1, 2, 4] です。それ以外の場合、前のシーケンスは [1, 2, 3, 4] です。したがって、サブ問題が重複しているとは言えません。上記の問題にDPを適用する方法はありますか? それともDPで解けると判断するのが間違っているのでしょうか?

4

3 に答える 3

3

これが足し算の連鎖で……

http://en.wikipedia.org/wiki/Addition_chain

適切なタイミングまたはメモリ使用量が少ないことを保証して、特定の数の最小加算チェーンを計算できる既知のアルゴリズムはありません。ただし、比較的短いチェーンを計算するいくつかの手法が存在します。比較的短い加算連鎖を計算する非常によく知られた手法の 1 つは、 2乗によるべき乗に似たバイナリ法です。その他のよく知られている方法としては、ファクター法とウィンドウ法があります。

参照: IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences で短い加算チェーンを生成するための新しい方法。

于 2012-05-04T07:08:01.543 に答える
-1

ルール 2 により、

連続する各要素は、先行する任意の 2 つの要素の合計です

このアルゴリズムは部分問題の重複に依存しているため、動的計画法がそれを解決するのに適しています。

于 2012-05-04T07:27:41.907 に答える