今天看了一下josephus问题，突然有点想写些东西的冲动，结合自己的部份思想，于是便写了这几篇帖子。因为有几篇代码有点长，就分开发吧。如果对你有什么帮助的话，本人胜感欣慰。也许你会说，这个问题好多书上都有代码，但本人诣在于用不同的方法写出，让初学者体会一下从面向结构到面向对象的不同之处;同时你也可以看看我写的和一些书中的不同之处。如果你是个大虾，大可一笑了之，或赐教一番。
josephus扩展问题（二）:一群小孩围成一个圈，间隔m个数顺时针方向计数，若要第win个小孩胜利，要从哪个小孩数起？
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//ring.h
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
struct Node
{
int code;
Node *next;
};
class Ring
{
public:
Ring(int n);
~Ring();
void Progress(int m);
void PrintNode();
int GetCode();
void DeleteNode();
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;
}
int Ring::GetCode()
{
return pCur -> code;
}
void Ring::DeleteNode()
{
pivot -> next = pCur ->next;
pCur = pivot;
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//jose.h
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
class Jose
{
public:
Jose(int boys, int begin, int m);
Jose();
int 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;
}
Jose::Jose()
{
int boys,begin,m;
cout << "Please input the number of boys.Then input the number which you want to begin count.The thirth number is interval per count: \n";
cin >> boys >> begin >> m;
if (boys < 1)
{
cout << "Bad number of boys!May be,the number is too small!\n";
return;
}
if (begin < 0)
{
cout << "The value of the begain number must more than 1.\n";
return;
}
if ((m<1) || (m>boys))
{
cout << "Interval number is between 1 and number of boys";
return;
}
numOfBoys = boys;
beginPos = begin;
interval = m;
}
int Jose::GetWinner()
{
Ring x(numOfBoys);
x.Progress(beginPos-1);
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.DeleteNode();
}
return x.GetCode();
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//start.cpp
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#include "Jose.h"
int start(int num, int winner, int interval)
{
Jose j(num,1,interval);
return (num+(1+(winner-j.GetWinner()))%num);
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//main.cpp
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#include <iostream.h>
#include "Jose.h"
int start(int num, int winner, int interval);
main()
{
int num,win,inte,i;
cout << "Please input three numbers.The frist number is count childen;The second number is the number which you want to win;And third number is interval number."
<<endl;
cin >> num >> win >>inte;
i=start(num, win, inte);
cout <<endl
<< "We must start count from number"
<< i
<<"!"
<<endl<<endl<<endl;
cout <<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"
<<endl
<<"Please input (Y)if you want to chack you answer;Else put (N):";
while(1)
{
char chack;
cin>>chack;
if(chack=='Y'||chack=='y')
{
Jose jose;
cout << "\nThe winner is " << jose.GetWinner();
break;
}
else if(chack=='N'||chack=='n')
break;
}
}
