约瑟夫环(约瑟夫问题)的起源可以追溯到公元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的人,他就是游戏的赢家。
(文、图/华玲,编审/张慧娟,审核/王俊华)