约瑟夫问题

灰太狼 2022-04-16 00:46 198阅读 0赞

## 约瑟夫问题 ##

![在这里插入图片描述][20181114211743434.jpg]

*  题目描述：  
    开始有5个人围成圆形，从0号开始，数2个人，谁被数到就出列。比如第一次是2，2出列，再从3开始数，第二次数到0，0再出列。循环下去，直到最后一位。  
    输出：出列的人顺序

--------------------

## 代码实现(利用循环链表+企业链表的原理) ##

#include <stdio.h>
    #include <stdlib.h>
    
    #define NUMBER_OF_PERSON 8
    #define STRIDE 3
    
    
    typedef struct PNODE
    { 
    	struct PNODE* next;	
    }pNode;
    
    
    
    
    typedef struct PERSON
    { 
    	pNode node;
    	int id;	
    }Person;
    
    
    Person Table[NUMBER_OF_PERSON];// 定义Person 数组
    
    
    int main(void)
    { 
    
    	//给数组赋值
    	for(int i=0;i<NUMBER_OF_PERSON;i++)
    	{ 
    		Table[i].id=i;
    		if(i<NUMBER_OF_PERSON-1)
      			Table[i].node.next=(pNode*)&Table[i+1];
    		else//最后一个next指向第一个，这样才能循环
    			Table[i].node.next=(pNode*)&Table[0];
    		
    	}
    
    	
    
    	pNode* pCurrent = (pNode*)&Table[0];
    	int Stride = STRIDE;
    	int NumOfPerson = NUMBER_OF_PERSON;
    
    	while(NumOfPerson>1)//当有两个或者以上的人，才有意义
    	{ 
    		if(Stride==1)//已经数到stride-1，需要将下一个节点删除
    		{ 
    			NumOfPerson--;
    			Stride = STRIDE;
    
    			Person* p = (Person*)pCurrent->next;//打印要删除的节点
    			printf("%d ",p->id);
    
    			pCurrent->next = pCurrent->next->next;//删除节点
    			pCurrent=pCurrent->next;//跳到删除节点的下一个节点
    			continue;//直接执行下次循环，stride不能--，否则和STRIDE=2相同效果
    		}
    
    		pCurrent =pCurrent->next;
    		Stride--;
    
    	}
    
    	Person* p = (Person*)pCurrent;
    	printf("%d ",p->id);
    
    	
    	return 0;
    }

结果：  
![在这里插入图片描述][20181114224320737.png]

[20181114211743434.jpg]: /images/20220416/08e09b53e440482a8862dbc13b083e49.png
[20181114224320737.png]: /images/20220416/0374953e2f7f415a9b615f1fc72e0baf.png