蓝桥杯竞赛：Fibonacci数列与黄金比例

问题描述

Fibonacci数列是一个经典的数学序列，定义如下：F(1) = 1, F(2) = 1，对于i > 2，F(i) = F(i-1) + F(i-2)。Fibonacci数列有一个有趣的性质，即前一项与后一项的比值F(i) / F(i+1)会逐渐趋近于黄金比例（约为1.6180339887）。为了验证这一性质，给定一个正整数N (1 ≤ N ≤ 2000000000)，计算F(N) / F(N+1)，并保留8位小数。

输入格式

输入一个正整数N。

输出格式

输出F(N) / F(N+1)，保留8位小数。

样例输入

2

样例输出

0.50000000

源代码

#include 
int dp[1000];

// 递归求斐波那契数
int Fibonacci_recursive(int N) {
    if (N == 1 || N == 2) return 1;
    else return Fibonacci_recursive(N - 1) + Fibonacci_recursive(N - 2);
}

// 动态规划求斐波那契数
int Fibonacci_dp(int N) {
    dp[1] = dp[2] = 1;
    for (int i = 3; i <= N; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[N];
}

void calculate_golden_ratio() {
    int N;
    double ratio;
    printf("Fibonacci数列与黄金比例\n");
    printf("请输入正整数N: ");
    scanf("%d", &N);

    int fib_N, fib_N_plus_1;
    if (N >= 20) {
        fib_N = Fibonacci_dp(20);
        fib_N_plus_1 = Fibonacci_dp(21);
    } else {
        fib_N = Fibonacci_dp(N);
        fib_N_plus_1 = Fibonacci_dp(N + 1);
    }

    ratio = (double)fib_N / fib_N_plus_1;
    printf("黄金比例的结果为: %.8lf\n", ratio);
}

int main() {
    calculate_golden_ratio();
    return 0;
}

运行结果

解题思路

当N非常大时，直接计算Fibonacci数会导致数据溢出。因此，可以通过预先计算并存储较小范围内的Fibonacci数，然后利用这些预计算的值来解决大N的情况。通过实验发现，当N ≥ 20时，保留8位小数的结果基本一致，因此可以直接使用N = 20时的结果来处理更大的N值。