0

次のようなシーケンスが与えられた関数 F を生成する方法はありますか?

seq = [1 2 4 3 0 5 4 2 6]

次に、F(seq) はそのシーケンスを生成する関数を返しますか? あれは、

F(seq)(0) = 1
F(seq)(1) = 2
F(seq)(2) = 4
... and so on

また、そうである場合、最も複雑でない関数は何ですか?また、生成された関数の複雑さはどれくらいですか?

編集 私ははっきりしていないようですので、例証しようとします：

F(seq([1 3 5 7 9])} 
# returns something like:
F(x) = 1 + 2*x
# limited to the domain x ∈ [1 2 3 4 5]

つまり、 +、* などの数学関数を使用して代数的に使用できる関数を計算し、メモリから消去した場合でも、整数のシーケンスを復元したいと考えています。それが可能かどうかはわかりませんが、些細なケースでそのような関数の近似を簡単にコーディングできるので、それがどこまで進んでいるか、それに関する実際の研究があるかどうか疑問に思っています.

EDIT 2別の質問に答えて、私は整数のシーケンスにのみ興味があります-それが重要な場合。

まだはっきりしていない場合はお知らせください！

4

3 に答える 3

3

数列が次数の低い多項式に由来する場合、それを生成する一意の多項式を見つける簡単な方法は、ニュートン級数を使用することです。数値の多項式の構築には O(n²) 時間の複雑さがあり、それを評価するには O(n) かかります。

ニュートン級数では、多項式は、より馴染みのある x、x²、x³ ではなく、x、x(x-1)、x(x-1)(x-2) などで表されます。係数を取得するには、基本的に、シーケンス内の後続のアイテム間の差を計算してから、1 つだけが残るか、すべてゼロのシーケンスが得られるまで、差の間の差を計算します。一番下の数値を項の次数の階乗で割ると、係数が得られます。たとえば、最初のシーケンスでは、次の違いが得られます。

1  2  4  3  0  5   4   2    6
   1  2 -1 -3  5  -1  -2    4 
      1 -3 -2  8  -6  -1    6
        -4  1 10 -14   5    7
            5  9 -24  19    2
               4 -33  43  -17
                 -37  76  -60
                     113 -136
                         -249

したがって、このシーケンスを生成する多項式は次のようになります。

f(x) = 1 + x(1 + (x-1)(1/2 + (x-2)(-4/6 + (x-3)(5/24 + (x-4)(4/120 
         + (x-5)(-37/720 + (x-6)(113/5040 + (x-7)(-249/40320))))))))

これは、ラグランジュ補間などの他の手法を使用して得られる多項式と同じです。これは、たとえばラグランジュ形式とは異なり、ホーナーの方法で評価できる多項式形式の係数を取得するため、それを生成する最も簡単な方法です。

于 2013-09-28T10:44:44.673 に答える