- 题目描述：
-
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。斐波那契数列的定义如下：
- 输入：
-
输入可能包含多个测试样例，对于每个测试案例，
输入包括一个整数n(1<=n<=70)。
- 输出：
-
对应每个测试案例，
输出第n项斐波那契数列的值。
- 样例输入：
-
3
- 样例输出：
-
2
看题目要求，需要输出到70的斐波那契数列，如果用常规的递归，显然层次过多，而且大部分是多余的。所以用一个数组来保持已经算出的斐波那契数列值，需要时直接从数组返回，大大节省时间。注意数组要用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 ; }
