CCF NOI1064 计算斐波那契第n项

问题链接：CCF NOI1064 计算斐波那契第n项。

时间限制: 1000 ms 空间限制: 262144 KB

题目描述

输入n，编写程序输出斐波那契数列的第n项。其中斐波那契数列f(n)的定义如下：
f(1)=0,f(2)=1
f(n)=f(n-1)+f(n-2)(n>=2)

输入

一行一个正整数n。

输出

输出一个数f(n)。

样例输入

5
样例输出

数据范围限制

1<=n<=30

问题分析

这是一个简单的经典的著名的问题。斐波那契数列的是递归定义的，但是可以用递推来实现。

输入的n被限制在30以内，所以用long类型就可以了。

程序说明

函数fib()封装了计算斐波那契数列第n项的功能，并且用递推来实现。

要点详解

用函数封装功能是一个好的做法。
能用递推就不用递归，递归的代码逻辑往往比递推要简洁，但是通常时间上要慢并且需要更多的存储。

参考链接：（略）。

100分通过的C语言程序：

#include <stdio.h>

long fib(int n)
{
    long f1=0, f2=1, temp;
    int i;

    if(n == 1)
        return 0;
    if(n == 2)
        return 1;
    for(i=3; i<=n; i++) {
        temp = f1 + f2;
        f1 = f2;
        f2 = temp;
    }

    return f2;
}

int main(void)
{
    int n;

    scanf("%d", &n);

    printf("%ld
", fib(n));

    return 0;
}