Clever Geek Handbook

フィボナッチ数を見つける

良い一日！

今日は、いくつかの再発を解決する方法について話し、このトピックに関する古典的な例を分析したいと思います。

繰り返しの式を定義することから始めましょう：

繰り返し式-表示式 シーケンスの各メンバーを表現する を通して 以前のメンバー。


非常に簡単に定式化される問題を考えてみましょう。Pを法とするN番目のフィボナッチ数を見つける必要があります。ここで、N <= 10 ^ 15、P <= 10 ^ 9です。 制限からわかるように、O（n）で自明な方法で数値を追加しても機能しません。より高速なアルゴリズムを考え出す必要があります。この記事では、漸近O（log N）の演算子メソッドに焦点を当てます。 列ベクトルがあるとします 、 -n番目のフィボナッチ数、演算子を見つけようとする 平等が成り立つように 。 フィボナッチ数の場合、繰り返し式を思い出せば、この演算子の行列を見つけるのは簡単です 、マトリックスは ほんとに 。 そして、演算子が最初のフィボナッチ数だけでなく、すべての人に適していることを考えると、 、私たちは持っています 。 そのため、演算子の行列をN乗することで答えを計算できます。これには、対数累乗のアルゴリズムを使用します。 Javaで記述されたコードは次のとおりです。

Copy Source | Copy HTML private static long getFibb( int n) { long a11 = 1 , a12 = 1 , a21 = 1 , a22 = 0 ; // long r11 = 1 , r12 = 0 ; //- long q11 = 0 , q12 = 0 , q21 = 0 , q22 = 0 ; // while (n > 0 ) { if ((n& 1 )== 1 ) { q11 = (r11 * a11 + r12 * a21) % MOD; q12 = (r11 * a12 + r12 * a22) % MOD; r11 = q11; r12 = q12; } q11 = (a11 * a11 + a12 * a21) % MOD; q12 = (a11 * a12 + a12 * a22) % MOD; q21 = (a21 * a11 + a22 * a21) % MOD; q22 = (a21 * a12 + a22 * a22) % MOD; a11 = q11; a12 = q12; a21 = q21; a22 = q22; n >>= 1 ; } return r12; // Fn }



  1. Copy Source | Copy HTML private static long getFibb( int n) { long a11 = 1 , a12 = 1 , a21 = 1 , a22 = 0 ; // long r11 = 1 , r12 = 0 ; //- long q11 = 0 , q12 = 0 , q21 = 0 , q22 = 0 ; // while (n > 0 ) { if ((n& 1 )== 1 ) { q11 = (r11 * a11 + r12 * a21) % MOD; q12 = (r11 * a12 + r12 * a22) % MOD; r11 = q11; r12 = q12; } q11 = (a11 * a11 + a12 * a21) % MOD; q12 = (a11 * a12 + a12 * a22) % MOD; q21 = (a21 * a11 + a22 * a21) % MOD; q22 = (a21 * a12 + a22 * a22) % MOD; a11 = q11; a12 = q12; a21 = q21; a22 = q22; n >>= 1 ; } return r12; // Fn }



  2. Copy Source | Copy HTML private static long getFibb( int n) { long a11 = 1 , a12 = 1 , a21 = 1 , a22 = 0 ; // long r11 = 1 , r12 = 0 ; //- long q11 = 0 , q12 = 0 , q21 = 0 , q22 = 0 ; // while (n > 0 ) { if ((n& 1 )== 1 ) { q11 = (r11 * a11 + r12 * a21) % MOD; q12 = (r11 * a12 + r12 * a22) % MOD; r11 = q11; r12 = q12; } q11 = (a11 * a11 + a12 * a21) % MOD; q12 = (a11 * a12 + a12 * a22) % MOD; q21 = (a21 * a11 + a22 * a21) % MOD; q22 = (a21 * a12 + a22 * a22) % MOD; a11 = q11; a12 = q12; a21 = q21; a22 = q22; n >>= 1 ; } return r12; // Fn }



  3. Copy Source | Copy HTML private static long getFibb( int n) { long a11 = 1 , a12 = 1 , a21 = 1 , a22 = 0 ; // long r11 = 1 , r12 = 0 ; //- long q11 = 0 , q12 = 0 , q21 = 0 , q22 = 0 ; // while (n > 0 ) { if ((n& 1 )== 1 ) { q11 = (r11 * a11 + r12 * a21) % MOD; q12 = (r11 * a12 + r12 * a22) % MOD; r11 = q11; r12 = q12; } q11 = (a11 * a11 + a12 * a21) % MOD; q12 = (a11 * a12 + a12 * a22) % MOD; q21 = (a21 * a11 + a22 * a21) % MOD; q22 = (a21 * a12 + a22 * a22) % MOD; a11 = q11; a12 = q12; a21 = q21; a22 = q22; n >>= 1 ; } return r12; // Fn }



  4. Copy Source | Copy HTML private static long getFibb( int n) { long a11 = 1 , a12 = 1 , a21 = 1 , a22 = 0 ; // long r11 = 1 , r12 = 0 ; //- long q11 = 0 , q12 = 0 , q21 = 0 , q22 = 0 ; // while (n > 0 ) { if ((n& 1 )== 1 ) { q11 = (r11 * a11 + r12 * a21) % MOD; q12 = (r11 * a12 + r12 * a22) % MOD; r11 = q11; r12 = q12; } q11 = (a11 * a11 + a12 * a21) % MOD; q12 = (a11 * a12 + a12 * a22) % MOD; q21 = (a21 * a11 + a22 * a21) % MOD; q22 = (a21 * a12 + a22 * a22) % MOD; a11 = q11; a12 = q12; a21 = q21; a22 = q22; n >>= 1 ; } return r12; // Fn }



  5. Copy Source | Copy HTML private static long getFibb( int n) { long a11 = 1 , a12 = 1 , a21 = 1 , a22 = 0 ; // long r11 = 1 , r12 = 0 ; //- long q11 = 0 , q12 = 0 , q21 = 0 , q22 = 0 ; // while (n > 0 ) { if ((n& 1 )== 1 ) { q11 = (r11 * a11 + r12 * a21) % MOD; q12 = (r11 * a12 + r12 * a22) % MOD; r11 = q11; r12 = q12; } q11 = (a11 * a11 + a12 * a21) % MOD; q12 = (a11 * a12 + a12 * a22) % MOD; q21 = (a21 * a11 + a22 * a21) % MOD; q22 = (a21 * a12 + a22 * a22) % MOD; a11 = q11; a12 = q12; a21 = q21; a22 = q22; n >>= 1 ; } return r12; // Fn }



  6. Copy Source | Copy HTML private static long getFibb( int n) { long a11 = 1 , a12 = 1 , a21 = 1 , a22 = 0 ; // long r11 = 1 , r12 = 0 ; //- long q11 = 0 , q12 = 0 , q21 = 0 , q22 = 0 ; // while (n > 0 ) { if ((n& 1 )== 1 ) { q11 = (r11 * a11 + r12 * a21) % MOD; q12 = (r11 * a12 + r12 * a22) % MOD; r11 = q11; r12 = q12; } q11 = (a11 * a11 + a12 * a21) % MOD; q12 = (a11 * a12 + a12 * a22) % MOD; q21 = (a21 * a11 + a22 * a21) % MOD; q22 = (a21 * a12 + a22 * a22) % MOD; a11 = q11; a12 = q12; a21 = q21; a22 = q22; n >>= 1 ; } return r12; // Fn }



  7. Copy Source | Copy HTML private static long getFibb( int n) { long a11 = 1 , a12 = 1 , a21 = 1 , a22 = 0 ; // long r11 = 1 , r12 = 0 ; //- long q11 = 0 , q12 = 0 , q21 = 0 , q22 = 0 ; // while (n > 0 ) { if ((n& 1 )== 1 ) { q11 = (r11 * a11 + r12 * a21) % MOD; q12 = (r11 * a12 + r12 * a22) % MOD; r11 = q11; r12 = q12; } q11 = (a11 * a11 + a12 * a21) % MOD; q12 = (a11 * a12 + a12 * a22) % MOD; q21 = (a21 * a11 + a22 * a21) % MOD; q22 = (a21 * a12 + a22 * a22) % MOD; a11 = q11; a12 = q12; a21 = q21; a22 = q22; n >>= 1 ; } return r12; // Fn }



  8. Copy Source | Copy HTML private static long getFibb( int n) { long a11 = 1 , a12 = 1 , a21 = 1 , a22 = 0 ; // long r11 = 1 , r12 = 0 ; //- long q11 = 0 , q12 = 0 , q21 = 0 , q22 = 0 ; // while (n > 0 ) { if ((n& 1 )== 1 ) { q11 = (r11 * a11 + r12 * a21) % MOD; q12 = (r11 * a12 + r12 * a22) % MOD; r11 = q11; r12 = q12; } q11 = (a11 * a11 + a12 * a21) % MOD; q12 = (a11 * a12 + a12 * a22) % MOD; q21 = (a21 * a11 + a22 * a21) % MOD; q22 = (a21 * a12 + a22 * a22) % MOD; a11 = q11; a12 = q12; a21 = q21; a22 = q22; n >>= 1 ; } return r12; // Fn }



  9. Copy Source | Copy HTML private static long getFibb( int n) { long a11 = 1 , a12 = 1 , a21 = 1 , a22 = 0 ; // long r11 = 1 , r12 = 0 ; //- long q11 = 0 , q12 = 0 , q21 = 0 , q22 = 0 ; // while (n > 0 ) { if ((n& 1 )== 1 ) { q11 = (r11 * a11 + r12 * a21) % MOD; q12 = (r11 * a12 + r12 * a22) % MOD; r11 = q11; r12 = q12; } q11 = (a11 * a11 + a12 * a21) % MOD; q12 = (a11 * a12 + a12 * a22) % MOD; q21 = (a21 * a11 + a22 * a21) % MOD; q22 = (a21 * a12 + a22 * a22) % MOD; a11 = q11; a12 = q12; a21 = q21; a22 = q22; n >>= 1 ; } return r12; // Fn }



  10. Copy Source | Copy HTML private static long getFibb( int n) { long a11 = 1 , a12 = 1 , a21 = 1 , a22 = 0 ; // long r11 = 1 , r12 = 0 ; //- long q11 = 0 , q12 = 0 , q21 = 0 , q22 = 0 ; // while (n > 0 ) { if ((n& 1 )== 1 ) { q11 = (r11 * a11 + r12 * a21) % MOD; q12 = (r11 * a12 + r12 * a22) % MOD; r11 = q11; r12 = q12; } q11 = (a11 * a11 + a12 * a21) % MOD; q12 = (a11 * a12 + a12 * a22) % MOD; q21 = (a21 * a11 + a22 * a21) % MOD; q22 = (a21 * a12 + a22 * a22) % MOD; a11 = q11; a12 = q12; a21 = q21; a22 = q22; n >>= 1 ; } return r12; // Fn }



  11. Copy Source | Copy HTML private static long getFibb( int n) { long a11 = 1 , a12 = 1 , a21 = 1 , a22 = 0 ; // long r11 = 1 , r12 = 0 ; //- long q11 = 0 , q12 = 0 , q21 = 0 , q22 = 0 ; // while (n > 0 ) { if ((n& 1 )== 1 ) { q11 = (r11 * a11 + r12 * a21) % MOD; q12 = (r11 * a12 + r12 * a22) % MOD; r11 = q11; r12 = q12; } q11 = (a11 * a11 + a12 * a21) % MOD; q12 = (a11 * a12 + a12 * a22) % MOD; q21 = (a21 * a11 + a22 * a21) % MOD; q22 = (a21 * a12 + a22 * a22) % MOD; a11 = q11; a12 = q12; a21 = q21; a22 = q22; n >>= 1 ; } return r12; // Fn }



  12. Copy Source | Copy HTML private static long getFibb( int n) { long a11 = 1 , a12 = 1 , a21 = 1 , a22 = 0 ; // long r11 = 1 , r12 = 0 ; //- long q11 = 0 , q12 = 0 , q21 = 0 , q22 = 0 ; // while (n > 0 ) { if ((n& 1 )== 1 ) { q11 = (r11 * a11 + r12 * a21) % MOD; q12 = (r11 * a12 + r12 * a22) % MOD; r11 = q11; r12 = q12; } q11 = (a11 * a11 + a12 * a21) % MOD; q12 = (a11 * a12 + a12 * a22) % MOD; q21 = (a21 * a11 + a22 * a21) % MOD; q22 = (a21 * a12 + a22 * a22) % MOD; a11 = q11; a12 = q12; a21 = q21; a22 = q22; n >>= 1 ; } return r12; // Fn }



  13. Copy Source | Copy HTML private static long getFibb( int n) { long a11 = 1 , a12 = 1 , a21 = 1 , a22 = 0 ; // long r11 = 1 , r12 = 0 ; //- long q11 = 0 , q12 = 0 , q21 = 0 , q22 = 0 ; // while (n > 0 ) { if ((n& 1 )== 1 ) { q11 = (r11 * a11 + r12 * a21) % MOD; q12 = (r11 * a12 + r12 * a22) % MOD; r11 = q11; r12 = q12; } q11 = (a11 * a11 + a12 * a21) % MOD; q12 = (a11 * a12 + a12 * a22) % MOD; q21 = (a21 * a11 + a22 * a21) % MOD; q22 = (a21 * a12 + a22 * a22) % MOD; a11 = q11; a12 = q12; a21 = q21; a22 = q22; n >>= 1 ; } return r12; // Fn }



  14. Copy Source | Copy HTML private static long getFibb( int n) { long a11 = 1 , a12 = 1 , a21 = 1 , a22 = 0 ; // long r11 = 1 , r12 = 0 ; //- long q11 = 0 , q12 = 0 , q21 = 0 , q22 = 0 ; // while (n > 0 ) { if ((n& 1 )== 1 ) { q11 = (r11 * a11 + r12 * a21) % MOD; q12 = (r11 * a12 + r12 * a22) % MOD; r11 = q11; r12 = q12; } q11 = (a11 * a11 + a12 * a21) % MOD; q12 = (a11 * a12 + a12 * a22) % MOD; q21 = (a21 * a11 + a22 * a21) % MOD; q22 = (a21 * a12 + a22 * a22) % MOD; a11 = q11; a12 = q12; a21 = q21; a22 = q22; n >>= 1 ; } return r12; // Fn }



  15. Copy Source | Copy HTML private static long getFibb( int n) { long a11 = 1 , a12 = 1 , a21 = 1 , a22 = 0 ; // long r11 = 1 , r12 = 0 ; //- long q11 = 0 , q12 = 0 , q21 = 0 , q22 = 0 ; // while (n > 0 ) { if ((n& 1 )== 1 ) { q11 = (r11 * a11 + r12 * a21) % MOD; q12 = (r11 * a12 + r12 * a22) % MOD; r11 = q11; r12 = q12; } q11 = (a11 * a11 + a12 * a21) % MOD; q12 = (a11 * a12 + a12 * a22) % MOD; q21 = (a21 * a11 + a22 * a21) % MOD; q22 = (a21 * a12 + a22 * a22) % MOD; a11 = q11; a12 = q12; a21 = q21; a22 = q22; n >>= 1 ; } return r12; // Fn }



  16. Copy Source | Copy HTML private static long getFibb( int n) { long a11 = 1 , a12 = 1 , a21 = 1 , a22 = 0 ; // long r11 = 1 , r12 = 0 ; //- long q11 = 0 , q12 = 0 , q21 = 0 , q22 = 0 ; // while (n > 0 ) { if ((n& 1 )== 1 ) { q11 = (r11 * a11 + r12 * a21) % MOD; q12 = (r11 * a12 + r12 * a22) % MOD; r11 = q11; r12 = q12; } q11 = (a11 * a11 + a12 * a21) % MOD; q12 = (a11 * a12 + a12 * a22) % MOD; q21 = (a21 * a11 + a22 * a21) % MOD; q22 = (a21 * a12 + a22 * a22) % MOD; a11 = q11; a12 = q12; a21 = q21; a22 = q22; n >>= 1 ; } return r12; // Fn }



  17. Copy Source | Copy HTML private static long getFibb( int n) { long a11 = 1 , a12 = 1 , a21 = 1 , a22 = 0 ; // long r11 = 1 , r12 = 0 ; //- long q11 = 0 , q12 = 0 , q21 = 0 , q22 = 0 ; // while (n > 0 ) { if ((n& 1 )== 1 ) { q11 = (r11 * a11 + r12 * a21) % MOD; q12 = (r11 * a12 + r12 * a22) % MOD; r11 = q11; r12 = q12; } q11 = (a11 * a11 + a12 * a21) % MOD; q12 = (a11 * a12 + a12 * a22) % MOD; q21 = (a21 * a11 + a22 * a21) % MOD; q22 = (a21 * a12 + a22 * a22) % MOD; a11 = q11; a12 = q12; a21 = q21; a22 = q22; n >>= 1 ; } return r12; // Fn }



  18. Copy Source | Copy HTML private static long getFibb( int n) { long a11 = 1 , a12 = 1 , a21 = 1 , a22 = 0 ; // long r11 = 1 , r12 = 0 ; //- long q11 = 0 , q12 = 0 , q21 = 0 , q22 = 0 ; // while (n > 0 ) { if ((n& 1 )== 1 ) { q11 = (r11 * a11 + r12 * a21) % MOD; q12 = (r11 * a12 + r12 * a22) % MOD; r11 = q11; r12 = q12; } q11 = (a11 * a11 + a12 * a21) % MOD; q12 = (a11 * a12 + a12 * a22) % MOD; q21 = (a21 * a11 + a22 * a21) % MOD; q22 = (a21 * a12 + a22 * a22) % MOD; a11 = q11; a12 = q12; a21 = q21; a22 = q22; n >>= 1 ; } return r12; // Fn }



  19. Copy Source | Copy HTML private static long getFibb( int n) { long a11 = 1 , a12 = 1 , a21 = 1 , a22 = 0 ; // long r11 = 1 , r12 = 0 ; //- long q11 = 0 , q12 = 0 , q21 = 0 , q22 = 0 ; // while (n > 0 ) { if ((n& 1 )== 1 ) { q11 = (r11 * a11 + r12 * a21) % MOD; q12 = (r11 * a12 + r12 * a22) % MOD; r11 = q11; r12 = q12; } q11 = (a11 * a11 + a12 * a21) % MOD; q12 = (a11 * a12 + a12 * a22) % MOD; q21 = (a21 * a11 + a22 * a21) % MOD; q22 = (a21 * a12 + a22 * a22) % MOD; a11 = q11; a12 = q12; a21 = q21; a22 = q22; n >>= 1 ; } return r12; // Fn }



  21. Copy Source | Copy HTML private static long getFibb( int n) { long a11 = 1 , a12 = 1 , a21 = 1 , a22 = 0 ; // long r11 = 1 , r12 = 0 ; //- long q11 = 0 , q12 = 0 , q21 = 0 , q22 = 0 ; // while (n > 0 ) { if ((n& 1 )== 1 ) { q11 = (r11 * a11 + r12 * a21) % MOD; q12 = (r11 * a12 + r12 * a22) % MOD; r11 = q11; r12 = q12; } q11 = (a11 * a11 + a12 * a21) % MOD; q12 = (a11 * a12 + a12 * a22) % MOD; q21 = (a21 * a11 + a22 * a21) % MOD; q22 = (a21 * a12 + a22 * a22) % MOD; a11 = q11; a12 = q12; a21 = q21; a22 = q22; n >>= 1 ; } return r12; // Fn }



  22. Copy Source | Copy HTML private static long getFibb( int n) { long a11 = 1 , a12 = 1 , a21 = 1 , a22 = 0 ; // long r11 = 1 , r12 = 0 ; //- long q11 = 0 , q12 = 0 , q21 = 0 , q22 = 0 ; // while (n > 0 ) { if ((n& 1 )== 1 ) { q11 = (r11 * a11 + r12 * a21) % MOD; q12 = (r11 * a12 + r12 * a22) % MOD; r11 = q11; r12 = q12; } q11 = (a11 * a11 + a12 * a21) % MOD; q12 = (a11 * a12 + a12 * a22) % MOD; q21 = (a21 * a11 + a22 * a21) % MOD; q22 = (a21 * a12 + a22 * a22) % MOD; a11 = q11; a12 = q12; a21 = q21; a22 = q22; n >>= 1 ; } return r12; // Fn }



  23. Copy Source | Copy HTML private static long getFibb( int n) { long a11 = 1 , a12 = 1 , a21 = 1 , a22 = 0 ; // long r11 = 1 , r12 = 0 ; //- long q11 = 0 , q12 = 0 , q21 = 0 , q22 = 0 ; // while (n > 0 ) { if ((n& 1 )== 1 ) { q11 = (r11 * a11 + r12 * a21) % MOD; q12 = (r11 * a12 + r12 * a22) % MOD; r11 = q11; r12 = q12; } q11 = (a11 * a11 + a12 * a21) % MOD; q12 = (a11 * a12 + a12 * a22) % MOD; q21 = (a21 * a11 + a22 * a21) % MOD; q22 = (a21 * a12 + a22 * a22) % MOD; a11 = q11; a12 = q12; a21 = q21; a22 = q22; n >>= 1 ; } return r12; // Fn }



  24. Copy Source | Copy HTML private static long getFibb( int n) { long a11 = 1 , a12 = 1 , a21 = 1 , a22 = 0 ; // long r11 = 1 , r12 = 0 ; //- long q11 = 0 , q12 = 0 , q21 = 0 , q22 = 0 ; // while (n > 0 ) { if ((n& 1 )== 1 ) { q11 = (r11 * a11 + r12 * a21) % MOD; q12 = (r11 * a12 + r12 * a22) % MOD; r11 = q11; r12 = q12; } q11 = (a11 * a11 + a12 * a21) % MOD; q12 = (a11 * a12 + a12 * a22) % MOD; q21 = (a21 * a11 + a22 * a21) % MOD; q22 = (a21 * a12 + a22 * a22) % MOD; a11 = q11; a12 = q12; a21 = q21; a22 = q22; n >>= 1 ; } return r12; // Fn }





私たちの答えを与えるだけです：

Copy Source | Copy HTML



  1. out .println（getFibb（N））;


ご清聴ありがとうございました。


More articles:


All Articles