约瑟夫环

共计 532 个字符，预计需要花费 2 分钟才能阅读完成。

约瑟夫环
Josephus 有过的故事：39 个犹太人与 Josephus 及他的朋友躲到一个洞中，39 个犹太人决定宁愿死也不要被敌人抓。于是决定了自杀方式，41 个人排成一个圆圈，由第 1 个人开始报数，每报数到第 3 人该人就必须自杀。然后下一个重新报数，直到所有人都自杀身亡为止。然而 Josephus 和他的朋友并不想遵从，Josephus 要他的朋友先假装遵从，他将朋友与自己安排在第 16 个与第 31 个位置，于是逃过了这场死亡游戏。
分析我们可以用一个队列解决这个问题。首先，将 1 -41 按顺序放入队列中。然后，从队首开对报数，如果报数为 1 和 2，则出对后进队，报数为 3 的出对操作，直至队列只剩下 2 个元素。
代码块
#define value 3
queue<int> Q;
int main(){
int n;
while(scanf(“%d”,&n)!=EOF){
int i;
for(i=1;i<=n;i++){
Q.push(i);
}
while(Q.size()>1){
for(i=1;i<value;i++){
Q.push(Q.front());
Q.pop();
}
Q.pop();
}
while(!Q.empty()){
printf(“%d\n”,Q.front());
Q.pop();
}
}
return 0;
}