从面向结构到面向对象-----josephus问题(方法四:面向对象的实现)

类别:编程语言 点击:0 评论:0 推荐:

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

 

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