(Josephus )约瑟夫环问题 C语言实现

Myth丶恋晨 2024-04-19 16:21 72阅读 0赞

约瑟夫环问题的一种描述是：  
编号为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;
    			
    	}	
    }