题目描述
设有n个人围坐在圆桌周围，现从某个位置 i 上的人开始报数，数到 m 的人就站出来。下一个人，即原来的第m+1个位置上的人，又从1开始报数，再是数到m的人站出来。依次重复下去，直到全部的人都站出来，按出列的先后又可得到一个新的序列。由于该问题是由古罗马著名的史学家家Josephus提出的问题演变而来，所以通常称为Josephus 问题。
编写程序选择循环队列作为存储结构模拟整个过程，并依次输出出列的各人的编号。
input
输入三个数字n（1<=n<=1000），m(1<=m<=1000)，p(1<=p<=1000)。n和m见描述，p代表最开始从第p个人开始报数。
output
按出队顺序输出每个人的编号。
输入
8 4 1
输出
4 8 5 2 1 3 7 6
解法1.单向循环链表
#include<iostream>
#include<stdio.h>using namespace std;struct LNode
{int num;LNode *next;
};
LNode *p,*r,*h;
void joseph(int n, int m,int k)
{int i;for(i=1;i<=n; i++){p = new LNode;p->num=i;if(h==NULL)h=p;elser->next=p;r=p;}p->next=h;p=h;r=p;for(int i=1;i<k;i++){p=p->next;}while(p->next!=p){for(i=1;i<m; i++){r=p;p=p->next;}r->next=p->next;printf("%d ",p->num);delete p;p=r->next;}printf("%d\n",p->num);}int main(void)
{int n,m,p;scanf("%d%d%d",&n,&m,&p);joseph(n,m,p);return 0;
}
解法2.循环队列
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#define maxn 10000
using namespace std;
int acc;
int in(int *Q ,int rear,int val)
{rear=(rear+1)%maxn;Q[rear]=val;return rear;
}
int out(int *Q,int front)
{front=(front+1)%maxn;acc=Q[front];return front;
}
int main(void)
{int n,m,p;int *Q;scanf("%d%d%d",&n,&m,&p);Q=(int *)malloc(maxn*sizeof(int));int i,front,rear;front=rear=0;for(i=1;i<=n;i++){Q[i]=i;}rear=i-1;for(i=1;i<p;i++){front=out(Q,front);rear=in(Q,rear,acc);}while((front+1)!=rear){for(i=1;i<m;i++){front=out(Q,front);rear=in(Q,rear,acc);}front=out(Q,front);printf("%d ",acc);}front=out(Q,front);printf("%d\n",acc);return 0;
}
注意： 循环链表的指针的头尾指针的进位；