斐波那契数列求第n项的值

求斐波那契数列第n项的值

百度到的斐波那契数列定义：

斐波那契数列（ ），又称黄金分割数列、因数学家列昂纳多·斐波那契（ ）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*）

方法一：递归

数列的第n项（除第1项和第2项）是第n-1项与第n-2项的和。数列满足递归的关系，故可用递归算法求第n项的值。

用递归求解，最重要的事是确定结束条件，给算法一个出口。本题中结束递归的条件为：n等于1或n等于2。

算法如下：

int (int* n)

step1:若n等于1或n等于2， 1;否则，进入step2;

step2: (n-1)+(n-2);

代码实现：

int Fibonacci(int* n)
{
	if(n==1||n==2)
		return 1;
	else
		return Fibonacci(n-1)+Fibonacci(n-2);
}

方法二：迭代

从斐波那契数列的第1项开始，按递推公式找到数列的每一项的值，直到找到第n项的值。

1 1 -> 1 1 2 -> 1 1 2 3 -> 1 1 2 3 5-> 1 1 2 3 5 8 -> …

代码如下：

int Fibonacci(int* n)
{
	int i, n1=1, n2=1, sum=0;
	for(i=3;i<=n;i++)
	{
		sum = n1+n2;
		n1 = n2;
		n2 = sum;
	}
	return sum;
}

方法三：用栈还原方法一的递归算法（注：本方法纯属个人练手，可跳过）

本题方法一的递归算法，有点类似二叉树的中序遍历。趁最近正在学二叉树，感觉非常打脑壳，用这个斐波那契数列递归算法非递归化找下手感。

直接放伪代码了：

int Fibonacci (int n)
{
	if(n==0||n==1)
		return 1;
	answer=0;
	for(i=n;;i--)//n到2依次入栈
	{
		if(i==1)
		{
			answer += 1;
			//i等于1，不入栈，把第2项的数值1加在answer上
			break;
		}
		else
			push(stack, i);//i大于1就入栈
	}
	while(!empty(stack)) 
	{
		top = gettop(stack);
		if(top-2==0||top-2==1)//如果栈顶的数值-2等于0或1，把数值1加到answer上（第1项的值和第2项的都等于1）
		{
			answer += 1;
			pop(stack);//此时top项已经计算完了（top-1项和top-2项的值都加在了answer上），弹出top项
		}
		else
		{
			pop(stack);
			push(stack, top-2);
			for(i=gettop(stack)-1;;i--)//top-1到2依次入栈
			{
				if(i==1)
				{
					answer += 1; 
					//i等于1，不入栈，把第2项的数值1加在answer上	
					break;
				}
				else
					push(stack, i); //i大于1就入栈
			}
		}
	}
	return answer;//最后，answer即为第n项的值
}

完