Question

c++ Josephus问题

Josephus问题：一群小孩围成一圈，任意假定一个数interval，从第一个小孩数起，数到第interval个的时候，该小孩离开，依次这样数下去，最后一个小孩是胜利者，问：胜利者是第几个小孩？
一：使用链表进行求解。这是关键
二：使用面向对象的方式进行求解。

Answer 1

下面的代码能解决你的问题，但类写得不够好，还很多问题：
#include <iostream>
using namespace std;
class CStudent
{
int n;
public:
CStudent(int nv):n(nv){}
void print()
{
cout<<" "<<n<<" ";
}
};

class CList
{
private:
class CItem
{
CStudent* pstu;
CItem* pnext;
public:
CItem(CStudent* pT,CItem* pN):pstu(pT),pnext(pN){}
friend class CList;
void print()
{
pstu->print();
}
};
CItem* pnow;
CItem* pzero;
public:
CList():pnow(0),pzero(0){}
void Push(CStudent* as)
{
pnow=new CItem(as,pnow);
if(pzero==0)pzero=pnow;
}
~CList()
{
while(pnow!=0)
{
CStudent* p=Pop();
delete p;
}
}
void Circle()
{
pzero->pnext=pnow;
pnow=pzero;
pzero=0;
}
CStudent* Pop()
{
if(pnow==0)return 0;
CStudent* pstu=pnow->pstu;
CItem* ptmp=pnow;
if(pnow->pnext==pnow){pnow=0;delete ptmp;return pstu;}
pnow=pnow->pnext;
delete ptmp;
return pstu;
}
void PopNext()
{
CItem* ptmp=pnow->pnext;
pnow->pnext=ptmp->pnext;
delete ptmp;
}
void Shift(int n)
{
for(int i=0;i<n;i++)
{
pnow=pnow->pnext;
}
}
void Check(int n)
{
while(pnow->pnext!=pnow)
{
Shift(n-1);
PopNext();
}
}
void print()
{
CItem* ptmp=pnow->pnext;
ptmp->print();
while(ptmp!=pnow)
{
ptmp=ptmp->pnext;
ptmp->print();
}
}
};
int main()
{
int num=20,interval=4;
cout<<"interval:"<<interval<<endl;
CList* alist=new CList();
for(int i=num;i>0;i--)
{
alist->Push(new CStudent(i));
}
alist->Circle();
cout<<"numbers:";
alist->print();
alist->Check(interval);
cout<<endl<<"result:";
alist->print();
delete alist;
return 0;
}

Answer 2

#include "stdafx.h"
#include "iostream.h"
#include "stdlib.h"
#include "time.h"

const N=100;

void Josphus(int m,int n)
{
int s[N];
int i,j,k,c;
for( i=0;i<n;i++)
s[i]=i+1;
i=0;
while(n>m)
{for (j=1;j<m;j++)
i=i%n+1;
cout<<s[i]<<' ';
for(k=i;k<n-1;k++)
s[k]=s[k+1];
n--;
cin>>c;
}
}

void main()
{
int m,n;
cout<<"输入m,n的值"<<endl;
cin>>m>>n;
Josphus(m,n);
}