约瑟夫环的问题

问题描述：编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。

双向链表

#include <iostream>
using namespace std;
//初始化 
struct LNode{
	int value;
	LNode *prior;
	LNode *next;
};
//main函数 
int main(){
	cout<<"一共有几个小朋友参加游戏:"<<endl;
	int num_of_people;
	cin>>num_of_people;
	//初始化一个头节点 
	LNode *nowNode=new LNode;
	nowNode->value=1;
	//建立双向链表，包含链表的插入 
	for(int i=2;i<=num_of_people;i++){
		nowNode->next=new LNode();
		nowNode->next->prior=nowNode;
		nowNode=nowNode->next;
		nowNode->prior->next=nowNode;
		nowNode->value=i;
    }
	//创建完双向链表后，将首位连接起来，建立成一个环状。
	nowNode->next->prior=nowNode;
	nowNode=nowNode->next;
	//输入第几个小孩在应该出去 
	int m; 
	cout<<"第几个小朋友退出:"<<endl; 
	cin>>m;
	//开始循环,包含链表的删除 
	LNode *temp=new LNode;//建立临时节点 
	int count=1;
	while(nowNode->next!=nowNode){
		if(count==m){
			cout<<nowNode->value<<" ";
			//删除
			nowNode->prior->next=nowNode->next;
			nowNode->next->prior=nowNode->prior;
			temp=nowNode->next;
			delete nowNode;
			nowNode=temp;
			count=1;
		}
		else{
			nowNode=nowNode->next;
			count++;
		}
	}
	cout<<nowNode->value<<"幸存"<<endl;
	delete(nowNode); 
}

循环链表

#include <iostream>
using namespace std;
typedef struct CLinkList{
	int num;
	struct CLinkList *next;
}node;
int main(){
	//建立循环链表、
	node *L,*r,*s;//r是尾指针 
	L=new node;
	r=L;
	int i;
	int n;
	cin>>n;
	int m;
	cin>>m;
	//利用后插法来建立链表 
	for(i=1;i<=n;i++){
		s=new node;
		s->num=i;
		r->next=s;
		r=s;
	}
	r->next=L->next;
	node *p;
	p=L->next;
	delete L;
	//解决约瑟夫环的问题
	while(p->next!=p){
		for(int i=1;i<m-1;i++){
			//每数k个人后死亡一人
			p=p->next;//向后推进 
		}
		cout<<p->next->num<<"->";//将该点删去 
		p->next=p->next->next;
		p=p->next; 
	} 
	cout<<p->num<<endl;
	return 0;
}

公式

#include <iostream>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int Joseph(int n,int m){
	if(n==1){
		return 0;//从这里返回，从0开始，只有一个元素就是剩余的元素0 
	}
	else{
		return (Joseph(n-1,m)+m)%n;//n是总共多少个数 
	}
}
int main(){
	int a,b;
	//递归求最后一个的编号
	cin>>a;
	cin>>b;
	//使用从正向思考
	cout<<"最后一个人是："<<Joseph(a,b)+1<<endl;
	int result=b-1;
	//第一个自杀的人为b-1 
	cout<<b;
	//每次自杀的都是b-1号，但是不同的b-1号换算到最初的序号所需要的次数是不同的 
	//外循环是循环不同的换算次数 
	for(int i=a;i>=2;i--){
		result=b-1;
		//内循环是开始运算 
		for(int j=i;j<=a;j++){
			result=(result+b)%j;
		}
		cout<<"->"<<result+1;//从0开始变1开始，所以加1 
	}
	return 0;
}