14

k = 2 の場合、フィボナッチ数列は誰もが知っています。

すなわち:1,1,2,3,5,8,13

しかし、これは 2-フィボナッチです。このように、3 番目のフィボナッチを数えることができます。

1,1,2,4,7,13,24

そして 4-フィボナッチ:

1,1,2,4,8,15,29

…と続きます

私が求めているのは、k-フィボナッチ数列内の「n」要素を計算するアルゴリズムです。

このように: を要求するfibonacci(n=5,k=4)と、結果は次のようになります: 8、つまり、4-フィボナッチ数列内の 5 番目の要素。

ウェブのどこにも見つかりませんでした。役立つリソースはmathworldかもしれません

誰？そして、あなたがpythonを知っているなら、私は好む. しかし、そうでない場合は、任意の言語またはアルゴリズムが役立ちます。

ヒント: 役に立つと思います: k フィボナッチ数列を分析してみましょう。ここで、k は 1 から 5 になります。

k    fibonacci series

1    1, 1, 1, 1, 1, 1, 1, 1,1, 1, 1, ...
2    1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
3    1, 1, 2, 4, 7, 13, 24, 44, 81, ...
4    1, 1, 2, 4, 8, 15, 29, 56, 108, ...
5    1, 1, 2, 4, 8, 16, 31, 61, 120, ...

これを分析すると、k-フィボナッチ数列の配列 [0:k] は前のフィボナッチ数列と等しく、k=1 まで続くことがわかります。

つまり（表示しようとしますが、正しい言い方がわかりません）：

k    fibonacci series

1    1, 
2    1, 1, 
3    1, 1, 2, 
4    1, 1, 2, 4, 
5    1, 1, 2, 4, 8,

これを解決するのに何らかの形で役立ったことを願っています。

[Pythonでの解決策（必要な場合）]

class Fibonacci:

    def __init__(self, k):
        self.cache = []
        self.k = k

        #Bootstrap the cache
        self.cache.append(1)
        for i in range(1,k+1):
            self.cache.append(1 << (i-1))

    def fib(self, n):
        #Extend cache until it includes value for n.
        #(If we've already computed a value for n, we won't loop at all.)
        for i in range(len(self.cache), n+1):
            self.cache.append(2 * self.cache[i-1] - self.cache[i-self.k-1])

        return self.cache[n]


#example for k = 5
if __name__ == '__main__':
    k = 5
    f = Fibonacci(k)
    for i in range(10):
        print f.fib(i),
4

10 に答える 10

9

2-フィボナッチと同様に、動的計画法が最適です。以前kの s の値をメモして、後の値をすぐに計算しO(n)ます。

の大きな値の速度を向上させるために使用できる別の最適化は、 getにスルーをk追加する代わりに、 を使用するだけです。これは 2 つのルックアップ、2 つの加算、および 1 つの乗算のみを使用するため、大きくなるとルックアップおよび加算よりもはるかに優れています(ただし、定数乗数が小さいだけです)。f(n-k)f(n-1)f(n)(2*f(n-1)) - f(n-k-1)kkkO(n)

于 2010-11-08T08:46:31.613 に答える
7

1 つの値(つまり ) だけを解きたい場合fibonnaci(n,k)、より効率的な方法は線形再帰を使用することです。O(k^3 log(n))k^3

基本的に、これが機能する方法は、ベクトルをベクトルF(n), F(n-1) ... F(n-k)の行列倍として表現することですF(n-1), F(n-2) ... F(n-k-1)。次に、行列の乗算は結合的であるため、行列を累乗し、これに初期ベクトルを掛けることができますF(k), F(k-1) ... F(0)。

O(log(n))べき乗は、2 乗によるべき乗を使用して行うことができます。

たとえば、k=3 の場合、次のようになります。

[F(n+2)]   [1 1 1] [F(n+1)]
[F(n+1)] = [1 0 0] [F(n)  ]
[F(n)  ]   [0 1 0] [F(n-1)]

F(n) を解くには、

[F(n+2)]   [1 1 1]^n [F(2)]
[F(n+1)] = [1 0 0]   [F(1)]
[F(n)  ]   [0 1 0]   [F(0)]
于 2010-11-08T09:47:59.813 に答える
7

これは、 Ambers answerに基づく反復ソリューションです。

class Fibonacci {

    List<Integer> cache = new ArrayList<Integer>();
    final int K;

    public Fibonacci(int k) {
        this.K = k;

        // Bootstrap the cache
        cache.add(1);
        for (int i = 1; i <= k; i++)
            cache.add(1 << (i-1));
    }

    public long fib(int n) {

        // Extend cache until it includes value for n.
        // (If we've already computed a value for n, we won't loop at all.)
        for (int i = cache.size(); i <= n; i++)
            cache.add(2 * cache.get(i-1) - cache.get(i-K-1));

        // Return cached value.
        return cache.get(n);
    }
}

テストは次のようになります。

public class Main {
    public static void main(String[] args) {
        System.out.println("k     fibonacci series");

        for (int k = 1; k <= 5; k++) {
            System.out.print(k + "     ");

            Fibonacci f = new Fibonacci(k);
            for (int i = 0; i < 10; i++)
                System.out.print(f.fib(i) + ", ");
            System.out.println("...");

        }
    }
}

そして版画

k     fibonacci series
1     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
2     1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
3     1, 1, 2, 4, 7, 13, 24, 44, 81, 149, ...
4     1, 1, 2, 4, 8, 15, 29, 56, 108, 208, ...
5     1, 1, 2, 4, 8, 16, 31, 61, 120, 236, ...
于 2010-11-08T08:58:37.050 に答える
3

簡単な方法は、最新の k 項を単純に加算して、毎回現在の項を取得することです。これにより、O(n*k) ランタイムが得られます。

もう 1 つの方法は、行列累乗を使用することです。k=2 の場合、行列を使用して状況をモデル化できます。(Fn-1, Fn-2) から (Fn-1+Fn-2,Fn-1) を計算することで (Fn, Fn-1) を導き出すことができます。

したがって、列行列を掛けると

[
Fn-1
Fn-2
]

正方行列で

[
1 1
1 0
]

収量

[
Fn-1 + Fn-2
Fn-1
]

これにより、Fn の値が得られます。

もちろん、これはまだ O(n*k) より優れているわけではありません。n 番目の項を取得するために、O(n) ループ/再帰を引き続き実行します。

それを観察してください（便宜上、列ベクトルを水平に書いていますが、それらはまだ列です）

[[Fn],[Fn-1]] = [[Fn-1],[Fn-2]]*[[1,1] [1,0]]
              = [[Fn-2],[Fn-3]]*[[1,1] [1,0]]*[[1,1] [1,0]]
              = [[Fn-3],[Fn-4]]*[[1,1] [1,0]]*[[1,1] [1,0]]*[[1,1] [1,0]]
              = [[Fn-3],[Fn-4]]*([[1,1] [1,0]])^3
              = [[Fn-k],[Fn-k-1]]*([[1,1] [1,0]])^k
              = [[F1],[F0]]*([[1,1] [1,0]])^n-1

これで、二乗によるべき乗([[1,1] [1,0]])^n-1を使用して O(log(n)) 時間で計算できます。したがって、最大で log(n) 行列の乗算を使用して、k-フィボナッチの n 番目の項を計算できます。単純な行列乗算を使用すると、O(k^3*log(n)) の複雑さが得られます。

編集：

これは、私が言っていることをよりよく説明するために一緒にハッキングした Python のコードです。

from itertools import izip

def expo(matrix,power, identity):
    if power==0:
        return identity
    elif power==1:
        return matrix
    elif power&1:
        return multiply(matrix,expo(matrix,power-1,identity))
    else:
        x=expo(matrix,power>>1,identity)
        return multiply(x,x)

def multiply(A,B):
    ret=[list() for i in xrange(len(B))]
    for i,row in enumerate(B):
        for j in xrange(len(A[0])):
            coloumn=(r[j] for r in A)
            ret[i].append(vector_multiply(row,coloumn))
    return ret

def vector_multiply(X,Y):
    return sum(a*b for (a,b) in izip(X,Y))

def fibonacci(n,start=[[1],[0]], k=2):
    identity=[[1 if col==row else 0 for col in xrange(k)] for row in xrange(k)] # identity matrix
    # build the matrix for k
    matrix=[[1]*k]
    for i in xrange(1,k):
        matrix.append([0]*(i-1)+[1]+[0]*(k-i))
    return multiply(start,expo(matrix,n-1,identity))[0][0]

print fibonacci(10)
于 2010-11-08T09:43:00.060 に答える
1

人々はすでに O(logN) ソリューションについて言及しています。累乗される行列の定数がどのように発生したかを理解している人は多くありません。マトリックスを使用して線形回帰を解決する方法の詳細な分析が必要な場合は、コード オーバーフローをご覧ください。

于 2013-09-01T07:18:22.870 に答える
1

演習のために、これを Haskell で実装しました。fib通常、リスト内包表記として次のように記述します。

fib = 1:1:[x + y | (x,y) <- zip fib $ tail fib]

zipには 2 つの引数が必要なため、「k」項への一般化は困難です。zip3、などがありますがzip4、一般的な はありませんzipn。ただし、ペアを作成する手法を廃止し、代わりに「シーケンスのすべてのテール」を生成し、kそれらの最初のメンバーを合計することができます。k=2 の場合は次のようになります。

fib2 = 1:1:[sum $ take 2 x | x <- tails fib2]

任意の一般化k:

fibk k = fibk'
  where fibk' = take (k - 1) (repeat 0) ++ (1:[sum $ take k x | x <- tails fibk'])


> take 10 $ fibk 2
[0,1,1,2,3,5,8,13,21,34]

> take 10 $ fibk 3
[0,0,1,1,2,4,7,13,24,44]

> take 10 $ fibk 4
[0,0,0,1,1,2,4,8,15,29]
于 2012-06-12T01:08:33.273 に答える
0

よりも優れたものが必要だと思いますO(nk)。
の場合O(nk)、単純に計算できます。と
に上限がある場合は、マトリックスを一度作成して、値が必要なときにいつでもクエリを実行することもできます。 n <= Nk <= KNxK

EDIT
数学をさらに掘り下げたい場合は、Generalized Order- k Pell Numbersに関するこの論文を読むことができます。

于 2010-11-08T08:45:14.500 に答える