今天看了一下josephus问题，突然有点想写些东西的冲动，结合自己的部份思想，于是便写了这几篇帖子。因为有几篇代码有点长，就分开发吧。如果对你有什么帮助的话，本人胜感欣慰。也许你会说，这个问题好多书上都有代码，但本人诣在于用不同的方法写出，让初学者体会一下从面向结构到面向对象的不同之处;同时你也可以看看我写的和一些书中的不同之处。如果你是个大虾，大可一笑了之，或赐教一番。
josephus问题：几个小孩围成一圈，从任意一个小孩间隔m顺时针方向数起，每数到第m个小孩时，该小孩就离开。最后一个剩下的就为胜利者。第几个为胜利者？
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//方法四:面向对象的实现
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//ring.h
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
struct Node
{
int code;
Node *next;
};
class Ring
{
public:
Ring(int n);
~Ring();
void Progress(int m);
void PrintNode();
void ClearCode();
protected:
Node *head;
Node *pivot;
Node *pCur;
};
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//ring.cpp
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#include <iostream.h>
#include <iomanip.h>
#include "ring.h"
Ring::Ring(int n)
{
head = new Node[n];
pCur = head;
for (int i=1; i<=n; i++,pCur=pCur->next)
{
pCur -> code = i;
pCur -> next = head + (i % n);
// PrintNode();//if you want to look the boy who was you input,you can live out "//"
}
cout<<endl;
pCur = &head[n-1];
}
Ring::~Ring()
{
delete []head;
}
void Ring::Progress(int m)
{
for (int i=0; i<m; i++)
{
pivot = pCur;
pCur = pCur -> next;
}
}
void Ring::PrintNode()
{
static int lineCount;
if (((lineCount++) % 10) == 0)
cout<<endl;
cout << setw(4)
<< pCur -> code;
}
void Ring::ClearCode()
{
pivot->next=pCur->next;
pCur=pivot;
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//jose.h
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
class Jose
{
public:
Jose(int boys=10, int begin=1, int m=3);
void Initial();
void GetWinner();
protected:
int numOfBoys;
int beginPos;
int interval;
};
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//Jose.cpp
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#include <iostream.h>
#include "ring.h"
#include "Jose.h"
Jose::Jose(int boys , int begin, int m)
{
if (boys < 1)
{
cout << "Bad number of boys!\n";
return;
}
if (begin < 0)
{
cout << "Bad beginning position!\n";
return;
}
if ((m<1) || (m>boys))
{
cout << "Bad interval number!\n";
return;
}
numOfBoys = boys;
beginPos = begin;
interval = m;
}
void Jose::GetWinner()
{
Ring x(numOfBoys);
x.Progress(beginPos);
for (int i=1; i<numOfBoys; i++)
{
x.Progress(interval);
//x.PrintNode(); //if you want to look the boy who is out,you can live out "//"
x.PrintNode();
x.ClearCode();
}
cout<<"\nThe winner is:";
x.PrintNode();
}
void Jose::Initial()
{
int num,begin,m;
cout<<"Please input the number of boys,Beginning position,innterbal per count"
<<endl;
cin>>num>>begin>>m;
if(num<2)
{
cerr<<"bad number of boys"
<<endl;
return;
}
if(begin<0)
{
cerr<<"bad beginning position."
<<endl;
return;
}
if(m<1||m>num)
{
cerr<<"bda interval number."
<<endl;
}
numOfBoys=num;
beginPos=begin;
interval=m;
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//main.cpp
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#include "Jose.h"
void main()
{
Jose jose;
jose.Initial();
jose.GetWinner();
}
