C++求约瑟夫环问题

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/

3 thoughts on “C++求约瑟夫环问题

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>