/*****Josephus 求解方法一：计数方法******/
void Josephus_1(int n,int m)
{
int *array=new int[n];
int *result=new int[n];
int s,count;
s=0;//记录出局人数
count=0;//记数
//赋初值
for(int i=0;i<n;i++)
{
array[i]=i;
result[i]=-1;
cout<<i<<",";
}
cout<<endl;
//循环遍历,计数到m就出局，s++
while(s<n)
{
for(int i=0;i<n;i++)
{
if(array[i]==-1)
{//表示此人已出局
}else
{
count++;
if(count==m)
{
array[i]=-1;
result[s]=i;
s++;
count=0;
}
}
}
}
for(int i=0;i<n;i++)
{
if(array[i]!=0)
{
result[s]=i;
break;
}
}
for(int i=0;i<n;i++)
{
cout<<result[i]<<",";
}
cout<<endl;
delete array;
delete result;
}
/*****Josephus 求解方法二：采用循环链表******/
void Josephus_2(int n,int m,int k)
{
node_t* pre=new node_t[n];
node_t* tmp1=pre;
node_t* tmp2=pre;
int count_n=0;
int count_m=0;
int count_k=0;
int *out=new int[n];
cout<<"输出原始编号：";
for(int i=0;i<n-1;i++)
{
tmp1->data=i+1;
tmp1->next=pre+i+1;
cout<<tmp1->data<<",";
tmp1=tmp1->next;
out[i]=-1;
}
out[n-1]=-1;
tmp1->data=n;
cout<<tmp1->data<<",";
tmp1->next=pre;//链表的首尾相接
cout<<endl;
tmp1=pre;
cout<<"模拟过程如下："<<endl;
while(count_n<n)
{
count_k=1;
count_m=1;
while(count_k<k)
{//跳到第K个人
count_k++;
tmp1=tmp1->next;
}
while(count_m<m)
{//数m个
cout<<tmp1->data<<",";
tmp2=tmp1;//记录下前一个，便于删除操作
tmp1=tmp1->next;
count_m++;
}
//输出出局
cout<<tmp1->data<<endl;
out[count_n++]=tmp1->data;
//删除节点
tmp2->next=tmp1->next;
delete tmp1;
tmp1=tmp2->next;
}
//输出出局顺序
cout<<"出局顺序："<<endl;
for(int i=0;i<n;i++)
{
cout<<out[i]<<",";
}
cout<<endl;
}