首页 > 代码库 > 每日一小练——高速Fibonacci数算法
每日一小练——高速Fibonacci数算法
上得厅堂,下得厨房,写得代码,翻得围墙,欢迎来到睿不可挡的每日一小练!
题目:高速Fibonacci数算法
内容:先说说Fibonacci数列,它的定义是数列:f1,f2....fn有例如以下规律:
尝试寻找高速的求出fn的方法
我的解法:上来没多想,打开vs2013就敲了起来,问题果然非常easy,分分钟就超神。。奥,不正确就攻克了!
事实上题目中就给出了这个算法的递归形式,所以首先我想到的是递归解法,只是由于求解高速方法在递归之前,我编写了一个非递归的算法
#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语言名题精选百则》
每日一小练——高速Fibonacci数算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。