约瑟夫环
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;
}