3.5 菲波那契数

3.5.1 链接地址

http://www.realoj.com/网上第72题

3.5.2 题目内容

菲波那契（Fibonacci）数（简称菲氏数）定义为：

如果写出菲氏数列，则应该是：

        0 1 1 2 3 5 8 13 21 34 …

如果求其第6项，则应为8。

求第n项菲氏数。

输入描述：输入数据含有不多于50个的正整数n（0≤n≤46）。

输出描述：对于每个n，计算其第n项菲氏数，每个结果应单独占一行。

输入样例

        6 10

输出样例

        8
        55

3.5.3 参考答案

先把第0项到第46项的菲波那契数求出来，放在一个表（或数组）中，然后，直接查表即可，这样就不会超时。

（1）采用数组来做。

        #include <iostream>
        #include <fstream>
        #include <cmath>

       using namespace std;

       int main(int argc, char * argv[])
        {
          ifstream cin("aaa.txt");
            int a[47];
            a[0]=0;

            a[1]=1;
           //先把前46项菲波那契数求出来放在表（或数组）中
            for(int i=2; i<=46; i++)
           {
                a[i]=a[i-1]+a[i-2];
           }
           //查表（数组）
            int n;
            while(cin>>n)
           {
                cout<<a[n]<<endl;
           }
           return 0;
        }

（2）采用向量来做。

        #include <fstream>
        #include <iostream>
        #include <vector>

       using namespace std;

       int main(int argc, char * argv[])
        {
          ifstream cin("aaa.txt");
          vector<unsigned int>v;
          unsigned int n;
          //先建表，把第0~46项的菲波那契数都算出来
          v.push_back(0);
          v.push_back(1);
          for(int i=2; i<=46; i++)
          {
              v.push_back(v[i-1]+v[i-2]);
          }
          //直接输出第n项菲波那契数（从0项开始计算）
          while(cin>>n)
          {
              cout<<v[n]<<endl;
          }
          return 0;
        }