Scratch编程学算法解约瑟夫环问题之递推法

欢迎大家来到IT世界,在知识的湖畔探索吧!

Scratch编程学算法解约瑟夫环问题之递推法

约瑟夫问题的来由与算法

一、问题来由

约瑟夫问题（Josephus Problem）起源于古罗马时期的一个历史传说：

公元1世纪，犹太历史学家弗拉维奥·约瑟夫斯（Flavius Josephus）在犹太反抗罗马的战争中，与40名战友被困于洞穴中。为避免被俘受辱，他们约定围成一圈，从第1人开始轮流报数，每数到第3人便将其杀死，最后剩下的人自杀。但约瑟夫斯不想自杀，于是通过数学计算找到最后一个位置，从而幸存下来。

欢迎大家来到IT世界,在知识的湖畔探索吧!

这一传说衍生出经典的数学问题： n个人围成一圈，从第k个人开始报数，每数到第m个的人则将其淘汰出局，直到最后剩下1人，求最后幸存者的位置。

二、归纳递推算法

约瑟夫环问题的递推算法是解决该问题的高效方法，其核心是通过数学归纳法推导出递推公式，避免了模拟法的高时间复杂度。以下从公式推导、含义解析、扩展场景到实例验证，详细讲解递推算法的原理。

模拟算法后面的头条文章介绍。

（一）、递推公式的前提：简化问题定义

为便于推导，先明确简化版问题：

有 n 个人围成一圈，编号为 0, 1, 2, …, n-1（用0开始编号，方便取模运算，如果是从1开始编号，在结果加上1即可）；

从编号 0 的人开始报数，每报数到 m 时，该人被淘汰；剩余的人继续从下一个人开始报数，直到最后剩下1人，求其编号。

递推公式：设 f(n) 表示 n 个人时，最后幸存者的编号，则当n=1时：

f(1) = 0 （只有1人时，幸存者只能是自己），我们用数学归纳法来证明

f(n) = (f(n-1) + m) % n （n ≥ 2）

递推公式的核心思想是：n 个人的问题可以利用归纳假设，转化为 n-1 个人的问题，通过找到两者的关系推导出公式。

1. 初始情况（n=1）：

当只有1个人时，幸存者编号为 0，即 f(1) = 0。

2. n=2时的关系：

2个人编号 0, 1，报数到 m 淘汰。

第一个淘汰的是 (0 + m -1) % 2（减1是因为从0开始报数，报“1”对应0号，报“m”对应第m-1号）。

剩余的那1人即为幸存者，此时可看作 n=1 的情况，这个幸存者在 n=2 时的编号为 (f(1) + m) % 2。

3. 通用归纳（n-1→n）：

假设已知 n-1 个人时的幸存者编号为 f(n-1)，推导 n 个人时的幸存者编号 f(n)：

第一步：n 个人中，第一个被淘汰出局的是 (0 + m-1) % n，记为 k（即 k = (m-1) % n）。

第二步：淘汰 k 后，剩余 n-1 人，从 k+1 开始重新报数（相当于 n-1 个人的问题，只不过起始编号0对应原全局编号的（k+1）%n，依次顺延）。

第三步：n-1 个人的幸存者在其局部编号中是 f(n-1)，对应到 n 个人的全局编号需加上偏移量 k+1，并对 n 取模（避免越界）。

因此：f(n) = (k + 1 + f(n-1)) % n。

代入 k = (m-1) % n，化简得：

f(n) = ((m-1) % n + 1 + f(n-1)) % n = (f(n-1) + m) % n。

以n=8,m=3为例，如下图示意：

黑色0~7为原全局编号，红色0~6为新环的局部编号，f(n-1)对应局部编号和f(n)对应全局编号指向同一位置

（二）公式含义：偏移量的传递

递推公式 f(n) = (f(n-1) + m) % n 的本质是幸存者位置的偏移：

当总人数从 n-1 增加到 n 时，新增的人会导致第一个被淘汰的位置固定为 (m-1) % n，剩余的 n-1 人构成新的环，幸存者在新环中的位置是 f(n-1)，但需要加上淘汰位置带来的偏移量 m（因为下一轮从淘汰位置的下一个人开始报数），最终对 n 取模，确保在合法（不超界即数字不超过n）范围内。

（三）扩展到非0起始编号或非0开始报数的场景

实际问题中，编号可能从 1 开始，或从第 k 个人开始报数，需对公式做调整：

1. 编号从1开始：

只需将结果 f(n) 加1即可（因为 f(n) 是0起始编号，加1转换为1起始）。

例如：n=5, m=3 时，f(5) = 3（0起始），对应1起始编号为 3+1=4。

2. 从第k个人开始报数（k为1起始）：

先将问题转换为“从0起始”的标准问题：

第 k 个人（1起始）对应0起始编号为 k-1，因此初始偏移量为 k-1。

计算标准问题的结果 f(n) 后，最终位置为 (f(n) + k-1) % n + 1（加1转回1起始）。

五、实例验证

以 n=5, m=3（0起始编号）为例，验证公式：

f(1) = 0

f(2) = (f(1) + 3) % 2 = (0 + 3) % 2 = 1

f(3) = (f(2) + 3) % 3 = (1 + 3) % 3 = 1

f(4) = (f(3) + 3) % 4 = (1 + 3) % 4 = 0

f(5) = (f(4) + 3) % 5 = (0 + 3) % 5 = 3

0起始编号的幸存者是3，对应1起始编号为4，与实际模拟结果一致。

约瑟夫问题递推算法的Scratch实现

有了前面的算法分析，得出了递推公式，编程就非常简洁：

（一）标准版：设变量“幸存者”存放f(n),由于f（1）=0，我们可直接赋初值为0，对个数K>1,可以直接根据迭代公式计算即可。循环总数-1次得出f(总数)，再加上1，就是幸存者的（从1开始的）编号。

可见只要约瑟夫选择第31号，就可幸免于难

（二）根据扩展版的算法公式，可以得出Scratch程序代码：

总结

递推公式 f(n) = (f(n-1) + m) % n（初始 f(1)=0）通过归纳法推导，将 n 人问题转化为 n-1 人问题，时间复杂度 O(n)，空间复杂度 O(1)（迭代实现），是解决约瑟夫环问题的最优方法。实际应用中只需根据编号起始方式调整结果即可。