斐波那契數列相信大家都不陌生，從第三項開始每一項都是前兩項的和，
F(N)=F(N-1)+F(N-2)(N>2);//假設不存在F(0)
想想最初我們是怎么做的：
int fibo(int n){
if(n<=2){
return 1;
}
return fibo(n-1)+fibo(n-2);
}相信大家對這段代碼并不陌生(遞回可是困擾俺好久)
雖然這么寫很方便，但是n稍微大一點就需要很長時間，所以聰明的程式員們就想出了優化版本（利用迭代）
?
int fibo(int n){
int a = 1, b = 1, c=0;
if (n <= 2){
return 1;
}
for (int i = 3; i <= n; i++){
c = a + b;
a = b;
b = c;
}
return c;
}
?利用三個變數不斷回圈迭代最終得到結果（這樣比遞回快不少嘞）
但是隨著n繼續增大，貌似迭代也不能滿足人們對效率的追求，于是我們今天的主角矩陣快速冪就誕生了，
我們先來了解一下什么是快速冪
假如要求一個數的 n 次方，我們首先想到的思路是這樣的
int pow(int num, int n){
int res = 1;
for (int i = 1; i <= n; i++){
res *= num;
}
return res;
}一個為1的變數乘n次num就得到了num的n次方（只考慮正整數的話）
但是這樣就要計算n次，怎么才能計算的更快呢，我們考慮把n表示成二進制的形式
舉個例子，假如現在要計算 21 的 9 次方
上面的方法我們要計算9次
不妨我們把九轉化成二進制
然后讓從低到高一次遍歷每個位，第一個位代表 21 的 1 次方，第二個位代表 21的 2 次方，
第三個位代表21的4次方，第四個位代表21的8次方，當這個位為 1 時res*=21的某次方，為零時不管
也就是res=1; res*=21^1; res*=21^8;
res-->1-->21^1-->21^9;
好的我們來看下代碼
long long q_pow(int num, int n){
long long res = 1;
while (n){
if (n & 1){
res *= num;
}
num *= num;
n >>= 1;
}
return res;
}！！！！（不要試21的九次方哦，long long都放不下）
這樣就把O(n)的復雜度優化成了O（logN），
既然是矩陣快速冪，那必然是要與矩陣產生聯系的（默認大家學過線性代數了哈）
（請原諒我這殘廢的雙手）
F（N）=A*F(N-1)+B*F(N-2)
然而F（N-1）與F（N-2）這個矩陣可以繼續遞推
這樣的話我們就得到了兩個常矩陣的乘積，A，B，F1，F2都是已知的，只要快速求出前面矩陣的N-1次冪在與后面矩陣相乘，結果矩陣的第一行第一列就是我們要的答案了，
但是前面的常量矩陣是要自己推導的！！！一般情況下遞推式有n項常矩陣n×n
下面我們來看下具體代碼怎么寫
#include<iostream>
using namespace std;
typedef struct matrix{
int arr[2][2];
matrix operator*(matrix &B){//為方便操作多載*運算子，也可以封裝函式實作
matrix res = {0};
for (int i = 0; i < 2; i++){
for (int j = 0; j < 2; j++){
for (int k = 0; k < 2; k++){
res.arr[i][j] += arr[i][k] * B.arr[k][j];
}
}
}
return res;
}
}matrix;
matrix q_pow(matrix A,int n){
matrix tem = { 1, 0, 0, 1 };
if (n < 0){
return tem;
}
while (n){
if (n & 1){
tem = tem*A;
}
A = A*A;//!!!(不要用*=，因為我們沒多載*=運算子)
n >>= 1;
}
return tem;
}
int main(){
int n;//n代表遞推式多少項
int A, B,a,b;//A，B表示遞推式系數a,b 表示F1，F2
cin >>n>> A >> B >> a >> b;
matrix T = { A,B,1,0 };//我們推導的常矩陣
T=q_pow(T, n-2);//T表示常矩陣的n-2次冪
long long res = T.arr[0][0] * b + T.arr[0][1] * a;
cout << res << endl;
while (1);
return 0;
}
我們可以簡單測驗下
然后寫一個最簡單的遞回版本
答案是ok的（過大的常數是會導致資料溢位的）
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/305436.html
標籤：java
上一篇：Java堆疊和佇列的實作