fibonacci数列

原文链接

解决了我一直没能理解的矩阵求fibonacci的困惑，原文链接：http://hawstein.com/posts/8.1.html

题目

写一个函数来产生第n个fibonacci数

解答

fibonacci数列的定义如下：

f(1) = f(2) = 1;
f(n) = f(n - 1) + f(n - 2);

根据递推公式，我们很容易写出递归和非递归代码

递归：

/**
 * 递归实现fibonacci数列
 */
long long int recursionFib(long long int n)
{
	if (n < 1)
		return -1;
	if (n == 1)
		return 1;
	if (n == 2)
		return 1;

	return recursionFib(n - 1) + recursionFib(n - 2);
}

非递归：

/**
 * 非递归实现fibonacci数列
 *
 * T = O(n)
 *
 */
long long int nonrecursionFib(int n)
{
	if (n < -1)
		return -1;
	if (n == 1)
		return 1;
	if (n == 2)
		return 1;

	long long int i, a, b, c;

	for (a = b = 1, i = 3; i <= n; i ++) {
		c = a + b;
		a = b;
		b = c;
	}

	return c;
}

非递归的时间复杂度已经是O(n),看起来简单快速，可是，我们还有更快的解决方法。根据上面的递推公式，我们可以得到它的矩阵版本：

继续化简得：

从上图可以看出，写成矩阵递推形式，可以让我们一推到底。最后的f(1) = f(2) = 1，因此，这个问题就转换成了，如何求矩阵的幂。要快速，不然就没什么意义了。我们先把问题退化一下，先不考虑矩阵的幂，如何求一个整数的幂。

/**
 * 求data的n次幂
 */
void numpow(long long int data, int n)
{
	long long int i, rs;

	for (i = 1, rs = 1; i <= n; i ++) {
		rs *= data;
	}

	printf("%lld\n", rs);
}

时间复杂度为O(n).现在让我们来考虑一种更快速的方法，假设我们要求m^13,然后我们把13写成二进制形式13 = 1101，一开始结果res = 1,我们要计算的幂可以写成：

m^13 = m^1 * m^4 * m^8

我们可以很直观的得出，如果指数13的二进制形式1101中某一位是1,那么，res就去乘以那一位对应的一个数

/**
 * 快速求data的n次幂
 *
 * T = O(logn)
 *
 */
void quickPow(long long int data, int n)
{
	long long int res;

	res = 1;

	while (n) {
		if (n & 1)	res *= data;

		data *= data;

		n >>= 1;
	}

	printf("%lld\n", res);
}

时间复杂度为O（logn）,正是我们想要的快速版本。OK，这时候如果让你快速求矩阵的幂，是不是很简单了？只需要将实数乘法改成矩阵乘法即可

long long int s[2][2] = {{1, 0}, {0, 1}};
long long int f[2][2] = {{1, 1}, {1, 0}};


/**
 * 矩阵乘法
 */
void multiMatrix(long long int c[2][2], long long int a[2][2], long long int b[2][2])
{
	long long int i, j, k, t[2][2];
	
	memset(t, 0, sizeof(t));


	for (i = 0; i < 2; i ++) {
		for (j = 0; j < 2; j ++) {
			t[i][j] = 0;
			for (k = 0; k < 2; k ++) {
				t[i][j] += a[i][k] * b[k][j];
			}
		}
	}
	
	for (i = 0; i < 2; i ++) {
		for (j = 0; j < 2; j ++)
			c[i][j] = t[i][j];
	}
}

/**
 * 快速求fibonacci数列
 *
 * T = O(logn)
 *
 */
long long int quickFib(int n, long long int s[2][2], long long int f[2][2])
{
	if (n < 1)	return -1;
	if (n == 1 || n == 2)	return 1;

	n = n - 2;
	while (n) {
		if (n & 1)	multiMatrix(s, f, s);

		multiMatrix(f, f, f);

		n >>= 1;
	}

	return s[0][0] + s[0][1];
}