~斐波那契算法~

1.非递归算法

long long Fibonacci(size_t n)
{
	long long first = 0;  //用int时范围过小，有溢出
	long long second = 1;
	long long ret = 0;

	if(n < 2)
	{
		return n;
	}

	for(size_t i=1; i<n; ++i)  //i是记录循环次数，与i的取值范围无关
	{
		ret = first + second;
		first = second;
		second = ret;
	}

	return ret;
}

2.递归算法

long long Fibonacci(size_t n)
{
	if(n < 2)
	{
		return n;
	}

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

3.斐波那契数组

long long* FibonacciArray(size_t n)
{
	long long* array = new long long[n + 1];  //若n=0时，数组只有一个数字：0

	array[0] = 0;

	if(n > 0)
	{
		array[1] = 1;
	
		for(size_t i=2; i<n+1; ++i)  //i是记录数组下标，与i的取值范围有关
		{
			array[i] = array[i-1] + array[i-2];
		}
	}

	return array;
}

4.测试用例

int main()
{
	//斐波那契算法测试用例
	cout<<Fibonacci(0)<<endl;
	cout<<Fibonacci(1)<<endl;
	cout<<Fibonacci(2)<<endl;
	cout<<Fibonacci(3)<<endl;
	cout<<Fibonacci(4)<<endl;
	cout<<Fibonacci(5)<<endl;
	cout<<Fibonacci(6)<<endl;
	cout<<Fibonacci(7)<<endl;
	cout<<Fibonacci(8)<<endl;
	cout<<Fibonacci(9)<<endl;

	//斐波那契数组测试用例
	long long* array = FibonacciArray(9);

	for(size_t i=0; i<=9; ++i)
	{
		cout<<array[i]<<" ";
	}
	cout<<endl;

	system("pause");
	return 0;
}