约瑟夫环

约瑟夫环

约瑟夫环

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

全部出列。请利用以下链队列实现该算法。

#define OK 1#define ERROR 0#define OVERFLOW -2typedef int QElemType;typedef int Status;//- - - - - 链队列定义- - - - - typedef struct QNode { QElemType data; struct QNode *next;} QNode, *QueuePtr;typedef struct { QueuePtr front; QueuePtr rear; } LinkQueue;//初始化Status InitQueue(LinkQueue &Q) { Q.front = Q.rear = new QNode; Q.front->next = NULL; return OK;}//入队Status EnQueue(LinkQueue &Q, QElemType e) { QueuePtr p; p = new QNode; p->data = e; p->next = NULL; Q.rear->next = p; Q.rear = p; return OK;}//出队Status DeQueue(LinkQueue &Q, QElemType &e) { QueuePtr p; if (Q.front == Q.rear) return ERROR; p = Q.front->next; e = p->data; Q.front->next = p->next; if (Q.rear == p) Q.rear = Q.front; delete p; return

输入 n,k,m

输出 出列次序。

样例输入

10 3 5

样例输出 7 2 8 4 1 10 3 6 9 5

直接上代码：

/***链队的基本操作***/#includeusing namespace std;#define OK 1#define ERROR 0#define OVERFLOW -2typedef int QElemType;typedef int Status;//- - - - - 队列的链式存储结构- - - - - typedef struct QNode {QElemType data;struct QNode *next;} QNode, *QueuePtr;typedef struct {QueuePtr front; //队头指针QueuePtr rear; //队尾指针} LinkQueue;//链队的初始化Status InitQueue(LinkQueue &Q) {//构造一个空队列QQ.front = Q.rear = new QNode; //生成新结点作为头结点，队头和队尾指针指向此结点Q.front->next = NULL; //头结点的指针域置空return OK;}//链队的入队Status EnQueue(LinkQueue &Q, QElemType e) {//插入元素e为Q的新的队尾元素QueuePtr p;p = new QNode; //为入队元素分配结点空间，用指针p指向p->data = e; //将新结点数据域置为ep->next = NULL;Q.rear->next = p; //将新结点插入到队尾Q.rear = p; //修改队尾指针return OK;}//链队的出队Status DeQueue(LinkQueue &Q, QElemType &e) {//删除Q的队头元素，用e返回其值 QueuePtr p;if (Q.front == Q.rear)return ERROR; //若队列空，则返回ERRORp = Q.front->next; //p指向队头元素e = p->data; //e保存队头元素的值Q.front->next = p->next; //修改头指针if (Q.rear == p)Q.rear = Q.front; //最后一个元素被删，队尾指针指向头结点delete p; //释放原队头元素的空间return OK;}void JOSEPHUS(int n,int k,int m) //约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐//在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人//又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人//全部出列。{LinkQueue Q;QElemType e;int i;InitQueue(Q);for(i=1;i<=n;i++) EnQueue(Q,i); for(i=1;i>n>>k>>m;JOSEPHUS(n,k,m);return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。