C++编程求Josephus(约瑟夫环)问题:m个小孩子围成一圈,从第一个小孩子开始顺时针方向数数字,到第n个小孩子离开,这样反反复复,最终只剩下一个小孩子,求第几个小孩子留下?
//用C++链表，次链表是单向循环链表，方便操作
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <windows.h>
using namespace std;
/////////////////////////////////////////////////////////////////
class ys//定义类
{
int s;
public:
ys *next;
friend ys *set(int n);
void get(ys *s);
void putout(ys *t,int m,int n);
};
/////////////////////////////////////////////////
ys *set(int n)//初始化链表
{
ys *q=new ys,*h=q;
int i;
for( i=1;i<n;i++)
{
q->s=i;
q->next=new ys;
q=q->next;
}
q->next=h;
q->s=i;
return q;
}
/////////////////////////////////////////////////////////
void ys::get(ys *s)//输出所有的小孩
{
int tem=s->s;
while(s->next->s!=tem)
{
cout<<s->next->s<<'\t';
s=s->next;
}
// cout<<s->s<<endl;
}
///////////////////////////////////////////////////////////////
void ys::putout(ys *t,int m,int n)//输出剩下的一个小孩
{
//cout<<"指针："<<t->s<<endl;
ys *h=t->next,*p=t;
int i=0;
for(;n>1;)
{
i++;
if(i%m!=0)
{p=h;h=h->next;}
else
{p->next=h->next;delete h;h=p->next;n--;}
}
cout<<endl<<"n:"<<h->s<<endl;
}
/////////////////////////////////////////////////////////////////
int main()
{
cout<<"请输入n个小孩，间隔为m：\n";
int n,m;
cin>>n>>m;
ys yue;
ys *head;
head=set(n);
yue.get(head);
yue.putout(head,m,n);
return 0;
}
///////////////////////////////////////////////////////////////////
作者：Luiing 转载请注明出处http://mtoou.info/c-yuesefuhuan-wenti/