循环队列和约瑟夫环问题.doc

发布时间：2022-06-09 发布人：admin 分类：说明书资料大小：0.04M 资料格式：doc 举报版权申诉

dhzhangxd-4679264-4744302543291346331.doc.pdf-第1页.png

第1页 / 共9页

dhzhangxd-4679264-4744302543291346331.doc.pdf-第2页.png

第2页 / 共9页

dhzhangxd-4679264-4744302543291346331.doc.pdf-第3页.png

第3页 / 共9页

dhzhangxd-4679264-4744302543291346331.doc.pdf-第4页.png

第4页 / 共9页

dhzhangxd-4679264-4744302543291346331.doc.pdf-第5页.png

第5页 / 共9页

dhzhangxd-4679264-4744302543291346331.doc.pdf-第6页.png

第6页 / 共9页

dhzhangxd-4679264-4744302543291346331.doc.pdf-第7页.png

第7页 / 共9页

dhzhangxd-4679264-4744302543291346331.doc.pdf-第8页.png

第8页 / 共9页

文本预览

约瑟夫环约瑟夫环的实现：设有 n 个人围坐在圆桌周围，现从某个位置 i 上的人开始报数，数到 m 的人就站出来。下一个人，即原来的第 m+1 个位置上的人，又从 1 开始报数，再是数到 m 的人站出来。依次重复下去，直到全部的人都站出来，按出列的先后又可得到一个新的序列。由于该问题是由古罗马著名的史学家 Josephus 提出的问题演变而来，所以通常称为 Josephus 问题。例如：当 n=8,m=4,i=1 时，得到的新序列为： 4，8，5，2，1，3，7，6 编写程序选择循环队列作为存储结构模拟整个过程，并依次输出出列的各人的编号。 //循环队列的定义 #include using namespace std; #define MAXSIZE 100 #define OK #define ERROR 1 0 typedef int Status; typedef int DataType; //创建一个循环队列结构体

struct SqQueue { }; DataType data[MAXSIZE]; int front; int rear; //初始化队列 Status InitQueue(SqQueue &Q) { } Q.front = Q.rear = 0; return OK; //求长度 int QueueLength(SqQueue Q) { } return (Q.rear - Q.front + MAXSIZE) % MAXSIZE; //插入队尾

Status EnQueue(SqQueue &Q,DataType e) { } if((Q.rear + 1) % MAXSIZE == Q.front)//队列满 return ERROR; Q.data[Q.rear] = e; Q.rear = (Q.rear +1) % MAXSIZE; return OK; //从队头删除数据 Status DeQueue(SqQueue &Q,DataType &e) { } if(Q.rear == Q.front) return ERROR; e = Q.data[Q.front]; Q.front = (Q.front +1) % MAXSIZE; return OK; //清楚队列 Status ClearQueue(SqQueue &Q) {

Q.rear = Q.front = 0; return OK; } //返回对头节点 bool QueueEmpty(SqQueue Q) { } if(QueueLength(Q) == 0) return true; else return false; //实现 // 循环队列.cpp : 定义控制台应用程序的入口点。 // /* 约瑟夫环的实现：设有n个人围坐在圆桌周围，现从某个位置i 上的人开始报数，数到m 的人就站出来。下一个人，即原来的第m+1个位置上的人，又从开始报数，再是数到m的人站出来。依次重复下去，直到全部的

人都站出来，按出列的先后又可得到一个新的序列。由于该问题是由古罗马著名的史学家Josephus提出的问题演变而来，所以通常称为Josephus 问题。例如：当n=8,m=4,i=1时，得到的新序列为： 4，，，，，，，编写程序选择循环队列作为存储结构模拟整个过程，并依次输出出列的各人的编号。 */ #include "stdafx.h" #include "SqQueue.h" #include using namespace std; //约瑟夫环 void Josephus(int num,int count) { SqQueue Q1,Q2,result; //创建三个队列 InitQueue(Q1); InitQueue(Q2);

InitQueue(result); //创建了一个环 for(int i = 1; i <= num; i++) { } EnQueue(Q1,i); int temp; while(QueueLength(result) != num) { for(int j = 1; j < count; j++) //转换 { //判断队列是否到达队尾 if(QueueEmpty(Q1)) { } while(!QueueEmpty(Q2)) { } DeQueue(Q2,temp); EnQueue(Q1,temp);

//将数据转移 DeQueue(Q1,temp); EnQueue(Q2,temp); } //判断队列是否到达队尾,这种情况出现在移动 if(QueueEmpty(Q1)) { } while(!QueueEmpty(Q2)) { } DeQueue(Q2,temp); EnQueue(Q1,temp); DeQueue(Q1,temp); EnQueue(result,temp); } cout<<"输出结果："<

while(! QueueEmpty(result)) { } DeQueue(result,temp); cout<>n>>m; Josephus(n,m); return 0;

分享到：

赞收藏

资料库

循环队列和约瑟夫环问题.doc

相关推荐

课程资源

热门标签

最新资料