今天看了一下josephus问题，突然有点想写些东西的冲动，结合自己的部份思想，于是便写了这几篇帖子。因为有几篇代码有点长，就分开发吧。如果对你有什么帮助的话，本人胜感欣慰。也许你会说，这个问题好多书上都有代码，但本人诣在于用不同的方法写出，让初学者体会一下从面向结构到面向对象的不同之处;同时你也可以看看我写的和一些书中的不同之处。如果你是个大虾，大可一笑了之，或赐教一番。
josephus问题：几个小孩围成一圈，从任意一个小孩间隔m顺时针方向数起，每数到第m个小孩时，该小孩就离开。最后一个剩下的就为胜利者。第几个为胜利者？
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//方法三:结构化方法的实现
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#include <iostream.h>
#include <iomanip.h>
struct Jose
{
int code;
Jose *next;
};
int n;
int begin;
int m;
Jose *pivot,*pCur;
int assign();
void initial(Jose *pJose);
void count(int m);
void process();
void main()
{
if(!assign())
{
cout<<"The program failed."
<<endl;
return;
}
Jose *pJose=new Jose[n];
initial(pJose);
count(begin);
process();
cout<<endl
<<"the winner is:"
<<pCur->code
<<endl;
delete []pJose;
}
int assign()
{
int number,start,count;
cout<<"please input the number,start,count:"
<<endl;
cin>>number>>start>>count;
if(number<3)
{
cerr<<"bad beginning position."
<<endl;
return 0;
}
if(start<1)
{
cerr<<"bad beginning position."
<<endl;
return 0;
}
if(count<2||count>number)
{
cerr<<"bad interval number"
<<endl;
return 0;
}
n=number;
begin=start-1;
m=count;
return 1;
}
void initial(Jose *pJose)
{
int lineCount=0;
Jose *px=pJose;
for(int i=1;i<=n;i++)
{
px->next=pJose+i%n;
px->code=i;
px=px->next;
if((lineCount++%10)==0)
cout<<endl;
cout<<setw(4)<<i;
}
cout<<endl;
pCur=pJose+n-1;
}
void count(int m)
{
for(int i=0;i<m;i++)
{
pivot=pCur;
pCur=pivot->next;
}
}
void process()
{
int l=0;
for(int i=1;i<n;i++)
{
count(m);
if((l++%10)==0)
cout<<endl;
cout<<setw(4)<<pCur->code;
pivot->next=pCur->next;
pCur=pivot;
}
}