首页 日常,🐶算法

题目

0.png

思路

斐波那契不难,但是数据源达到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;
}



文章评论