月落乌啼算钱（斐波那契数列）的题解

记住只在没有思路时使用题解，不要从它复制粘贴代码。请尊重题目和题解的作者。
在解题之前提交题解的代码会导致封禁。

作者： admin

概述

本题要求根据题面给出的通项公式求出斐波那契数列的第 $n$ ~n~ 项 $F_n$ ~F_n~，并把结果保留两位小数输出。核心解法是识别出该公式正是斐波那契数列的通项公式，从而把它转化为整数递推 $F_n = F_{n-1} + F_{n-2}$ ~F_n = F_{n-1} + F_{n-2}~，避开无理数幂运算。

分析

核心观察

题面公式中出现 $\sqrt{5}$ ~\sqrt{5}~ 与两个无理数的 $n$ ~n~ 次幂，但它定义的 $F_n$ ~F_n~ 恒为整数，并且恰好就是斐波那契数列： $F_0 = 0$ ~F_0 = 0~， $F_1 = 1$ ~F_1 = 1~， $F_2 = 1$ ~F_2 = 1~， $F_3 = 2$ ~F_3 = 2~……因此只需要做整数加法，全程不出现浮点数。

思路

记

$\displaystyle \alpha = \frac{1+\sqrt{5}}{2}, \qquad \beta = \frac{1-\sqrt{5}}{2}$

题面公式可写成 $F_n = \frac{\alpha^n - \beta^n}{\sqrt{5}}$ 。这两个数是方程 $x^2 = x + 1$ ~x^2 = x + 1~ 的两根，故对任意非负整数 $k$ ~k~ 有

$\displaystyle \alpha^{k+2} = \alpha^{k+1} + \alpha^k, \qquad \beta^{k+2} = \beta^{k+1} + \beta^k$

两式相减后同除以 $\sqrt{5}$ ~\sqrt{5}~，左端即 $F_{k+2}$ ~F_{k+2}~，右端即 $F_{k+1} + F_k$ ~F_{k+1} + F_k~，于是得到递推关系

$\displaystyle F_{k+2} = F_{k+1} + F_k$

初值直接由公式代入得到： $F_0 = \frac{1-1}{\sqrt{5}} = 0$ ~F_0 = \frac{1-1}{\sqrt{5}} = 0~，而 $F_1 = \frac{\alpha - \beta}{\sqrt{5}} = \frac{\sqrt{5}}{\sqrt{5}} = 1$ 。

这说明公式定义的数列与斐波那契数列 $0, 1, 1, 2, 3, 5, 8, \ldots$ ~0, 1, 1, 2, 3, 5, 8, \ldots~ 完全相同，两项初值加一条递推即可把它完全确定。

数据范围只有 $0 \le n \le 48$ ~0 \le n \le 48~，用两个变量滚动保存相邻两项、循环 $n$ ~n~ 次做加法即可，时间与空间都是常数级别。若按原公式分别计算两个幂再相减，则需要处理 $\sqrt{5}$ ~\sqrt{5}~ 与无理数幂，引入不必要的浮点误差；整数递推的结果是精确的，不存在这个环节。先递推求出前 $49$ ~49~ 项打表也是一种可行做法，但直接滚动递推的代码更短，且不需要额外存储。

具体示例

以 $n = 6$ ~n = 6~ 为例，按递推逐项计算：

$\displaystyle F_2 = 1 + 0 = 1,\quad F_3 = 1 + 1 = 2,\quad F_4 = 2 + 1 = 3,\quad F_5 = 3 + 2 = 5,\quad F_6 = 5 + 3 = 8$

输出为 $8.00$ ~8.00~，与数据一致。再看两端： $n = 0$ ~n = 0~ 时答案为 $0.00$ ~0.00~， $n = 1$ ~n = 1~ 时答案为 $1.00$ ~1.00~，可见两项初值都必须作为输出备选； $n$ ~n~ 取最大值 $48$ ~48~ 时答案为 $4807526976.00$ ~4807526976.00~，该值已经超过 $32$ ~32~ 位有符号整数的上限 $2147483647$ ~2147483647~。

算法步骤

读入整数 n。
令 a 表示当前项，初值为 $F_0 = 0$ ~F_0 = 0~；令 b 表示下一项，初值为 $F_1 = 1$ ~F_1 = 1~。
重复 n 次：先用临时变量 t 保存 a + b，再令 a = b、b = t，使两项同时向后滑动一格。
循环结束时 a 即为 $F_n$ ~F_n~，按保留两位小数的格式输出 a。

复杂度分析

时间： $O(n)$ ~O(n)~。递推共执行 $n$ ~n~ 次整数加法，每次为常数时间。
空间： $O(1)$ ~O(1)~。只需 $3$ ~3~ 个变量保存相邻两项与临时值。

实现注意事项

$n$ ~n~ 可以取 $0$ ~0~，此时循环体一次也不执行，直接输出初值 $F_0 = 0$ ~F_0 = 0~，结果为 $0.00$ ~0.00~。初值必须取 $F_0$ ~F_0~ 与 $F_1$ ~F_1~；若从 $F_1$ ~F_1~ 与 $F_2$ ~F_2~ 起步，会在 $n = 0$ ~n = 0~、 $n = 1$ ~n = 1~ 处出错。
$F_{47} = 2971215073$ ~F_{47} = 2971215073~ 与 $F_{48} = 4807526976$ ~F_{48} = 4807526976~ 都超过 $32$ ~32~ 位有符号整数上限 $2147483647$ ~2147483647~，保存数列项的变量必须使用 $64$ ~64~ 位整数类型，C++ 中对应 long long，Python 的整数本身没有位数限制。
答案恒为整数，但输出要求两位小数。C++ 需要开启定点输出并把精度设为 $2$ ~2~，且输出前要转换为浮点类型，否则整数会按原样打印、没有小数部分；Python 用格式化字符串即可。
$F_{48}$ ~F_{48}~ 远小于 $2^{53}$ ~2^{53}~，把该整数交给两位小数的格式化输出不会产生精度损失，不需要手工拼接小数部分。
输入只有一行一个自然数，直接读入即可，不需要处理多余空白。
不要按原公式直接计算两个幂再相减：整数递推完全精确，而浮点幂运算会引入误差。

源代码

#include <iostream>
#include <iomanip>
using namespace std;

int main() {
    int n;
    cin >> n;

    long long a = 0, b = 1;  // a = F(0), b = F(1)
    for (int i = 0; i < n; ++i) {
        long long t = a + b;
        a = b;
        b = t;
    }

    cout << fixed << setprecision(2) << (double)a << endl;
    return 0;
}

n = int(input())

a, b = 0, 1  # a = F(0), b = F(1)
for _ in range(n):
    a, b = b, a + b

print(f"{a:.2f}")

目前没有评论。