❝

约瑟夫环（约瑟夫问题）的起源可以追溯到公元1世纪，当时有一个名叫约瑟夫的犹太历史学家。据传，他和他的同伴被敌人包围，在面临绝境时，他们决定宁死不屈，于是决定通过自杀的方式结束生命。为了执行这个决定，他们围成一个圈，然后按照一定的规则来选择自杀的人，直到只剩下最后一个人。约瑟夫，作为一个不愿意自杀的人，快速地计算出了一个位置，使得他成为了最后一个存活的人，从而有机会逃脱。

数学模型

将这个故事抽象成数学模型，我们得到了约瑟夫环问题：假设有n个人围成一圈，从某个人开始，按顺时针方向逐一编号。接着从编号为1的人开始报数，每数到m就将该人从圈中排除，然后从下一个人重新开始报数，直到圈中只剩下一个人。

比如说，如果有6个人(n = 6)参与游戏（编号为1到6），选择的m是3，那么游戏进行的过程大概是这样的：

1. 从编号1的人开始报数，数到3的人是编号3的人，所以编号3的人离开游戏。
2. 接下来，从编号4的人开始报数，数到3的人是编号6的人，因此编号6的人离开游戏。
3. 现在，从编号1的人开始报数，数到3的人是编号2的人，所以编号2的人离开游戏。
4. 然后，从编号4的人开始报数，数到3的人是编号5的人，因此编号5的人离开游戏。
5. 最后，剩下编号1和编号4的人，从编号1的人开始报数，数到3的人是编号4的人，所以编号4的人离开游戏。
6. 最终，只剩下编号1的人，他就是游戏的赢家。

我们用伪代码解答：

 f( n,  m){
    return n == 1 ? n : (f(n - 1, m) + m - 1) % n + 1;
}

逻辑

这个函数f接收两个参数：

• n：圈中的人数。
• m：报数的数字，每报到这个数字的人就要退出游戏。
• 函数 f 返回的是最后存活的人的编号，这个编号是基于初始时圈中人的排列顺序。假设有 n 个人围成一个圈，按顺序编号从 1 到 n，并且按照规则每数到第 m 个人就将其从圈中移除，那么 f(n, m) 就会返回在这个过程结束时，即圈中只剩下一个人时，那个人的原始编号。
• 例如，如果有 5 个人 (n = 5) 围成一圈，选择的 m 是 3，那么 f(5, 3) 将计算并返回在这些人按照规则开始报数，每报到 3 时就有一个人离开圈子，直到最后只剩下一个人时，那个人的编号。

这个函数的计算方法确保了不管 n 和 m 的值如何，它都能准确计算出在这种特定报数规则下最后一个剩余的人的编号。

这是利用递归思想解决问题，让我们逐步分解这个函数：

1. 基本情况：如果n == 1，这意味着圈中只剩下一个人，那么这个人就是赢家，函数返回这个人的编号，即1。这是递归的基本结束条件。

2. 递归步骤：如果n > 1，则需要进行递归调用来缩小问题的规模。

• f(n - 1, m) + m - 1：首先，将上一轮的赢家编号（在减少一个人之后的情况）加上m - 1，因为我们从下一个人开始重新计数，直到数到m。
• % n：然后，对当前人数n取模，这样可以确保如果数字超过了人数n，它会从头开始计算。
• + 1：最后，加1是因为我们的编号是从1开始的，而非0开始。这样就能正确映射到从1开始的编号。
• f(n - 1, m)：首先，函数递归调用自身，人数减少一个（因为每一轮游戏都会有一个人被淘汰），直到只剩一个人，递归才会结束。
• (f(n - 1, m) + m - 1) % n + 1：这部分是计算经过一轮淘汰后，剩余人员重新编号后的赢家编号。其中：

接下来我们看看具体是怎么做的：

举例

1. 开始点：f(5, 3)

• 需要计算 f(4, 3), 并将其结果加上 3 - 1, 然后对 5 取模，最后加 1。

2. 计算 f(4, 3)

• 类似地，f(4, 3) 需要计算 f(3, 3), 并将其结果加上 3 - 1, 对 4 取模，再加 1。

3. 计算 f(3, 3)

• f(3, 3) 需要计算 f(2, 3), 并将其结果加上 3 - 1, 对 3 取模，再加 1。

4. 计算 f(2, 3)

• f(2, 3) 需要计算 f(1, 3), 并将其结果加上 3 - 1, 对 2 取模，再加 1。

5. 计算 f(1, 3)

• 当 n = 1, f(1, 3) 返回 1，因为只剩一个人时，那个人就是赢家。

让我们反着来看思考过程，这会更容易一点：

回溯过程

• f(1, 3) = 1
• f(2, 3)：将 f(1, 3) 的结果 1 加上 2（即 3 - 1），得到 3，然后对 2 取模得到 1，再加 1 得到 2。（这里说f(2, 3) = 2 ，也就是编号为2的人活了下来，下文同理。）
• f(3, 3)：将 f(2, 3) 的结果 2 加上 2（即 3 - 1），得到 4，然后对 3 取模得到 1，再加 1 得到 2。
• f(4, 3）：将 f(3, 3) 的结果 2 加上 2（即 3 - 1），得到 4，然后对 4 取模得到 0，再加 1 得到 1。
• f(5, 3)：将 f(4, 3) 的结果 1 加上 2（即 3 - 1），得到 3，然后对 5 取模得到 3，再加 1 得到 4。

结果

因此，f(5, 3) 的最终结果是 4，意味着在有 5 个人围成一圈，按照每数到 3 就让一个人离开的规则下，最后剩下的是最初编号为 4 的那个人。

何以递归？

约瑟夫环问题如何能成为递归算法的经典案例？结合计算思维，我们进一步探讨。

自相似性

递归算法的核心思想是将问题分解成更小的子问题，直到这些子问题足够小，可以直接解决。约瑟夫环问题本质上具有自相似的结构：每当一个人被淘汰，剩下的人又形成了一个较小的圈，规则不变，这就构成了一个更小规模的约瑟夫环问题。这种自相似性质使得约瑟夫环问题非常适合用递归方法来解决。

分而治之

递归算法是分而治之策略的一种体现。在约瑟夫环问题中，通过递归调用，我们不断缩小问题的规模（即每次减少一个人），直到达到一个基本情况（只剩下一个人）。这种方法能够将一个复杂问题简化为易于管理和解决的小问题，是计算思维中分解问题的典型例证。

刘谦魔术的把戏

在刘谦的魔术中，约瑟夫问题的核心思想被巧妙地应用于控制过程的结果。约瑟夫问题是通过固定间隔来选择和排除序列中的对象，直到只剩一个对象。在这个魔术中，尽管没有直接使用固定间隔的排除方法，但通过一系列精心设计的操作步骤（如牌的折叠、插入、丢弃等），实现了类似的控制效果，即无论参与者如何执行这些步骤，都会以一种预定的方式减少牌的数量，最终留下一张特定的牌。

让我们试着逐步分析：

1. 初始状态是四张不同的牌，标记为A、B、C、D。
2. 撕开后变成两副牌，顺序为ABCDABCD。这意味着每张牌都有一个另一半，形成了两套完全相同的序列。
3. 接着，规则允许任意数量的牌从前面移动到后面，新的排序用abcdabcd表示，这是说序列可能被重新排列，但仍然是两个重复的四牌序列。
4. 然后，最前面的三张牌被插入到后面某个位置，导致序列中的两个d分开，但因为只有这三张牌移动了位置，所以这两个d之间的其他牌仍然保持原有的相对顺序。
5. 移除序列中的第一张牌（d），这不会影响剩余牌的相对顺序。
6. 接下来，将剩下的1、2或3张牌插入到后面的牌中，这可能会改变某些牌的相对顺序，但因为操作是有限的，所以这种影响是可控的。
7. 丢弃最上面的一张或两张牌，这减少牌的数量，但保留了牌的相对位置。
8. 按顺序将7张牌移动到最后，这个步骤确保了在完成这些移动后，原来的第一张d牌（已经被移除）的另一半现在在倒数第二的位置。（请读者证明）
9. 最后，通过交替地放置一张牌到最后和丢弃一张牌，最终剩下一张牌，这张牌是d的另一半。（约瑟夫环的简化版本）