Josephus 问题
Josephus 问题是指下面的游戏:
有 $N$ 个人坐成一圈, 编号依次为 $1,2,3,\ldots,N$.
从编号 $1$ 的人开始传递马铃薯. $M$ 次传递之后, 持有热马铃薯的人退出游戏, 圈缩小. 然后游戏从退出者下一位开始, 继续进行.
最终留下来的人获胜.
这样, 如果 $M=0$ 并且 $N=5$, 那么参加游戏的人依次退出, $5$ 号获胜.
如果 $M=1$ 并且 $N=5$, 那么退出的顺序就是 $2$、$4$、$1$、$5$. 最后是 $3$ 号获胜.
比如:
Josephus problem!
Please input the number of players: N = 5
Please input the gap: M = 1
N=5
M=1
start index =1
deleting 2
now vector a is
1 3 4 5
next index =2
--------------
start index =2
deleting 4
now vector a is
1 3 5
next index =3
--------------
start index =3
deleting 1
now vector a is
3 5
next index =1
--------------
start index =1
deleting 5
now vector a is
3
next index =2
--------------
start index =2
deleting 3
now vector a is
next index =1
--------------
=======================
The queue is:
2 4 1 5 3
References:
《数据结构与算法分析C++描述》(第3版)P.81, Exer 3.6.
https://en.wikipedia.org/wiki/Josephus_problem