很多书在一开始就开始学习josephus问题，为了让大家前面学起来较为容易我把前面涉及到此问题的地方都故意去掉了，现在我们已经学习过了结构体和类，所以放在这里学习可能更合适一些。
在正式开始学习之前我们先回顾一下如何利用数组和结构体的方式来解决，最后我们再看一下如何利用面向对象的抽象理念进行解决此问题的程序设计，相互对比，找出效率最高，最容易理解，最方便维护的程序来，说明利用面向对象的抽象理念进行程序设计的好处。
josephus问题其实就是一个游戏，一群小孩围成一个圈，设置一个数，这个数是个小于小孩总数大于0的一个整数,从第一个小孩开始报数，当其中一个小孩报到你设置的那个数的时候离开那个圈，这样一来反复报下去，直到只剩下最后一个小孩的时候那个小孩就是胜利者，写程序来找出这个小孩。
以下是数组方法:
由于数组的限制我们必须预先假设好有多少个小孩，离开的小孩他自身设置为0来标记离开状态。
代码如下：
#include <iostream>
using namespace std;
void main()
{
const int num=10;
int interval;
int a[num];
for(int i=0; i<num; i++)
{
a[i]=i+1;
}
cout <<"please input the interval: ";
cin >>interval;
for(int i=0; i<num; i++)
{
cout <<a[i] <<",";
}
cout <<endl;
int k=1;
int p=-1;
while(1)
{
for(int j=0;j<interval;)
{
p=(p+1)%num;
if(a[p]!=0)
{
j++;
}
}
if(k==num)
{
break;
}
cout<<a[p]<<",";
a[p]=0;
k++;
}
cout <<"\nNo." <<a[p] <<" boy''ve won.\n";
cin.get();
cin.get();
}
就数组解决来看,程序简短但效率不高可读性也不好，此代码没有什么特别之处主要依靠一个加1取模的方式来回到首位置，形成环链:p=(p+1)%num;。
以下是利用结构体的方法解决josephus问题：
当我们学过结构体后，我们了解到结构体自身的成员指针可以指向自身对象的地址的时候，我们很容易想到解决这个数学问题，用结构体来描述是再合适不过的了，用它可以很完美的描述环形链表。
代码如下：
#include <iostream>
#include <string>
using namespace std;
struct Children
{
int number;
Children *next;
};
void show(Children *point,int num)//环链输出函数
{
for(int i=1;i<=num;i++)
{
cout<<point->number<<",";
point = point->next;
}
}
void main()
{
int num;//孩子总数
int interval;//抽选号码
cout<<"请输入孩子总数:";
cin>>num;
cout<<"请输入抽选号码:";
cin>>interval;
Children *josephus = new Children[num];//设置圈的起点指针,并动态开辟堆空间用于存储数据
Children *point = josephus;//用于初化链表的指针,起始地址与josephus指针相同
for(int i=1;i<=num;i++)
{
point -> number = i;
point -> next = josephus + i % num;//利用+1取模的方式设置节点的next指针,当到最后的时候自动指向到第一个,形成环链
point = point->next;//将位置移到下一饿节点也就是下一个小孩的位置
}
show(point,num);
Children *cut_point;
point=&josephus[num-1];//把起始指针设置在最后一个节点,当进入循环的时候就会从0开始,这样就好让不需要的节点脱离
int k=0;//故意设置一个k观察while循环了多少次
while(point->next!=point)//通过循环不 |
