防走失，电梯直达
安全岛
报人刘亚
东A
来源： 进步的阶梯eacc
作者： 辰子进步的阶梯
❝
约瑟夫环（约瑟夫问题）的起源可以追溯到公元1世纪，当时有一个名叫约瑟夫的犹太历史学家。据传，他和他的同伴被敌人包围，在面临绝境时，他们决定宁死不屈，于是决定通过自杀的方式结束生命。为了执行这个决定，他们围成一个圈，然后按照一定的规则来选择自杀的人，直到只剩下最后一个人。约瑟夫，作为一个不愿意自杀的人，快速地计算出了一个位置，使得他成为了最后一个存活的人，从而有机会逃脱。
数学模型
将这个故事抽象成数学模型，我们得到了约瑟夫环问题：假设有n个人围成一圈，从某个人开始，按顺时针方向逐一编号。接着从编号为1的人开始报数，每数到m就将该人从圈中排除，然后从下一个人重新开始报数，直到圈中只剩下一个人。
比如说，如果有6个人(n = 6)参与游戏（编号为1到6），选择的m是3，那么游戏进行的过程大概是这样的：
-
从编号1的人开始报数，数到3的人是编号3的人，所以编号3的人离开游戏。
-
接下来，从编号4的人开始报数，数到3的人是编号6的人，因此编号6的人离开游戏。
-
现在，从编号1的人开始报数，数到3的人是编号2的人，所以编号2的人离开游戏。
-
然后，从编号4的人开始报数，数到3的人是编号5的人，因此编号5的人离开游戏。
-
最后，剩下编号1和编号4的人，从编号1的人开始报数，数到3的人是编号4的人，所以编号4的人离开游戏。
-
最终，只剩下编号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
的值如何，它都能准确计算出在这种特定报数规则下最后一个剩余的人的编号。
这是利用 递归思想 解决问题，让我们逐步分解这个函数：
-
基本情况 ：如果
n == 1，这意味着圈中只剩下一个人，那么这个人就是赢家，函数返回这个人的编号，即1。这是递归的基本结束条件。 -
递归步骤 ：如果
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
：这部分是计算经过一轮淘汰后，剩余人员重新编号后的赢家编号。其中：
接下来我们看看具体是怎么做的：
举例
-
开始点 ：
f(5, 3)
需要计算
f(4, 3)
, 并将其结果加上
3 - 1
, 然后对
5
取模，最后加
1
。
计算
f(4, 3)
类似地，
f(4, 3)
需要计算
f(3, 3)
, 并将其结果加上
3 - 1
, 对
4
取模，再加
1
。
计算
f(3, 3)
f(3, 3)
需要计算
f(2, 3)
, 并将其结果加上
3 - 1
, 对
3
取模，再加
1
。
计算
f(2, 3)
f(2, 3)
需要计算
f(1, 3)
, 并将其结果加上
3 - 1
, 对
2
取模，再加
1
。
计算
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
的那个人。
何以递归？
约瑟夫环问题如何能成为递归算法的经典案例？结合计算思维，我们进一步探讨。
自相似性
递归算法的核心思想是将问题分解成更小的子问题，直到这些子问题足够小，可以直接解决。约瑟夫环问题本质上具有自相似的结构：每当一个人被淘汰，剩下的人又形成了一个较小的圈，规则不变，这就构成了一个更小规模的约瑟夫环问题。这种自相似性质使得约瑟夫环问题非常适合用递归方法来解决。
分而治之
递归算法是分而治之策略的一种体现。在约瑟夫环问题中，通过递归调用，我们不断缩小问题的规模（即每次减少一个人），直到达到一个基本情况（只剩下一个人）。这种方法能够将一个复杂问题简化为易于管理和解决的小问题，是计算思维中分解问题的典型例证。
刘谦魔术的把戏
在刘谦的魔术中，约瑟夫问题的核心思想被巧妙地应用于控制过程的结果。约瑟夫问题是通过固定间隔来选择和排除序列中的对象，直到只剩一个对象。在这个魔术中，尽管没有直接使用固定间隔的排除方法，但通过一系列精心设计的操作步骤（如牌的折叠、插入、丢弃等），实现了类似的控制效果，即无论参与者如何执行这些步骤，都会以一种预定的方式减少牌的数量，最终留下一张特定的牌。
让我们试着逐步分析：
-
初始状态是四张不同的牌，标记为A、B、C、D。
-
撕开后变成两副牌，顺序为ABCDABCD。这意味着每张牌都有一个另一半，形成了两套完全相同的序列。
-
接着，规则允许任意数量的牌从前面移动到后面，新的排序用abcdabcd表示，这是说序列可能被重新排列，但仍然是两个重复的四牌序列。
-
然后，最前面的三张牌被插入到后面某个位置，导致序列中的两个d分开，但因为只有这三张牌移动了位置，所以这两个d之间的其他牌仍然保持原有的相对顺序。
-
移除序列中的第一张牌（d），这不会影响剩余牌的相对顺序。
-
接下来，将剩下的1、2或3张牌插入到后面的牌中，这可能会改变某些牌的相对顺序，但因为操作是有限的，所以这种影响是可控的。
-
丢弃最上面的一张或两张牌，这减少牌的数量，但保留了牌的相对位置。
-
按顺序将7张牌移动到最后，这个步骤确保了在完成这些移动后，原来的第一张d牌（已经被移除）的另一半现在在倒数第二的位置。（请读者证明）
-
最后，通过交替地放置一张牌到最后和丢弃一张牌，最终剩下一张牌，这张牌是d的另一半。（约瑟夫环的简化版本）
结语
人类对数学的探究可以追溯到古代文明时期。从古至今，数学在人类文明发展中扮演了重要角色，不仅在科学、技术、经济等领域发挥着基础性作用，还在哲学和艺术等方面产生了深远影响。
不由得让我们感叹，春晚的魔术中都蕴含着古人深刻的数学思想，难怪平时的我学起数学来迷迷糊糊，看魔术时候的我也汗流浃背(小尼脸)
