理解C++程序設(shè)計中的抽象理論

2019-11-17 05:06:13

字體：大中小

供稿：網(wǎng)友

josephus問題是c++中的一個經(jīng)典題目，在正式開始學(xué)習(xí)之前我們先回顧一下如何利用數(shù)組和結(jié)構(gòu)體來解決josephus問題，最后我們再看一下如何利用面向?qū)ο蟮某橄罄砟钸M(jìn)行解決此問題的程序設(shè)計，相互對比，找出效率最高，最輕易理解，最方便維護(hù)的程序來，說明利用面向?qū)ο蟮某橄罄砟钸M(jìn)行程序設(shè)計的好處。

　　josephus問題其實(shí)就是一個游戲，一群小孩圍成一個圈，設(shè)置一個數(shù)，這個數(shù)是個小于小孩總數(shù)大于0的一個整數(shù),從第一個小孩開始報數(shù)，當(dāng)其中一個小孩報到你設(shè)置的那個數(shù)的時候離開那個圈，這樣一來反復(fù)報下去，直到只剩下最后一個小孩的時候那個小孩就是勝利者，寫程序來找出這個小孩。

　　以下是數(shù)組方法:

　　由于數(shù)組的限制我們必須預(yù)先假設(shè)好有多少個小孩，離開的小孩他自身設(shè)置為0來標(biāo)記離開狀態(tài)。

　　代碼如下:

　C++ 代碼
//程序作者:管寧
//所有稿件均有版權(quán),如要轉(zhuǎn)載,請務(wù)必聞名出處和作者

#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();
}

　　就數(shù)組解決來看,程序簡短但效率不高可讀性也不好，此代碼沒有什么非凡之處主要依靠一個加1取模的方式往返到首位置，形成環(huán)鏈:p=(p+1)%num;。