利用C解決約瑟夫問(wèn)題。

發(fā)布時(shí)間：2025-11-23 | 來(lái)源：互聯(lián)網(wǎng)轉(zhuǎn)載和整理

這里補(bǔ)充一下約瑟夫問(wèn)題的描述：N個(gè)人圍成一圈，從第一個(gè)開(kāi)始報(bào)數(shù)，數(shù)到M的人出隊(duì)，然后他的下一位繼續(xù)從1開(kāi)始報(bào)數(shù)，數(shù)到M的出隊(duì)，如此循環(huán)直到剩下一個(gè)人，求最后剩下的那個(gè)人最初是隊(duì)伍中的第幾位。

解決這道題可以采用模擬報(bào)數(shù)的方法，建立一個(gè)大小為N的數(shù)組，數(shù)組的第N個(gè)元素表示第N個(gè)人是否還在隊(duì)伍中，首先將每個(gè)元素都置為1，表示全員都在隊(duì)伍中。如果第N個(gè)人出隊(duì)，則將第N個(gè)元素置為0。

模擬報(bào)數(shù)可以使用一個(gè)累加計(jì)數(shù)器，用它表示這輪報(bào)數(shù)已有多少人報(bào)數(shù)，然后循環(huán)訪問(wèn)每個(gè)人，若其在隊(duì)伍中，則將計(jì)數(shù)器+1，如果累加到M，則這個(gè)人出隊(duì)。如此循環(huán)直到N-1個(gè)人出隊(duì)，僅剩1人。

最后遍歷一下那個(gè)數(shù)組，找到還在隊(duì)伍中的人就可以。

代碼如下：

#includeusingnamespacestd;intmain(){intm,n,i,s=0,rem;//s為計(jì)數(shù)器,rem為剩余人數(shù)int*a;cout>n>>m;rem=n;a=newint[n];for(i=0;i1){s+=a[i];if(s==m)//第i個(gè)人出隊(duì)，重置累加計(jì)數(shù)器{s=0;rem--;a[i]=0;}i++;i%=n;}for(i=0;i<n;i++)if(a[i]){cout<<剩下的人為：<<i<<endl;break;}ｄｅｌｅｔｅ[]a;return0;}