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;
}
///////////////////////////////////////////////////////////////////
