防走失，电梯直达
安全岛
报人刘亚东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) = 1f(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的另一半。（约瑟夫环的简化版本）
结语
人类对数学的探究可以追溯到古代文明时期。从古至今，数学在人类文明发展中扮演了重要角色，不仅在科学、技术、经济等领域发挥着基础性作用，还在哲学和艺术等方面产生了深远影响。
不由得让我们感叹，春晚的魔术中都蕴含着古人深刻的数学思想，难怪平时的我学起数学来迷迷糊糊，看魔术时候的我也汗流浃背(小尼脸)
