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

今天看了一下josephus问题，突然有点想写些东西的冲动，结合自己的部份思想，于是便写了这几篇帖子。因为有几篇代码有点长，就分开发吧。如果对你有什么帮助的话，本人胜感欣慰。也许你会说，这个问题好多书上都有代码，但本人诣在于用不同的方法写出，让初学者体会一下从面向结构到面向对象的不同之处;同时你也可以看看我写的和一些书中的不同之处。如果你是个大虾，大可一笑了之，或赐教一番。

 josephus扩展问题（一）:一群小孩围成一个圈，间隔m个数顺时针方向计数，从第一个小孩数起，求一个和几个获胜者。

 

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//ring.h
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
struct Node
{
  int code;
  Node *next;
};

class Ring
{
  public:
    Ring(int n);
    ~Ring();
    void Progress(int m);
    void PrintNode();
    void ClearCode();
    void Display();
  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 "//"
  }

  Display();
  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;

}

void Ring::Display()
{
  Node *pB=pCur;
 
  do{
    PrintNode();
    pCur=pCur->next;
  }while(pB!=pCur);
  
  cout<<endl;

}

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//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;
    int wins;
};

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//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-wins+1; 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.Display();
}

void Jose::Initial()
{
  int num,begin,m,w;
  cout<<"Please input the number of boys:"
      <<endl
      <<"Beginning position,\n innterbal per count"
      <<endl
      <<"number of winners:"
      <<endl;
  cin>>num>>begin>>m>>w;

  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;
  }

  if(w<1||w>=num)
  {
    cerr<<"bad number of winners.";
    return;
  }

  numOfBoys=num;
  beginPos=begin;
  interval=m;
  wins=w;
}

 

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//main.cpp
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

#include "Jose.h"

void main()
{
  Jose jose;
  jose.Initial();
  jose.GetWinner();
}
 
 

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