大前端

前端学习之家-大前端

斐波那契数列

斐波那契数列数列,又叫做兔子数列,因数学家莱昂纳多·斐波那契(Leonardo Fibonacci)以兔子繁殖为例子而引入。描述的是这样的一个数列,0,1,1,2,3,5,8…有两种写法,一种是递归法,一种是动态规划法。
一,递归法
递归需要用到栈,一般需要一个递推的公式,还需要一个递归的终止条件,这里的终止条件就是当n等于0,或者当n等于1的时候。

int fib(int n)
{
	if (n == 0)
	{
		return 0;
	}
	else if (n == 1)
	{
		return 1;
	}
	else
	{
		return fib(n - 1) + fib(n - 2);
	}
}

二,动态规划法
第一种方法有一个缺点就是需要重复计算,比如fin[1],fin[0]就重复计算了好多次,如果可以把这些计算保存下来,就可以节约计算成本。这样就需要申请一个数组,保存计算的值。
动态规划法思路

#include <iostream>
using namespace std;
int vec[100] = { 0 };
int fib2(int n)
{
	int res;//接收结果。
	res = vec[n];
	if (res == 0)
	{
		if (n == 0)
		{
			return 0;
		}
		else if (n == 1)
		{
			return 1;
		}
		else
		{
			return fib2(n - 1) + fib2(n - 2);
		}
		vec[n] = res;
	}
	return res;
}

发表评论:

Copyright Your WebSite.Some Rights Reserved.