首頁猿問 C++鏈表開發(fā)問題

C++鏈表開發(fā)問題

JavaScript

尚方寶劍之說 2019-04-19 16:11:35

#includeusingnamespacestd;structchild{intnum;child*link;};;voidinit(intn);;voidgameStart(intn,intm);child*head;child*present;child*end;;intmain(){intn,m;coutn;coutm;init(n);gameStart(n,m);coutlink;deletepresent;present=pGuard->link;n--;}}這是個約瑟夫環(huán)問題我想問下present->link=head;end=present;present=head;具體什么意思貌似是將首尾相連形成循環(huán)鏈表吧。。請詳細解釋下。。謝謝！求解。。

查看完整描述

2 回答

嚕嚕噠

TA貢獻1784條經(jīng)驗獲得超7個贊

@洃c小強大半夜的看到這道題目，我來補充一下吧。約瑟夫環(huán)的問題是說，有編號為1..n的n個犯人圍坐成一圈報數(shù)，報數(shù)為m的犯人出列被kill掉，然后剛才出列犯人的下一位從1開始報數(shù)，以此類推，最終只剩一個人為止。并報告此人的編號g(n,m)。這是計算機算法的一道經(jīng)典題目。常規(guī)的解法是根據(jù)題目進行建模。其中structchild{intnum;child*link;};是犯人的模型，每個犯人有一個編號num，同時有下一個編號犯人的指針link，這樣，能夠建立一個單向鏈表。但是，約瑟夫環(huán)是首尾循環(huán)的，所以，需要present->link=head;來將單向鏈表變成環(huán)鏈表。完成模型建構(gòu)以后，需要指定開始和結(jié)束的位置end=present;present=head;就是用來完成這一功能的。之后的gameStart就是完成根據(jù)條件刪除鏈表節(jié)點的功能。除去約瑟夫環(huán)的背景，其實，這段程序的基本功能只有兩個：1.構(gòu)建環(huán)鏈表；2.根據(jù)條件刪除環(huán)鏈表節(jié)點；這樣程序就容易理解多了。^-^另外，題目中的解法是利用模擬的辦法來解決約瑟夫環(huán)的問題的。其實，在數(shù)學(xué)上，關(guān)于約瑟夫環(huán)g(n,m)=?是有直接答案的。g(n,m)=(g(n–1)+m)%n,(n>1)用Python寫出的代碼如下：defjosephus(n,m):j=0foriinrange(2,n+1):j=(j+m)%iprintj+1大概就是這些吧。

反對回復(fù) 2019-04-19

萬千封印

TA貢獻1891條經(jīng)驗獲得超3個贊

我沒仔細看也不懂約瑟夫環(huán)也不會c++.不過看樣子是present->link=head;end=present;present=head;這三句話的意圖是重置present與present的link還有end指針使之都指向鏈表頭而已,也就是說這時候約瑟夫環(huán)已經(jīng)構(gòu)建完畢,可以把指針都設(shè)置為鏈表初始值以待后用了,再看看函數(shù)名為init,我想我的推測完全沒錯

反對回復(fù) 2019-04-19