🍀 什么是约瑟夫环

约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知 n 个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为 k 的人开始报数，数到 m 的那个人出圈；他的下一个人又从 1 开始报数，数到 m 的那个人又出圈；依此规律重复下去，直到剩余最后一个胜利者。

👩 举例: 哪个女演员能成为女主角

例如：有10个演技相当的女演员都来竞选这个剧的女主角，那么怎么选呢，可以让她们玩一个游戏，坐在一张圆桌边进行此游戏，每个人编号为 1-10 。若规定数到 3 的人出圈。则游戏过程如下。

如图

🎮 游戏过程

1. 开始报数，第一个数到 3 的人为 3 号，3 号出圈。

   1， 2，【3\color{red}{3}3】， 4， 5， 6， 7， 8， 9， 10。

2. 从4号重新从1开始计数，则接下来数到3的人为6号，6号出圈。

   1， 2，【3\color{red}{3}3】， 4， 5， 【6\color{red}{6}6】， 7， 8， 9， 10。

3. 从7号重新从1开始计数，则接下来数到3的人为9号，9号出圈。

   1， 2，【3\color{red}{3}3】， 4， 5， 【6\color{red}{6}6】， 7， 8， 【9\color{red}{9}9】， 10。

4. 从10号重新从1开始计数，由于10个人称环形结构，则接下来数到3的人为2号，2号出圈。

   1， 【2\color{red}{2}2】，【3\color{red}{3}3】， 4， 5， 【6\color{red}{6}6】， 7， 8， 【9\color{red}{9}9】， 10。

5. 从4号重新从1开始计数，则接下来数到3的人为7号，7号出圈。

   1， 【2\color{red}{2}2】，【3\color{red}{3}3】， 4， 5， 【6\color{red}{6}6】， 【7\color{red}{7}7】， 8， 【9\color{red}{9}9】， 10。

6. 从8号重新从1开始计数，则接下来数到3的人为1号，1号出圈。

     【1\color{red}{1}1】， 【2\color{red}{2}2】，【3\color{red}{3}3】， 4， 5， 【6\color{red}{6}6】， 【7\color{red}{7}7】， 8， 【9\color{red}{9}9】， 10。

7. 从4号重新从1开始计数，则接下来数到3的人为8号，8号出圈。

   【1\color{red}{1}1】， 【2\color{red}{2}2】，【3\color{red}{3}3】， 4， 5， 【6\color{red}{6}6】， 【7\color{red}{7}7】， 【8\color{red}{8}8】， 【9\color{red}{9}9】， 10。

8. 从10号重新从1开始计数，则接下来数到3的人为5号，5号出圈。

   【1\color{red}{1}1】， 【2\color{red}{2}2】，【3\color{red}{3}3】， 4， 【5\color{red}{5}5】， 【6\color{red}{6}6】， 【7\color{red}{7}7】， 【8\color{red}{8}8】， 【9\color{red}{9}9】， 10。

9. 从10号重新从1开始计数，则接下来数到3的人为10号，10号出圈。

   【1\color{red}{1}1】， 【2\color{red}{2}2】，【3\color{red}{3}3】， 4， 【5\color{red}{5}5】， 【6\color{red}{6}6】， 【7\color{red}{7}7】， 【8\color{red}{8}8】， 【9\color{red}{9}9】， 【10\color{red}{10}10】。

10. 最终剩余 4 号，4 号女演员当选女主角。

🎫 算法实现

📙 思路

用python列表求解：

先用一个列表去标识这 n 个人的状态，默认全为 1 ，也就是都在圈子内，当数到 m的人出圈之后，标识置为 0（就是出圈了），同时报数器清 0，下一个人要从 1 开始。在每次报数之前要判断他是否在圈子内（也就是他的标识是否为 1 ），如果在圈子里面才会继续报数。定义一个变量记录出圈的人数， 出圈的人数等于  n-1 时，则游戏结束。

💻 详细代码和运行结果

def select_actor(n, m):
    count = 0   # 记录已经出圈的人数
    num = 0     # 报数器
    status_list = []  # 参与游戏人的状态，初始都为1
    for i in range(n):
        status_list.append(1)

   # 开始游戏，报数，计数
    while count < n - 1:
        for i in range(n):
            if status_list[i] == 1:
                num +=1
                if num==m: # 此人数到m则出圈, 报数器清零
                    count += 1
                    print("%d 号退出竞选" % (i+1))
                    status_list[i] = 0
                    num = 0
                if count == n - 1:
                    break

    for idx, val in enumerate(status_list):
        if val==1:
            print("%d号取得当女主角的资格" % (idx+1))

select_actor(10, 3)

运行结果