“兔子数列“通关手册：从递归到动态规划（C语言+LeetCode/蓝桥杯真题详解）

斐波那契数列详解（C语言版）

一、从兔子问题到斐波那契数列

1.1 生活化引入：兔子繁殖的数学奥秘

假设一对刚出生的兔子（一公一母），从第3个月开始每月生一对小兔子，且所有兔子都不会死亡。那么第1个月有1对兔子，第2个月有1对，第3个月有2对（老兔+新兔），第4个月有3对（老兔+第3月新兔+第4月新兔）……如此下去，每月的兔子对数构成一个数列：1, 1, 2, 3, 5, 8, 13, 21…

这个数列就是著名的斐波那契数列（Fibonacci sequence），它的规律是：从第3项开始，每一项都等于前两项之和。

1.2 数学定义与公式

斐波那契数列的严格定义为：

• 当 ( n = 0 ) 时，( F(0) = 0 )（部分定义从0开始，需注意题目要求）
• 当 ( n = 1 ) 时，( F(1) = 1 )
• 当 ( n >=2 ) 时，( F(n) = F(n-1) + F(n-2) )
  

注意：不同场景下数列的起始项可能不同（如部分定义从 ( F(1)=1, F(2)=1 )开始）！解题时需先确认题目中的“第n项"对应哪个定义（蓝桥杯/LeetCode题目通常会明确说明起始条件）。

二、斐波那契数列的C语言实现方法

2.1 方法1：递归实现（直观但低效）

思路

直接按数学定义编写递归函数：若 ( n \leq 1 ) 则返回n，否则返回 ( F(n-1) + F(n-2) )。

代码实现

#include <stdio.h>

// 递归计算斐波那契数列第n项
long long fib_recursion(int n) {
    if (n <= 1) {  // 终止条件：F(0)=0, F(1)=1
        return n;
    } else {
        return fib_recursion(n-1) + fib_recursion(n-2);  // 递归调用
    }
}

int main() {
    int n = 10;
    printf("F(%d) = %lld\n", n, fib_recursion(n));  // 输出：F(10) = 55
    return 0;
}

缺陷：指数级时间复杂度！！！

递归实现虽然简洁，但存在严重的重复计算问题。例如计算 ( F(5) ) 时，( F(3) ) 被计算2次，( F(2) ) 被计算3次……当 ( n=40 )时，调用次数超过 ( F(40) \approx 10^8 )，程序会明显卡顿；( n=50 )时，可能需要几分钟才能出结果！

时间复杂度：( O(2^n) )（指数级，效率极低）
空间复杂度：( O(n) )（递归栈深度为n）

表：递归计算F(5)的调用树（重复计算一目了然）

2.2 方法2：迭代实现（高效首选）

思路

用循环代替递归，从第2项开始自底向上计算，用两个变量存储前两项的值，避免重复计算。

代码实现

#include <stdio.h>

// 迭代计算斐波那契数列第n项（无优化版）
long long fib_iteration(int n) {
    if (n <= 1) {
        return n;
    }
    long long a = 0;  // F(0)
    long long b = 1;  // F(1)
    long long result = 0;
    for (int i = 2; i <= n; i++) {
        result = a + b;  // F(i) = F(i-2) + F(i-1)
        a = b;           // 更新F(i-2)为F(i-1)
        b = result;      // 更新F(i-1)为F(i)
    }
    return result;
}

int main() {
    int n = 50;
    printf("F(%d) = %lld\n", n, fib_iteration(n));  // 输出：F(50) = 12586269025
    return 0;
}

优势：线性时间复杂度！

迭代法只需遍历一次，每个项仅计算1次。当 ( n=10^6 )时，也能在毫秒级内出结果。

时间复杂度：( O(n) )（线性级，效率极高）
空间复杂度：( O(1) )（仅用3个变量，常数级空间）

2.3 方法3：记忆化搜索（递归+缓存优化）

思路

用数组存储已计算的项（类似“备忘录”），避免递归中的重复计算。

代码实现

#include <stdio.h>
#include <string.h>

#define MAX_N 1000  // 最大计算项数
long long memo[MAX_N];  // 缓存数组，存储已计算的F(n)

// 记忆化搜索计算斐波那契数列第n项
long long fib_memoization(int n) {
    if (n <= 1) {
        return n;
    }
    // 若已计算过，直接返回缓存值（避免重复计算）
    if (memo[n] != -1) {
        return memo[n];
    }
    // 未计算过，递归计算并缓存结果
    memo[n] = fib_memoization(n-1) + fib_memoization(n-2);
    return memo[n];
}

int main() {
    int n = 50;
    memset(memo, -1, sizeof(memo));  // 初始化缓存为-1（表示未计算）
    printf("F(%d) = %lld\n", n, fib_memoization(n));  // 输出：F(50) = 12586269025
    return 0;
}

优势：兼顾递归的简洁与迭代的效率

记忆化搜索本质是“递归+缓存”，每个项仅计算1次，时间复杂度与迭代法相同，但代码更接近数学定义。

时间复杂度：( O(n) )
空间复杂度：( O(n) )（缓存数组+递归栈）

二、经典案例实战

2.1 蓝桥杯真题：斐波那契数列的取模问题

题目描述（蓝桥杯基础练习）

给定 ( n )，计算斐波那契数列第 ( n ) 项对 ( 10^9 + 7 ) 取模的结果（( n \leq 10^6 )）。

关键考点：防止数据溢出！

斐波那契数列增长极快：( F(40) \approx 10^8 )，( F(80) \approx 10^{16} )，超过32位整数（最大值约 ( 2 \times 10^9 )）的范围。即使使用 long long（64位，最大值约 ( 9 \times 10^{18} )），当 ( n=90 )时也会溢出！

解决方案：每步计算后对 ( 10^9 + 7 ) 取模（模运算性质：( (a + b) \mod m = [(a \mod m) + (b \mod m)] \mod m )）。

C语言代码实现

#include <stdio.h>
#define MOD 1000000007  // 1e9+7，蓝桥杯常用取模值

long long fib_mod(int n) {
    if (n <= 1) return n;
    long long a = 0, b = 1, result;
    for (int i = 2; i <= n; i++) {
        result = (a + b) % MOD;  // 每步取模，防止溢出
        a = b;
        b = result;
    }
    return result;
}

int main() {
    int n = 1000000;  // n=1e6，迭代法轻松处理
    printf("F(%d) mod 1e9+7 = %lld\n", n, fib_mod(n));
    return 0;
}

2.2 LeetCode 509：斐波那契数（简单必刷）

题目链接

LeetCode 509. Fibonacci Number

题目描述

给定 ( n )，计算 ( F(n) )（定义：( F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) )）。

解题思路

直接用迭代法或记忆化搜索，此处展示迭代法（效率最高）。

C语言代码

int fib(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

执行效率

• 时间复杂度：( O(n) )，击败100% C语言用户
• 空间复杂度：( O(1) )

2.3 LeetCode 70：爬楼梯（斐波那契数列的经典应用）

题目链接

LeetCode 70. Climbing Stairs

题目描述

你正在爬楼梯，需要 ( n ) 阶才能到达楼顶。每次可以爬1或2个台阶，有多少种不同的方法爬到楼顶？

思路：转化为斐波那契数列！

• 设 ( f(n) ) 为爬到第n阶的方法数。
• 最后一步只能是1阶或2阶，因此：( f(n) = f(n-1) + f(n-2) )（前n-1阶的方法数 + 前n-2阶的方法数）。
• 初始条件：( f(1)=1 )（1阶：1种方法），( f(2)=2 )（2阶：1+1或2，共2种）。

发现规律：( f(n) = F(n+1) )，其中 ( F(n) ) 是斐波那契数列第n项（如 ( f(3)=3=F(4), f(4)=5=F(5) )）。

C语言代码

int climbStairs(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    int a = 1, b = 2, c;  // a=f(n-2), b=f(n-1)
    for (int i = 3; i <= n; i++) {
        c = a + b;  // f(i) = f(i-1) + f(i-2)
        a = b;
        b = c;
    }
    return b;
}

执行效率

• 时间复杂度：( O(n) )
• 空间复杂度：( O(1) )

三、斐波那契数列的“隐藏彩蛋”

3.1 黄金比例关系

当 ( n ) 足够大时，斐波那契数列相邻两项的比值 ( \frac{F(n+1)}{F(n)} ) 无限接近黄金比例 ( \phi = \frac{1+\sqrt{5}}{2} \approx 1.618 )。例如：

• ( F(10)=55, F(11)=89 ) → ( 89/55 \approx 1.618 )
• ( F(20)=6765, F(21)=10946 ) → ( 10946/6765 \approx 1.618 )

3.2 模运算的周期性（蓝桥杯高频考点）

对斐波那契数列取模后，结果会呈现周期性（称为“皮萨诺周期”）。例如对 ( \text{mod}=10 ) 时，周期为60（即每60项后取模结果重复）。利用这一性质，可快速计算 ( n ) 很大时的 ( F(n) \mod m )（如 ( n=10^{18} ) 时，直接用周期简化计算）。

表：不同实现方法的对比（选方法不再纠结！）

四、总结与学习建议

斐波那契数列是理解递归、动态规划、迭代优化的绝佳案例，其核心思想“用已知推未知”贯穿算法设计始终。掌握它的实现与应用，能为后续学习复杂算法（如动态规划、矩阵快速幂）打下基础。

推荐练习题目

1. 蓝桥杯基础练习：《斐波那契数列》（强化取模与迭代实现）
2. LeetCode 1137：第 N 个泰波那契数（斐波那契数列的扩展）
3. 蓝桥杯真题：《兔子繁殖问题》（变种场景应用）

扩展学习（选学）

• 矩阵快速幂：将时间复杂度优化至 ( O(\log n) )，可处理 ( n=10^{18} ) 的超大规模问题
• 通项公式法：用黄金比例公式直接计算 ( F(n) )，但受限于浮点数精度，实际应用较少

注：本文案例参考 LeetCode 509、70 题及蓝桥杯往届真题，代码均通过实际编译测试。