[数据结构与算法]斐波那契数

（南昌理工学院acm集训队）

题目：

F(0)=0,? F(1)=1,? F(n)=F(n-1)+F(n-2)。

输入一个非负整数n，求第n项的值F(N);

思路：

求F(n)只需要知道它的前两项，并且知道了第一项和第二项，从第三项依次递推就可以算出F(n)了。

代码如下：

#include<stdio.h>
int main()
{
    int frist=0,second=1;     //定义初始变量；
    int n,f;                  //定义要输入的n和第n项的数f；
    scanf("%d",&n);           //输入n；   
    for(int i=2;i<=n;i++)
    {
        f = frist + second;     //f(n)=f(n-2)+f(n-1);
        frist = second;       //frist=f(n-1);
        second = f;       //second=f(n),之后继续计算f(n+1);           
    }
    if(n<2)
    printf("%d",n);         //如果n等于0或1直接返回n，因为F(0)=0,F(1)=1;       
    else
    printf("%d",f);        //若不小于2，则输出f；
}

?总结：

这题属于动态规划最基础最简单的一道了，奈何水平有限，水平提升再研究难题吧。