上得廳堂,下得廚房,寫得代碼,翻得圍牆,歡迎來到睿不可擋的每日一小練!
題目:快速Fibonacci數算法
内容:先說說Fibonacci數列,它的定義是數列:f1,f2....fn有如下規律:
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsICM1ITN0ETMxETMyUDM0EDMy8CX0Vmbu4GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.jpg)
嘗試尋找快速的求出fn的方法
我的解法:上來沒多想,打開vs2013就敲了起來,問題果然很簡單,分分鐘就超神。。奧,不對就解決了!
其實題目中就給出了這個算法的遞歸形式,是以首先我想到的是遞歸解法,不過因為求解快速方法在遞歸之前,我編寫了一個非遞歸的算法
#include <iostream>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
int f(int n);
cout << f(7) << endl;
getchar();
return 0;
}
int f(int n)
{
int temp = 0, f1 = 1, f2 = 1;
if (n == 1 || n == 2)
return 1;
else
{
for (int i = 1; i < (n - 1); i++)
{
temp = f1 + f2;
f2 = f1;
f1 = temp;
}
return temp;
}
}
然後我又編寫了遞歸的算法
#include <iostream>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
int f(int n);
cout << f(7) << endl;
getchar();
return 0;
}
int f(int n)
{
if (n == 1|| n==2)
return 1;
if (n > 2)
return f(n - 1) + f(n - 2);
}
在遞歸的基礎上,有人提出了更犀利的算法,這個我沒有想到。。慚愧。。。
這個算法利用了一些技巧矩陣,通過矩陣乘法來算Fibonacci的加法,然後通過我在《數值自乘非遞歸解》中提到的利用區分奇偶數來利用指數二進制堆乘的方法,減少乘法的次數。
ps:
利用上面的矩陣連乘,在矩陣11位置的數就是矩陣11和21的和,并且用矩陣11和21表示Fibonacci的f(n-1)和f(n-2),通過連乘來求fn。
#include <iostream>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
int f(int n);
cout << f(7) << endl;
getchar();
return 0;
}
int f(int n)
{
void matrix_power(int a, int b, int c, int d, int n, int *aa, int *bb, int *cc, int *dd);
int a, b, c, d;
if (n == 1 || n == 2)
{
return 1;
}
else
{
matrix_power(1, 1, 1, 0, n - 2, &a, &b, &c, &d);
return a + b;
}
}
void matrix_power(int a, int b, int c, int d, int n, int *aa, int *bb, int *cc, int *dd)
{
int xa, xb, xc, xd;
if (n == 1)
*aa = a, *bb = b, *cc = c, *dd = d;
else if (n & 0x01 == 1)
{
matrix_power(a, b, c, d, n - 1, &xa, &xb, &xc, &xd);
*aa = a*xa + b*xc;
*bb = a*xb + b*xd;
*cc = c*xa + d*xc;
*dd = c*xb + d*xd;
}
else
{
matrix_power(a, b, c, d, n >> 1, &xa, &xb, &xc, &xd);
*aa = xa*xa + xb*xc;
*bb = xa*xb + xb*xd;
*cc = xc*xa + xd*xc;
*dd = xc*xb + xd*xd;
}
}
三段代碼的實驗結果同如下:
歡迎大家加入每日一小練,嘿嘿!
每天練一練,日久見功夫,加油!
-End-
參考文獻:《c語言名題精選百則》