本文最后更新于 619 天前，其中的信息可能已经有所发展或是发生改变。

题目描述

输入一个正整数n，求Fibonacci数列的第n个数。Fibonacci数列的特点：第1,2个数为1,1。从第3个数开始，概述是前面两个数之和。即：

要求输入的正整数n不超过50.

输入

一个不超过50的正整数

输出

Fibonacci数列的第n个数，末尾输出换行。递归法(使用数组记录已经算过的斐波那契数)

#include<bits/stdc++.h>
using namespace std;
uint64_t Fibonacci(unsigned char n)
{static uint64_t fib[256] = { 0, 1 };if (n == 0) return 0;if (fib[n] != 0) return fib[n];fib[n] = Fibonacci(n - 1) + Fibonacci(n - 2);return fib[n];
}
int main() {int n;cin >> n;cout << Fibonacci(n);
}

递推法

#include<bits/stdc++.h>
using namespace std;
int main()
{long long sum = 1, pre_sum = 0, cre_sum;int i;scanf("%d", &i);while (--i){cre_sum = sum;sum += pre_sum;pre_sum = cre_sum;}printf("%lld\n", sum);return 0;
}