计算斐波那契数列

日期: 08 月 27日, 2014
标签:

斐波那契数列的定义为：

  • F0 = 0
  • F1 = 1
  • Fn = Fn-1 + Fn-2 (n≥2)

即：斐波那契数列由0和1开始，之后的每一项均为之前的两数之和。

计算方法

递归法

unsigned long fibonacci(unsigned long n)
{
	if (n == 0)
	{
		return 0;
	}
	else if (n == 1)
	{
		return 1;
	}
	else
	{
		return fibonacci(n-1) + fibonacci(n-2)
	}
}

迭代法

unsigned long fibonacci(unsigned long n)
{
	unsigned long fib1 = 0, fib2 = 1;
	if (n == 0)
	{
		return 0;
	}
	else if (n == 1)
	{
		return 1;
	}
	else
	{
		while (n > 1)
		{
			unsigned long tmp = fib2;
			fib2 = fib1 + fib2;
			fib1 = tmp;
			n--;
		}
		return fib2;
	}
}

矩阵

矩阵的乘方可以用快速幂运算来做，时间复杂度为 O(log n)。

unsigned long fibonacci(unsigned long n)
{
	register unsigned long pow[2][2] = { {1, 1}, {1, 0} };
	register unsigned long fib[2][2] = { {1, 0}, {0, 1} };

	while (n > 0)
	{
		register unsigned long tmp[2][2];
		if (n & 1)
		{
			tmp[0][0] = fib[0][0];
			tmp[0][1] = fib[0][1];
			tmp[1][0] = fib[1][0];
			tmp[1][1] = fib[1][1];
			fib[0][0] = tmp[0][0] * pow[0][0] + tmp[0][1] * pow[1][0];
			fib[0][1] = tmp[0][0] * pow[0][1] + tmp[0][1] * pow[1][1];
			fib[1][0] = tmp[1][0] * pow[0][0] + tmp[1][1] * pow[1][0];
			fib[1][1] = tmp[1][0] * pow[0][1] + tmp[1][1] * pow[1][1];
		}
		tmp[0][0] = pow[0][0];
		tmp[0][1] = pow[0][1];
		tmp[1][0] = pow[1][0];
		tmp[1][1] = pow[1][1];
		pow[0][0] = tmp[0][0] * tmp[0][0] + tmp[0][1] * tmp[1][0];
		pow[0][1] = tmp[0][0] * tmp[0][1] + tmp[0][1] * tmp[1][1];
		pow[1][0] = tmp[1][0] * tmp[0][0] + tmp[1][1] * tmp[1][0];
		pow[1][1] = tmp[1][0] * tmp[0][1] + tmp[1][1] * tmp[1][1];
		n >>= 1;
	}

	return fib[0][1];
}