“约瑟夫环”问题的四种方法及详解注释（c++或c语言实现）

Ⅰ.故事背景

据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决。Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。 [1]

17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事：15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。

Ⅱ.问题描述

算法举例抽象为：已知 n 个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。第一个人开始报数，数到 k 的那个人出圈；他的下一个人又从 1 开始报数，数到 k 的那个人又出圈；依此规律重复下去，直到剩余最后一个胜利者。

(图片以n=10，k=3为例）

Ⅲ.代码实现

#include<iostream>
using namespace std;
#include<stdlib.h>
#define ok -1
#define error -2
typedef int Status;
typedef int ElemType; 
typedef struct LNode
{
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;
Status InitList(LinkList &L,LinkList &M);//初始化 
Status fuzhi(LinkList &L,int x);         //赋值 
void shuchu(LinkList L);				//输出 
void delete1(LinkList &L,int m,int x);  //进行删除 ,m是死的位置（每第几个位置），x是数量 
int main()
{
	LinkList L,M;
	int x,m,n;
	ElemType y,e;
	x=InitList(L,M);
	if(x==error) cout<<"初始化失败";
	else         cout<<"初始化成功"<<endl;
	cout<<"请决定为线性表L赋几个元素:";
	cin>>x;
	fuzhi(L,x);
	cout<<"线性表L为："<<endl;
	shuchu(L); 
	cout<<"请决定规则（轮到哪个号去世）:";
	cin>>m;
	delete1(L,m,x);
	cout<<endl<<"最后存活的位置是最后的"<<m<<"个位置.若想活下两个，则应站在最后"<<m-1<<"个位置"<<endl;
	return 0;
}
Status InitList(LinkList &L,LinkList &M)
{
	L=new LNode;
	M=new LNode;
	if(L==NULL||M==NULL) return error;
	L->next=L;
	M->next=NULL;
	return ok;
}
Status fuzhi(LinkList &L,int x)
{
	LNode *s,*r=L;
	ElemType n=1;
	for(int i=1;i<=x;i++)
	{
		if(i==1)
		{
			L->data=n++;
		}
		else
		{
			s=new LNode;
			s->data=n++;
			s->next=r->next;
			r->next=s;
			r=s;
		}
	}
	return ok;
}
void shuchu(LinkList L)
{
	LNode *p=L;
	cout<<"单链表内容为:"<<endl;
	cout<<p->data<<" ";
	p=p->next;
	while(p!=L)
	{
		cout<<p->data<<" ";
		p=p->next;
	}
	cout<<endl;
}
void delete1(LinkList &L,int m ,int x)
{
	int j=0,i=2;
	LNode *p=L,*q;
	cout<<"被删除的有:"<<endl; 
	while(p->next!=p)
	{
		if(x-j<=m) break; 
		if(i%3==0)
		{
			q=p->next;
			p->next=q->next;
			i++; 
			cout<<q->data<<"  ";
			delete q;
			j++; 
		}
		i++;
		p=p->next;		
	}
	cout<<endl<<"最后可以存活位置为："<<endl<<"   ";
	for(int k=1;k<=m;k++)
	{
		cout<<p->data<<"  ";
		p=p->next;
	}
}