-1 
#include <iostream>
using namespace std;

int main() {
    int i=1;
    int j=0;
    int k=0;
    int h=1;
    int t=0;
    int n;
    cin>>n;

    while (n) {
        if (n%2) {
            t=j*h;
            j=i*h+j*k+t;
            i=ik+t;
        }

        t=h*h;
        h=2*k*h+t;
        k=k*k+t;
        n=n/2;
    }

    cout<<j;
    return 0;
}

これは、インターネットで見つけたフィボナッチの最速のアルゴリズムです。他のアルゴリズムは理解していますが、これは私には意味がありません。

このアルゴリズムが行列の乗算や二乗によるべき乗とどのように関連しているかわかりません。誰か説明できますか？

4

2 に答える 2

1

これは、フィボナッチ数を計算するための標準的な行列法です。変数 h、i、j、および k は、行列の 4 つの要素です。行列演算は「手書き」で書き出されます。

于 2013-12-03T22:00:01.703 に答える
1

マトリックスの解決策は、マトリックスを取ることです

1 1
0 1

そして、必要なフィボナッチ数に等しい累乗に上げます。log(n) ステップを使用してそれを行うことができます。累乗のバイナリ形式を使用します。各ステップで、行列をそれ自体で乗算し (指数に 2 を乗算するのと同じ)、ビットが 1 の場合は元の行列を乗算します (指数に 1 を加算するのと同じ)。

もう一度コードを確認してください。変数はマトリックス内の 4 つのセルをエンコードし、乗算ロジックのインライン化がありますが、それでも同じです。

于 2013-12-03T22:09:04.640 に答える