#include
using namespace std;
struct Node{
int data;
Node *next;
};
void Josephus()
{ Node *pre,*p,*q,*s;
int n,k,m;
cout<<"总人数:"< cin>>n;
cout<<"开始报数的编号:"< cin>>k;
cout<<"退出的序号:"< cin>>m;
int count=2;
s=new Node;
pre=s;
p=pre->next;
for(int i=1;i { s->data=i;
s->next=new Node;
s=s->next;
}
s->data=n;
s->next=pre;
p=pre->next;
for(int i=1;i { pre=pre->next;
p=p->next;
}
while(p!=pre)
{ if(count!=m)
{ pre=p;
p=p->next;
count++;
}
else
{ cout<<"出列序号:"<data< q=p->next;
p->next=q->next;
delete q;
count=0;
}
}
cout<data<<endl;
delete p;
}
int main()
{ Josephus();
return 0;
}
http://blog.csdn.net/wenhai_zh/article/details/9620847
http://blog.chinaunix.net/uid-22556372-id-1773437.html
建议你读读左飞老师的《算法之美》
我自己写了一个:
#include<iostream>
using namespace std;
struct jose
{
int code;
jose * next;
};
void Josephus(int num, int n,int begin)
{
int i;
jose * p = new jose[num];
jose * p_current = p;
for (i = 0; i < num; i++)
{
p[i].code = i + 1; //对人进行编号
p_current->next = p + (i + 1) % num; //记录下一个人
p_current = p_current->next; //修改当前的人
}
jose * pivot=NULL;
/*
确定当前那个结构指针是指向那个人
*/
if (begin==1)
p_current = &p[num-1];
else
p_current = &p[begin - 2];
while (p_current->next != p_current)
{
for (int j = 0; j < n; j++)
{
pivot = p_current;
p_current = pivot->next;
}
cout << "出列人:";
cout << p_current->code << endl;; //输出脱离的人的编号
pivot->next = p_current->next; //去除脱离人的结构
p_current = pivot;
}
cout << "获胜人:";
cout << p_current->code << endl;
delete[] p;
}
int main()
{
cout << "总人数:";
int num, n,begin;
cin >> num;
cout << "开始报数的人的编号:";
cin >> begin;
cout << "出列人的报数为:";
cin >> n;
Josephus(num, n,begin);
system("pause");
return 0;
}
输出结果: