您想知道的人工智能干货,第一时间送达
约瑟夫环(约瑟夫问题)的起源可以追溯到公元1世纪,当时有一个名叫约瑟夫的犹太历史学家。据传,他和他的同伴被敌人包围,在面临绝境时,他们决定宁死不屈,于是决定通过自杀的方式结束生命。为了执行这个决定,他们围成一个圈,然后按照一定的规则来选择自杀的人,直到只剩下最后一个人。约瑟夫,作为一个不愿意自杀的人,快速地计算出了一个位置,使得他成为了最后一个存活的人,从而有机会逃脱。
将这个故事抽象成数学模型,我们得到了约瑟夫环问题:假设有n个人围成一圈,从某个人开始,按顺时针方向逐一编号。接着从编号为1的人开始报数,每数到m就将该人从圈中排除,然后从下一个人重新开始报数,直到圈中只剩下一个人。
比如说,如果有6个人(n = 6)参与游戏(编号为1到6),选择的m是3,那么游戏进行的过程大概是这样的:
我们用伪代码解答:
f( n, m){
return n == 1 ? n : (f(n - 1, m) + m - 1) % n + 1;
}
这个函数f接收两个参数:
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
的那个人。
约瑟夫环问题如何能成为递归算法的经典案例?结合计算思维,我们进一步探讨。
递归算法的核心思想是将问题分解成更小的子问题,直到这些子问题足够小,可以直接解决。约瑟夫环问题本质上具有自相似的结构:每当一个人被淘汰,剩下的人又形成了一个较小的圈,规则不变,这就构成了一个更小规模的约瑟夫环问题。这种自相似性质使得约瑟夫环问题非常适合用递归方法来解决。
递归算法是分而治之策略的一种体现。在约瑟夫环问题中,通过递归调用,我们不断缩小问题的规模(即每次减少一个人),直到达到一个基本情况(只剩下一个人)。这种方法能够将一个复杂问题简化为易于管理和解决的小问题,是计算思维中分解问题的典型例证。
在刘谦的魔术中,约瑟夫问题的核心思想被巧妙地应用于控制过程的结果。约瑟夫问题是通过固定间隔来选择和排除序列中的对象,直到只剩一个对象。在这个魔术中,尽管没有直接使用固定间隔的排除方法,但通过一系列精心设计的操作步骤(如牌的折叠、插入、丢弃等),实现了类似的控制效果,即无论参与者如何执行这些步骤,都会以一种预定的方式减少牌的数量,最终留下一张特定的牌。
让我们试着逐步分析:
结语
联系客服