Josephus问题

1.算法描述

简单的游戏：有N个人坐成一圈，编号1-N、从编号为1的人开始传递热马铃薯。M次传递之后，持有马铃薯的人退出游戏，圈缩小，然后游戏从退出人下面的人开始，继续进行，最后留下的人获胜。如，M=0， N=5则参加游戏的人依次退出，5号获胜。M=1,N=5则退出顺序是2,4,1,5.

 

2.算法分析

该算法使用一个没有头指针的循环链表完成，移动的过程计数，如果计数为M，则将其移除并从下一位继续开始，否则继续。过程非常简单，主要考察指针的运用。当然还可以使用数组实现，不过移动所花费开销非常大！不推荐使用数组。

该算法的复杂度为O(n),直接对链表操作。

 

3.代码

#include <iostream>
#include <ctime>
using namespace std;
const int LNE = 100000;

struct Node{
	Node *next;
	int data;
};

//创建一个没有头结点的链表
Node* createList(int *a, int n){
	Node* first = new Node;
	first->data = a[0];
	Node* t = first;
	for(int i=1; i<n; i++){
		Node* r = new Node;
		r->data = a[i];
		t->next = r;
		t = r;
	}
	t->next = first;
	return first;
}

//N个人，传递M次
int josephus(Node *l, int M, int N){
	if(M<0 || N < 1) return -1;
	if(M >= N) M %= N;								//处理M
	int count = 0;				//用于计数
	Node *p = l, *t;
	//当M为0的时候处理方式，依次处理，最后一个人即是胜利者
	if(M == 0){
		while(1){
			if(p->next == l) return p->data;
			t = p;
			//cout<<p->data<<" ";
			p = p->next;
			delete t;
		}
	}else{
		//循环到只剩最后一个人
		while(N != 1){
			//计数到M之前的位置
			if(count == M-1){
				t = p->next;
				//只剩最后元素，退出
				if(t == p){
					 break;
				}else{							//没有到最后一个
					 p->next = t->next;
					 //cout<<t->data<<" ";
					 delete t;
					 N --; 						//总人数减去1
				}
				count = -1;
			}
			p = p->next;
			count ++;							//计数器加1
		}
	}
	return p->data;
}

int main(){
	int *a = new int[LNE];
	for(int i=0; i<LNE; i++){
		a[i] = i+1;
	}
	
	int k;
	Node *f = createList(a, LNE);
	cout<<"输入传递次数：";
	cin>>k;

	time_t b = time(NULL);
	cout<<endl;
	cout<<"胜利者是："<<josephus(f, k, LNE)<<endl;
	time_t e = time(NULL);
	cout<<"耗时："<<e-b<<endl;
	delete []a;
	return 0;
}