用顺序表解决约瑟夫环问题

一、实验题目：约瑟夫环问题：设编号为1，2，3，……，n的n(n>0)个人按顺时针方向围坐一圈，m为任意一个正整数。从第一个人开始顺时针方向自1起顺序报数，报到m时停止并且报m的人出列，再从他的下一个人开始重新从1报数，报到m时停止并且报m的人出列。如此下去，直到所有人全部出列为止。要求设计一个程序模拟此过程，对任意给定的m和n，求出出列编号序列。实验要求：用顺序表实现。
二、设计分析：
首先创建了一个顺序表，并且用数组存每个人的编号，出列的时候将此编号置为0，代表此位置的人已经出列，循环查询编号不为0的元素，并用变量j记下当前是第几个人，当j==m的时候，代表此位置是第m个人，输出并将编号置为0，用k记录出列人的下一位的索引，并将数组长度-1，再进行新一轮的循环，直到所有人都出列。
三、程序代码：

#include<iostream>
#include<cstdlib>
using namespace std;
const int MaxSize=100;
typedef struct Node{
	int data[MaxSize];
	int length;
}List;
void CreateList(List *&L,int n){
	L=(List *)malloc(sizeof(List*));
	for(int i=1;i<=n;i++){
		L->data[i]=i;
	}
	L->length=n;
}
void DispList(List *&L,int m){
	int len=L->length;
	int j=0,k=1;
	while(L->length){
		 for(int i=1;i<=len;i++){
		 	if(L->data[k]){
		 		j++;
			}
			if(j==m){
				cout<<L->data[k]<<" ";
				L->data[k]=0;
				L->length--;
				j=0;
				k=(k+1)%(len+1)?(k+1)%(len+1):1;
				break;
			}
			k=(k+1)%(len+1)?(k+1)%(len+1):1;
		 }
	}
	
}
int main(){
	int m,n;
	cin>>m>>n;
	List *L;
	CreateList(L,n);
	DispList(L,m);
        return 0;
} 

用顺序表解决约瑟夫环问题

原文：https://www.cnblogs.com/xbdcjs/p/14639584.html