打印本文 打印本文  关闭窗口 关闭窗口  
Josephus问题的C++新解法
作者：佚名  文章来源：不详  点击数  更新时间：2008/4/18 14:41:04  文章录入：杜斌  责任编辑：杜斌
Josephus.h
class Josephus 
{ 
public:
void OutControl(int num,int begin,int interval); 
protected:
int num; 
int begin;
int interval; 
}; 

List.h
struct People 
{ 
int number; 
People *next; 
}; 


class List
{ 
public: 
List (int num)//初始化point->number
{ 
josephus = new People[num]; 
point = josephus; 
for(int i=1;i<=num;i++) 
{ 
point->number = i ; 
point->next = josephus + i % num; /*利用+1取模的方式设置节点的next指针,
当到最后的时候自动指向到第一个,形成环链 */
point = point->next; 
} 
point = &josephus[num-1]; //把起始指针设置在最后一个节点,当进入循环的时候就会从0开始,
}

~List() 
{ 
delete[] josephus; //返回堆内存空间
}

void Change (int num, int begin);
void Count(int interval); 
void Output(); 
void Show();

protected: 
People *josephus; 
People *point; 
People *cut_point; 
}; 


Josephus.cpp
#include <iostream> 
#include "Josephus.h" 
#include "List.h" 
using namespace std; 

void Josephus::OutControl(int num,int begin,int interval) //调用List的成员函数,依次输出出列的号码
{ 
List in(num); 
in.Change (num, begin);

cout<<"依次出列次序为:";
for(int i=1;i<=num;i++) 
{ 
in.Count(interval);
in.Show(); 
in.Output(); 
}
cout<<endl;
} 

List.cpp
#include <iostream> 
#include "List.h" 
using namespace std;


void List::Change (int num, int begin) //设置起始指针的位置
{ 
if (begin==1) 
point=&josephus[num-1]; 
if (begin>=2)
point=&josephus[begin-2];
}

void List::Count(int interval) //通过循环不断的寻找需要放弃的节点
{ 
for(int i=0;i<interval;i++) 
{
cut_point = point; 
point = cut_point->next; 
} 
} 

void List::Show() //打印号码
{ 
cout<<point->number<<"."; 
} 

void List::Output() //使不需要的节点脱离
{ 
cut_point->next = point->next; 
point=cut_point; 
} 


main.cpp
#include <iostream> 
#include "Josephus.h" 
using namespace std; 

void main() 
{ int num,begin,interval; 

cout<<"请输入总人数:"; 
cin>>num; 
if(num<2)
{ 
cout<<"错误!总人数不能小于2!"; 
return; 
} 

cout<<"请输入开始号码:";
cin>>begin;
if(begin<1||begin>num)
{
cout<<"错误!开始号码不能小于1或大于总人数!";
return;
}

cout<<"请输入间隔:"; 
cin>>interval; 
if(interval<1||interval>num) 
{ 
cout<<"错误!间隔不能小于1或大于总人数!"; 
return; 
} 

Josephus in; 
in.OutControl(num,begin,interval);
cin.get ();
cin.get ();
}
打印本文 打印本文  关闭窗口 关闭窗口