用户数组解决约瑟夫问题.txt

用数组解决约瑟夫问题的源程序 【约瑟夫问题】 编号为1

用数组解决约瑟夫问题的源程序
附件中是使用数组解决约瑟夫问题的源程序。希望大家好好研究一下。思考这样几个问题：     
(1)为什么定义一个抽象类？    
(2)函数NextPeople()为什么是私有的？  
(3)函数NextPeople()中有没有出现死循环的风险？

===================================================================

#include <iostream>
using namespace std;

class Joseph{
protected:
 int number_of_people;
 int step;
public:
 virtual void CreateOutput()=0;
 Joseph(int n,int m){
  number_of_people=n;
  step=m;
 }
};

class JosephWithArray:public Joseph{
 int *WorkingArray;
 int NextPeople(int prev);
public:
 JosephWithArray(int n,int m);
 void CreateOutput();
 ~JosephWithArray(){delete[] WorkingArray;}
};

JosephWithArray::JosephWithArray(int n,int m):Joseph(n,m){
 WorkingArray = new int[n];
 for(int i=0;i<n;i++)
  WorkingArray[i]=i+1;
}

void JosephWithArray::CreateOutput(){
    int i;
 int outnum=-1;
 for(i=0;i<number_of_people;i++){
  outnum = NextPeople(outnum);
  cout << WorkingArray[outnum] << " ";
  WorkingArray[outnum]=0;
 }
 cout << endl;
}

int JosephWithArray::NextPeople(int prev){
 int count=0;
 int travel=prev;
 while(count<step){
  travel=(travel+1)%number_of_people;
  if(WorkingArray[travel])
   count++;
 }
 return travel;
}

int main(){
 int n,m;
 cout << "please input number of people:";
 cin >> n;
 cout << "please input step:";
 cin >> m;
 JosephWithArray obj(n,m);
 obj.CreateOutput();
 getchar();
 getchar();
}