题目
思路
斐波那契不难,但是数据源达到2000000000,无论用什么都会超出范围。
但是通过观察发现第20个数之后的比例都为0.61803399。
所以只要把前20个求出来,后面的直接输出为0.61803399就行。
#include <iostream>
#include <vector>
#include <math.h>
#define int long long
using namespace std;
signed main()
{
vector<double> arr = vector<double>(2000, 0);
arr[1] = 1;
arr[2] = 1;
int n;
cin>>n;
if (n < 20 && n >= 1) {
for (double i = 3; i <= n + 1; i++) {
arr[i] = arr[i - 1] + arr[i - 2];
}
double res = arr[n] / arr[n + 1];
printf("%.8f", res);
}
else {
cout<<"0.61803399";
}
return 0;
}