(Josephus )約瑟夫環問題 C語言實作

約瑟夫環問題的一種描述是：

編号為1,2,…,n的n個人按順時針方向圍坐一圈，每人持有一個密碼(正整數)。

一開始任選一個整數作為報上限制m，從第一個人開始順時針自1開始順序報數，報到m時停止報數。

報m的人出列，将他的密碼作為新的m值，從他在順時針方向上的下一個人開始重新從1報數，

如此下去，直至所有的人全部出列為止。試設計一個程式，求出列順序。

#include<stdio.h>
#include<stdlib.h>

void CreatList(int n);//建立函數 
void DeleteList(int m,int n);//出列函數 

typedef struct NodeType{
	int id;//每個人的序号 
	int password;//每個人的密碼 
	struct NodeType *next;
}Nodetype;

NodeType *pHead = NULL;


int main(){
	
	int m,n;//m為初始密碼，n為人數 
	scanf("%d%d",&m,&n);
	
	CreatList(n);
	DeleteList(m,n);
	
	return 0;
}

//建立函數 
void CreatList(int n){
	
	NodeType *pNew,*pEnd;
	pEnd = (NodeType *)malloc(sizeof(NodeType));
	
	for(int i=1;i<n+1;i++){
		
		pNew = (NodeType *)malloc(sizeof(NodeType));
		pNew->id = i;
		int password;
		
		printf("\n請輸入第%d個人的密碼：",i);
		scanf("%d",&password);
		pNew->password=password;

		if(i==1) pHead = pNew;
		else     pEnd->next = pNew;	
		pNew->next = pHead;
		pEnd = pNew;		
	}
			
}

//出列函數 
void DeleteList(int m,int n){
	
	int i=0;
	NodeType *p=pHead;
	NodeType *q=p;
	
	while(n--){
		
		
		if(m==1){
		while(q->next!=p)  q=q->next;
		pHead = p->next;//	
	}
		else{
		while(--m){
		q=p;
		p=p->next;
	}
	}
	
	printf("\n第%d個出列的數為：%d\n",++i,p->id);
	m=p->password;
	
	q->next = p->next;
	free(p);
	p=q->next;
	q=p;
			
	}	
}