题目描述
输入一个正整数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;
}