題目描述：

大家都知道斐波那契數(shù)列，現(xiàn)在要求輸入一個(gè)整數(shù)n，請(qǐng)你輸出斐波那契數(shù)列的第n項(xiàng)。斐波那契數(shù)列的定義如下：

?

輸入：

輸入可能包含多個(gè)測(cè)試樣例，對(duì)于每個(gè)測(cè)試案例，

輸入包括一個(gè)整數(shù)n(1<=n<=70)。

?

輸出：

對(duì)應(yīng)每個(gè)測(cè)試案例，

輸出第n項(xiàng)斐波那契數(shù)列的值。

?

樣例輸入：

        3
      

樣例輸出：

        2
        

        

        
          
            
              看題目要求，需要輸出到70的斐波那契數(shù)列，如果用常規(guī)的遞歸，顯然層次過(guò)多，而且大部分是多余的。所以用一個(gè)數(shù)組來(lái)保持已經(jīng)算出的斐波那契數(shù)列值，需要時(shí)直接從數(shù)組返回，大大節(jié)省時(shí)間。注意數(shù)組要用long long。
            
            

            

          
        
      

          #include <iostream>
          
            

#include 
          
          <fstream>
          
            

#include 
          
          <vector>
          
            

#include 
          
          <
          
            string
          
          >
          
            

#include 
          
          <algorithm>
          
            

#include 
          
          <map>
          
            

#include 
          
          <stack>
          
            

#include 
          
          <cmath>
          
            

#include 
          
          <queue>
          
            

#include 
          
          <
          
            set
          
          >
          
            

#include 
          
          <list>
          
            

#include 
          
          <cctype>
          
            

#include 
          
          <stdio.h>
          
            

#include 
          
          <stdlib.h>
          
            

#include 
          
          <
          
            string
          
          .h>


          
            #define
          
           REP(i,j,k) for(int i = j ; i < k ; ++i)


          
            #define
          
           MAXV (1000)


          
            #define
          
           INF (0x6FFFFFFF)


          
            using
          
          
            namespace
          
          
             std;


          
          
            long
          
          
            long
          
           ans[
          
            80
          
          
            ];


          
          
            long
          
          
            long
          
           fac(
          
            int
          
          
             x)

{

    
          
          
            if
          
          (x==
          
            0
          
          
            )

        
          
          
            return
          
          
            0
          
          
            ;

    
          
          
            if
          
          (x==
          
            1
          
          
            )

        
          
          
            return
          
          
            1
          
          
            ;

    
          
          
            if
          
          (ans[x]!=
          
            0
          
          
            )

        
          
          
            return
          
          
             ans[x];

    
          
          
            if
          
          (ans[x]==
          
            0
          
          
            )

    {

        ans[x]
          
          =fac(x-
          
            1
          
          )+fac(x-
          
            2
          
          
            );

        
          
          
            return
          
          
             ans[x];

    }

}


          
          
            int
          
          
             main()

{

    
          
          
            //
          
          
            freopen("in.txt","r",stdin);
          
          

    memset(ans,
          
            0
          
          ,
          
            sizeof
          
          (
          
            long long
          
          
            ));

    
          
          
            int
          
          
             n;

    ans[
          
          
            1
          
          ]=
          
            1
          
          
            ;

    fac(
          
          
            71
          
          
            );

    
          
          
            while
          
          (~scanf(
          
            "
          
          
            %d
          
          
            "
          
          ,&
          
            n))

        printf(
          
          
            "
          
          
            %lld\n
          
          
            "
          
          
            ,ans[n]);

    
          
          
            return
          
          
            0
          
          
            ;

}
          
        

      

        ?
      
      
        
          
            ?
          
        
      
    

題目1387：斐波那契數(shù)列