很簡單的一道題膨蛮，可以參考 wise 的筆記，三種方法季研，遞歸敞葛、迭代、矩陣快速冪与涡，下面直接上C++代碼惹谐。
// 遞歸
int fib(int N) {
if(N == 0)
return 0;
else if(N == 1)
return 1;
else{
int result = 0;
result = fib(N - 1) + fib(N - 2);
return result;
}
}
image.png
然后是迭代，wise 說是簡單的動(dòng)規(guī)
// 迭代
int fib(int N) {
int a = 0;
int b = 1;
int c = 1;
int temp = 0;
for(int i = N; i > 0; i--){
temp = b + c;
a = b;
b = c;
c = temp;
}
return a;
}
image.png
可以說非常牛逼了
最后是復(fù)雜度 logn 的矩陣快速冪
// 矩陣
int fib(int N) {
int pow = N;
int base[2][2] = {{1,1},{1,0}};
int mulbase[2][2] = {{1,1},{1,0}};
int temp[2][2] = {{1,0},{0,1}};
int result[2][2] = {{1,0},{0,1}};
for(pow = N; pow != 0; pow >>= 1){
if(pow & 1){
result[0][0] = temp[0][0] * base[0][0] + temp[0][1] * base[1][0];
result[0][1] = temp[0][0] * base[0][1] + temp[0][1] * base[1][1];
result[1][0] = temp[1][0] * base[0][0] + temp[1][1] * base[1][0];
result[1][1] = temp[1][0] * base[0][1] + temp[1][1] * base[1][1];
}
mulbase[0][0] = base[0][0] * base[0][0] + base[0][1] * base[1][0];
mulbase[0][1] = base[0][0] * base[0][1] + base[0][1] * base[1][1];
mulbase[1][0] = base[1][0] * base[0][0] + base[1][1] * base[1][0];
mulbase[1][1] = base[1][0] * base[0][1] + base[1][1] * base[1][1];
for(int i = 0; i < 2; i++){
for(int j = 0; j < 2; j++){
temp[i][j] = result[i][j];
base[i][j] = mulbase[i][j];
}
}
}
return result[1][0];
}
代碼比較多驼卖，但是復(fù)雜度低了氨肌，在運(yùn)算比較大的數(shù)據(jù)時(shí)候有優(yōu)勢。
image.png
