约瑟夫有关问题（经典有关问题）

约瑟夫问题（经典问题）

约瑟夫问题（有时也称为约瑟夫斯置换，是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。又称“丢手绢问题”.）

问题来源：

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

算法分析：

1.数组法（也可利用指针实现）。利用数组存储n个编号，不断循环查找第m个要被杀的人，实现循环的关键就是对出现过的数据统一标记为0，利用某个变量记录间隔数目，找出满足要求的进行0标记，当循环从0到n时，使i=0，再次进入循环，直到寻找到的人数k==n，输出最后一个，即为生存者。代码如下：

#include<iostream>
using namespace std;
void main()
{
	int n,m,a[101],k,i,j,num;
	cout<<"请输入   人数(不超过100人) & 自杀的人之间的跨度:\n";
	cin>>n>>m;
	for(i=1;i<=n;i++)
	{
		a[i]=1;
	}
	j=0;
	k=0;
	for(i=1;i<=n;i++){
		if(a[i]==1){
			j=j+a[i];
			if(j==m)
			{
				j=0;
				a[i]=0;
				cout<<i<<"->";
				k++;
				if(k%16==0)
					cout<<'\n';
			}
			if(k==n){
				num=i;
				break;
			}
		}
		if(i==n)
			i=0;
	}
	cout<<"最后生存的是第"<<num<<"号！"<<endl;
	cout<<"----------------------------------------"<<endl;
}

2.链表法

利用循环链表搭建整个联系网络，主要是链表的建立和删除，实现上就是将数组思想转化为链表思想。代码如下：

#include<iostream>
using namespace std;
struct Node{
	int num;
	struct Node *next;
}*Joseph;
int n,m;
void Create();
int del();
int main()
{
	scanf("%d%d",&n,&m);
	if(n==0)
	{
		cout<<"0人怎么玩。。。。。o(╯□╰)o\n";
		
		return 0;
	}
	
	Create();
	
	cout<<"\n\n生存者是第"<<del()<<"人\n\n";
	return 0;
}
void Create()
{
	int i=1;
	Joseph=NULL;
	Node *p,*q;
	p=q=NULL;
	
	while(i<=n)
	{
		p=new Node;
		p->num=i++;
		if(Joseph==NULL)
			Joseph=p;
		else
			q->next=p;
		q=p;
	}
	
	if(Joseph!=NULL)
		q->next=Joseph;
}
int del()
{
	int count=1;
	
	Node *p,*q;
	
	q=Joseph->next;
	p=Joseph;
	while(q!=q->next)
	{
		count++;
		if(count%m==0)
		{
			p->next=q->next;
			cout<<q->num<<"->";
			delete q;
			q=p->next;
		}
		else
		{
			p=q;
			q=q->next;
		}
	}
	cout<<q->num;
	return q->num;
}