从面向结构到面向对象-----josephus扩展问题（二）

今天看了一下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;
  }
}

本文地址：http://com.8s8s.com/it/it23758.htm