上得厅堂。下得厨房。写得代码，翻得围墙，欢迎来到睿不可挡的每日一小练！

题目：高速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语言名题精选百则》