//一群小孩围成一圈，任意假定一个数m，从第一个小孩起，顺时针方向数，每数到第m个

//小孩时，该小孩便离开。小孩不断离开，圈子不断缩小。最后剩下的小孩便是胜利者.

用面向对象实现:
//-------------------------
//        ringx.h        
//-------------------------
struct Boy
{
    int code;
    Boy * next;
};
class Ring
{
public:
    Ring(int n);
    void Count(int m);
    void PutBoy();
    void ClearBoy();
    void Display();
    ~Ring();
protected:
    Boy * pBegin;
    Boy * pivot;
    Boy * pCurrent;
};

//----------------------
//      ringx.cpp    
//----------------------
#include<iostream.h>
#include<iomanip.h>
#include"ringx.h"
Ring::Ring(int n)
{
    pBegin=new Boy[n];
    pCurrent=pBegin;
    for(int i=1;i<=n;i++,pCurrent=pCurrent->next)
    {
        pCurrent->next=pBegin+i%n;
        pCurrent->code=i;
    }
    Display();
    pCurrent=&pBegin[n-1];
}
void Ring::Count(int m)
{
    for(int i=0;i<m;i++)
    {
        pivot=pCurrent;
        pCurrent=pivot->next;
    }
}
void Ring::PutBoy()
{
    static int numInLine;
    if(numInLine++%10==0)
        cout<<endl;
    cout<<setw(4)<<pCurrent->code;
}
void Ring::ClearBoy()
{
    pivot->next=pCurrent->next;
    pCurrent=pivot;
}
void Ring::Display()
{
    Boy * pB=pCurrent;
    do
    {
        PutBoy();
        pCurrent=pCurrent->next;
    }while(pB!=pCurrent);
    cout<<endl;
}
Ring::~Ring()
{
    delete[]pBegin;
}
//--------------------
//      josex.h
//--------------------
class Jose
{
public:
    Jose(int boys=0,int begin=1,int m=3)
    {
        numOfBoys=boys;
        beginPos=begin;
        interval=m;
    }
    void Initial();
    void GetWinner();
protected:
    int numOfBoys;
    int beginPos;
    int interval;
    int wins;
};
//-------------------
//      josex.cpp
//-------------------
#include<iostream.h>
#include"ringx.h"
#include"josex.h"
void Jose::Initial()
{
    int num,begin,m,w;
    cout<<"Please input the number of boys,\n"
        "begin position,\ninterval per count,\n"
        "number of winners:\n";
    cin>>num>>begin>>m>>w;
    if(num<2)
    {
        cerr<<"bad number of boys\n";
        return;
    }
    if(begin<0)
    {
        cerr<<"bad begin position.\n";
        return;
    }
    if(m<1||m>num)
    {
        cerr<<"bad interval number.\n";
        return;
    }
    if(w<1||w>=num)
    {
        cerr<<"bad number of winners.\n";
        return;
    }
    numOfBoys=num;
    beginPos=begin;
    interval=m;
    wins=w;
}
void Jose::GetWinner()
{
    Ring x(numOfBoys);
    x.Count(beginPos);
    for(int i=1;i<numOfBoys-wins+1;i++)
    {
        x.Count(interval);
        x.PutBoy();
        x.ClearBoy();
    }
    cout<<"\nthe winner(s) is";
    x.Display();
}
//--------------------
//     jose.cpp
//--------------------
#include"josex.h"
int main()
{
    Jose jose;
    jose.Initial();
    jose.GetWinner();
         retuen 0;
}
 -----------------------------------------------------------------

用数组实现：

#include < iostream >
using namespace std;
void main()
{
//建立小孩数组
const int num=10;
int interval;
int a[num];
//给小孩编号
for (int i=0;i < num;i++)
a[i]=i+1;

//输入小孩间隔
cout<<"plaease input the interval:";
cin >>interval;

//out the child
for (int i=0;i < num;i++)
cout << a[i] << ":";
cout << endl;

int k=1; //the child out of the community
int i=-1; //数组下标 （＋1）
while (1)
{ for (int j=0;j < interval;)
{
i=(i+1)%num;
if (a[i]!=0)
j++;
}
if (k==num) break;
cout< a[i]=0;

k++;
}
cout<< "\n NO." << a[i] <<"boy's won" << endl;

}

-------------------------------------------------------------------

用链表实现

#include < iostream >
#include < iomanip >
using namespace std;

struct jose
{
int code;
jose* next;
};

void main()
{
int numofBoys,interval;
cout << "please input the number of boys, \n"
<< " interval of counting:\n" ;
cin >> numofBoys >> interval;

//建立小孩结构数组：构成环链，小孩编号，输出编号

jose* Pjose= new jose[numofBoys]; //从堆内存分配空间
jose* Pcurrent=Pjose;

int itemsInline=0; //输出每10个换行 （后面用到）

for (int i=1;i<=numofBoys;i++)
{
Pcurrent->next=Pjose+i%numofBoys; // i%numofBoys 的妙用
Pcurrent->code=i;
Pcurrent=Pcurrent->next;

if (itemsInline++ %10==0) //输出每10个换行
cout << endl;
cout << setw(4) << i;
}
itemsInline=0;

jose* pivot; //链表哨兵
Pcurrent=&Pjose[numofBoys-1]; //下一个就是Pjose[0]

while (Pcurrent->next != Pcurrent)
{
for (int j=0; j < interval; j++)
{
pivot=Pcurrent;
Pcurrent=pivot->next;
}

if (itemsInline++ % 10==0)
cout << endl;

cout << setw(4) << Pcurrent->code;

pivot->next=Pcurrent->next; //小孩脱链

Pcurrent=pivot;
}

cout << "\n \n the winner is "
<< Pcurrent->code << endl;

delete []Pjose; //释放堆空间
}

评论