很多書在一開始就開始學習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)//通過循環不斷的尋找需要放棄的節點
{
k++;
for(int i = 0;i<interval;i++)//找需要放棄的節點位置
{
cut_point=point;//存儲截斷位置指針
point=cut_point->next;//將point的指針移動到放棄的節點位置,此處也和while循環終止條件有關系
}
cut_point->next=point->next;//將截斷出的next指針設置成放棄處節點的next指針,使放棄處節點也就是不需要的節點脫離
cout<<"k:"<<k<<endl;
}
cout<<"\n最後的贏家:"<<endl<<point->number<<endl<<point<<endl<<point->next<<endl;
delete[] josephus;
cin.get();
cin.get();
}
此代碼較為難以理解的部分就是while循環的終止條件的設置，如果讀者沒有能夠理解好這部分注意看下面的圖式幫助學習。
結構體的解法非常重要，對於我們全面理解面向對象的程序設計的抽象問題是基礎，必須看明白我們才能夠進行後面知識的學習,務必認真對待。
這段代碼比較前一個程序，可讀性上有所加強，但仍然不太容易理解！
為了更容易學習便於理解，我們的圖例是以有兩個小孩圍成一圈，並且設置報數的數為1的情況來制作的。
上面的兩種解決Josephus問題的解決辦法從代碼上來看，都屬於一桿子到底的解法，第二種從結構表達上優於第一種，但是這兩個都屬於純粹的過程式程序設計，程序雖然簡短,但很難讓人看懂，程序的可讀性不高，在我們沒有學習面向對象的編程之前，聰明的人可能會把各各步驟分解出來做成由幾個函數來解決問題。
思路大致可以分為以下六個部分：
1.建立結構
2.初始化小孩總數,和數小孩的數
3.初始化鏈表並構成環鏈
4.開始通過循環數小孩獲得得勝者
5.輸出得勝者
6.返回堆內存空間
從表上看這個程序為了便於閱讀可以寫成六個函數來分別處理這六個過程，的確，這麼修改過後程序的可讀性是提高了一大步，但是有缺點仍然存在，程序完全暴露在外，任何人都可以修改程序，程序中的一些程序作者不希望使用者能夠修改的對象暴露在外，各對象得不到任何的保護，不能保證程序在運行中不被意外修改，對於使用者來說還是需要具備解決Josephus問題算法的能力，一旦程序變的越來越很，,每一個參與開發的程序員都需要通讀程序的所有部分，程序完全不具備黑盒效應，給多人的協作開發帶來了很大的麻煩，幾乎每個人都做了同樣的重復勞動，這種為了解決一個分枝小問題寫一個函數，最後由很多個解決局部問題的函數組合成的程序我們叫做結構化程序設計，結構化編程較過程化編程相比可讀性是提高了，但程序不能輕易的被分割解決一個個大問題的模塊，在主函數中使用他們的時候總是這個函數調用到那個函數，如果你並不是這些函數的作者就很難正確方便的使用這些函數，而且程序的變量重名問題帶來的困擾也是很讓人頭痛的……
那麼面向對象的程序設計又是如何解決這些問題的呢？
面向對象的程序設計的思路是這樣的：
程序 = 對象 + 對象 +對象..........
這麼組合而來的
對於上面的josephus問題可以把問題分割成如下的方法進行設計(如下圖所示)
由上圖可以看出：
面向對象的程序設計是由類組合而成的，有類必然有類的對象，程序之間的交互主要是通過對象與對象之間的關系進行操作的。
由於我們把josephus問題分解成了josephus類和ring類，在主函數中，用戶只需要使用josephus類設計其對象明確知道Josephus類的外部接口函數也就是操作該對象的方法initial()就可以了，至於josephus的內部實現又是如何與Ring類進行操作的使用者一概不需要知道，只要拿來用知道接口和接口函數是什麼就可以了，這樣的程序設計很好的保護了各類成員數據的安全，主函數代碼調用極其簡單只有建立對象和調用對象方法的操作這兩部而已，以後類一旦需要修改，只修改類體本身就可以，而主函數不需要做任何修改，這樣就很好的做到了什麼人做的事情什麼人處理互不沖突。
程序的代碼如下，我把工程文件壓縮了作為此帖的附件提供下載，希望讀者仔細閱讀仔細推敲，真正理解面向對象oop編程的特點和意圖。
主程序test4.cpp
#include <iostream>
#include "josephus.h"
using namespace std;
void main()
{
Josephus a;
a.initial();
cin.get();
cin.get();
}
josephus.h
class Josephus
{
public:
Josephus(int num=10,int interval=1)
{
Josephus::num=num;
Josephus::interval=interval;
}
void initial();
protected:
int num;
int interval;
};
josephus.cpp
#include <iostream>
#include "josephus.h"
#include "ring.h"
using namespace std;
void Josephus::initial()
{
int num,interval;
cout<<"請輸入孩子總數:";
cin>>num;
if(num<2)
{
cout<<"孩子總數不能小於2,否則不能構成環鏈!";
return;
}
cout<<"請輸入抽選號碼";
cin>>interval;
if(interval<1|interval>num)
{
cout<<"請輸入抽選號碼不能小於1或者大於小孩總數!";
return;
}
Josephus::num=num;
Josephus::interval=interval;
Ring a(num);
a.ShowRing(num);
cout<<endl;
for(int i=1;i<num;i++)
{
a.CountInterval(interval);
a.ShowWiner_loser();
a.OutChild();
}
cout<<endl<<"勝利者是:";
a.ShowWiner_loser();
}
ring.h
struct Children
{
int number;
Children *next;
};
class Ring
{
public:
Ring(int num)
{
josephus = new Children[num];
point = josephus;
for(int i=1;i<=num;i++)
{
point->number = i;
point->next = josephus + i % num;
point=point->next;
}
point = &josephus[num-1];
}
~Ring()
{
delete[] josephus;
}
void ShowRing(int num);
void CountInterval(int interval);
void OutChild();
void ShowWiner_loser();
protected:
Children *josephus;
Children *point;
Children *cut_point;
};
ring.cpp
#include <iostream>
#include "ring.h"
using namespace std;
void Ring::ShowRing(int num)
{
point=josephus;//也可以寫成point=point->next;但前著效率高一點點
for(int i=1;i<=num;i++)
{
cout<<point->number<<",";
point=point->next;
}
point=&josephus[num-1];//輸出過後恢復point應該在的位置
}
void Ring::CountInterval(int interval)//數小孩
{
for(int i=0;i<interval;i++)
{
cut_point = point;
point = cut_point->next;
}
}
void Ring::OutChild()
{
cut_point->next = point->next;//將不要節點斷離
point=cut_point;
}
void Ring::ShowWiner_loser()
{
cout<<point->number<<",";
}
程序中需要注意的小地方是在這裡
class Josephus
{
public:
Josephus(int num=10,int interval=1)
{
Josephus::num=num;
Josephus::interval=interval;
}
void initial();
protected:
int num;
int interval;
};
代碼中的
Josephus::num=num;
Josephus::interval=interval;
使用域區分符的目的就是為了區分成員變量和局部變量Josephus(int num=10,int interval=1)
相信讀者認真讀完程序認真理解後應該就可以理解面向對象程序設計的用意和好處了，切記認真推敲！
大家看到面向對象程序設計的解決辦法，可能覺得它的代碼太多了，會懷疑它執行的效率是否足夠好，呵呵！
這裡只能這麼說，程序的效率不是單單看程序的長短來看的，優秀的程序應該是便於維護，關系清楚的，面向對象的程序設計其實和過程式或者是結構化程序設計的思路是不沖突的，在不同的地方使用不同的方法，優勢互補才是正道！
