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

2019-11-17 05:06:13

字體：大中小

供稿：網(wǎng)友

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

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

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

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

　　代碼如下:

　C++ 代碼
//程序作者:管寧
//所有稿件均有版權(quán),如要轉(zhuǎn)載,請(qǐng)務(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ù)組解決來(lái)看,程序簡(jiǎn)短但效率不高可讀性也不好，此代碼沒(méi)有什么非凡之處主要依靠一個(gè)加1取模的方式往返到首位置，形成環(huán)鏈:p=(p+1)%num;。