递归算法实战：五人分鱼问题的数学建模与实现

1. 问题背景与递归思想引入

五个人夜间捕鱼后疲倦睡去。第一个人醒来后将鱼分成五份，发现多一条，于是扔掉多余的一条，拿走自己的一份。接着第二、第三、第四、第五个人依次同样操作。问他们至少捕了多少条鱼？

这个看似简单的数学谜题，实际上考察的是递归思想和模运算的应用。我第一次遇到这个问题是在大学算法课上，当时用穷举法花了半小时才解出来。后来掌握递归技巧后，发现只需10行代码就能优雅解决。

递归的核心在于将大问题分解为相似的小问题。在分鱼问题中，每个人的操作都是"分五份余一，取一份"，这种重复性正是递归的用武之地。我们不妨从最后一个人倒推，建立递推关系式。

2. 数学建模与递推公式

设第i个人操作前的鱼数为f(i)，操作后为f(i+1)。根据题意：

1. 分五份：f(i) / 5
2. 余一条：(f(i) - 1) % 5 == 0
3. 取一份：f(i+1) = f(i) - 1 - (f(i) - 1)/5

化简得到递推关系：
f(i) = (f(i+1) * 5 / 4) + 1

关键约束条件：

• 每次分配必须整除：(f(i) - 1) % 5 == 0
• 鱼数始终为正整数

这个递推关系揭示了问题的数学本质：我们需要找到一个最小的初始值f(0)，使得经过5次逆向计算后，所有中间值都是整数。

3. 递归算法实现

3.1 基础递归解法

c复制#include <stdio.h>

int fish(int n, int person) {
    if (person == 0) return n;
    if ((n - 1) % 5 != 0) return -1;
    return fish((n - 1) * 4 / 5, person - 1);
}

int main() {
    int n = 1;
    while (1) {
        if (fish(n, 5) != -1) {
            printf("至少捕了%d条鱼\n", n);
            break;
        }
        n++;
    }
    return 0;
}

这个实现从n=1开始向上穷举，对每个n用递归验证是否满足5次分配条件。虽然直观，但效率较