首頁猿問 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--;}}這是個(gè)約瑟夫環(huán)問題我想問下present->link=head;end=present;present=head;具體什么意思貌似是將首尾相連形成循環(huán)鏈表吧。。請(qǐng)?jiān)敿?xì)解釋下。。謝謝！求解。。

查看完整描述

2 回答

嚕嚕噠

TA貢獻(xiàn)1784條經(jīng)驗(yàn) 獲得超7個(gè)贊

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

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

萬千封印

TA貢獻(xiàn)1891條經(jīng)驗(yàn) 獲得超3個(gè)贊

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

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