數(shù)據(jù)結(jié)構(gòu)常見問題：12單元28 敢死隊(duì)問題

《數(shù)據(jù)結(jié)構(gòu)》課程常見問題

一一單元28敢死隊(duì)問題

i.敢死隊(duì)問題求解

解析：

問題描述

有M個(gè)敢死隊(duì)員要炸掉敵人的一碉堡，誰都不想去，排長決定用輪回?cái)?shù)數(shù)的辦法來決定哪個(gè)戰(zhàn)士去執(zhí)

行任務(wù)。如果前一個(gè)戰(zhàn)士沒完成任務(wù)，則要再派一個(gè)戰(zhàn)士上去?，F(xiàn)給每個(gè)戰(zhàn)士編一個(gè)號，大家圍坐成一圈，

隨便從某一個(gè)戰(zhàn)士開始計(jì)數(shù)，當(dāng)數(shù)到5時(shí)，對應(yīng)的戰(zhàn)士就去執(zhí)行任務(wù)，且此戰(zhàn)士不再參加下一輪計(jì)數(shù)。如

果此戰(zhàn)士沒完成任務(wù)，再從下一個(gè)戰(zhàn)士開始數(shù)數(shù)，被數(shù)到第5時(shí)，此戰(zhàn)士接著去執(zhí)行任務(wù)。以此類推，直

到任務(wù)完成為止。

排長是不愿意去的，假設(shè)排長為1號，請你設(shè)計(jì)一程序，求出從第幾號戰(zhàn)士開始計(jì)數(shù)才能讓排長最后

一個(gè)留下來而不去執(zhí)行任務(wù)。

要求：至少采用兩種不同的數(shù)據(jù)結(jié)構(gòu)的方法實(shí)現(xiàn)。

一、單循環(huán)鏈表數(shù)據(jù)結(jié)構(gòu)

（-）需求分析

1,本程序任務(wù)是通過輸入任意隊(duì)伍人數(shù)n和報(bào)數(shù)上限m,輸出使排長最后一個(gè)執(zhí)行任務(wù)而開始記數(shù)的

初始位置。首先輸入隊(duì)伍人數(shù)n,然后輸入報(bào)數(shù)上限m（m〈=n）,從1號開始報(bào)數(shù)，當(dāng)達(dá)到報(bào)數(shù)上限時(shí)，那名

士兵出列執(zhí)行任務(wù)，從下個(gè)人開始記數(shù)，再次循環(huán)，直到只剩一人，得到其在隊(duì)伍中的位置，記下該位置

視為排長位置，則1號即可視為最先報(bào)數(shù)的人，通過數(shù)學(xué)計(jì)算即可獲得所求。

2.功能模塊和流程：

1）功能模塊

該程序功能比較單一，主要是為解決敢死隊(duì)問題而設(shè)計(jì)。通過輸入隊(duì)伍人數(shù)和報(bào)數(shù)上限即可獲得

開始報(bào)數(shù)的位置。

2）程序流程

（1）構(gòu)造鏈表（2）數(shù)據(jù)輸入（3）執(zhí)行刪除（4）輸出要求數(shù)值（5）結(jié)束

3.數(shù)據(jù)測試：

當(dāng)n=10,m=5,輸出結(jié)果為：要求的位置是：9。

（二）詳細(xì)設(shè)計(jì)

1.算法設(shè)計(jì)：

本程序其實(shí)質(zhì)是約瑟夫環(huán)問題。從排長位置即1號開始報(bào)數(shù)，共有n個(gè)人，達(dá)到報(bào)數(shù)上限m=5的戰(zhàn)士

出列，繼續(xù)進(jìn)行報(bào)數(shù)，直到剩余最后一人，記下該位置為k。若將該位置視為排長位置，則原先的1號位

置即位所有的開始報(bào)數(shù)的位置Z。則z=n-k+2?

2.以單循環(huán)鏈表為存儲結(jié)構(gòu)，包含三個(gè)模塊：

(1)主程序模塊

(2)構(gòu)造鏈表并初始化

(3)刪除結(jié)點(diǎn)

3.結(jié)點(diǎn)類型和指針類型

typedefstructnode

(

intdata;

structnode*next;

}LNode;/*定義結(jié)點(diǎn)類型*/

LNode*p;

4.每個(gè)模塊的分析

(1)主程序模塊：

main()

(

LNode*p;

intm,n,z,y;

do

(

printfCPleaseinputthepeoplenumber:\n，z);

scanf&n);

)

while(n<=0);

do

(

printf(，zPleaseinputtheexcursion:、、)；

scanf&m);

)

while(m<=0);

if(n=l)

printf(，zthepositionis:1〃)；

else

(

p=CREAT(n);

y=DELETE(p,m);

z=n-y+2;

if(z%n==0)/*排除特殊情況*/

printf("thepositionis:\n%d\n〃，z);

else

printf(，zthepositionis:\n%d\nz，,(n-y+2)%n);

}/*通過數(shù)學(xué)思想求得實(shí)驗(yàn)要求情況下的數(shù)值*/

(2)構(gòu)造單循環(huán)鏈表并初始化模塊：

LNode*GREAT(intn)/*創(chuàng)建循環(huán)鏈表*/

(

LNode*s,*q,*t;

inti;

if(n!=0)

(

t=q=(LNode*)malloc(sizeof(LNode));

q->data=l;/*生成第一個(gè)結(jié)點(diǎn)并使其data值為1*/

for(i=2;i<=n;i++)

(

s=(LNode*)malloc(sizeof(LNode));/*自動生成結(jié)點(diǎn)*/

q->next=s;

口-〉1^*58@1。=:1;/*給第i個(gè)結(jié)點(diǎn)賦值i*/

q=q->next;

)

q->next=t;

}/*生成后續(xù)結(jié)點(diǎn)，并使其data值即為它所在鏈表(隊(duì)伍)中的位置*/

returnt;

)

(3)刪除結(jié)點(diǎn)模塊：

DELETE(LNode*t,intm)/*鏈表的刪除*/

(

LNode*a;inti;

while(t->next!=t)

(

for(i=l;i<m-l;i++)/*查找要?jiǎng)h除結(jié)點(diǎn)的前一結(jié)點(diǎn)*/

t=t->next;

a=t->next;

t->next=a->next;

free(a);/*釋放結(jié)點(diǎn)*/

t=t->next;

}/*while循環(huán)依次刪除被點(diǎn)到的士兵*/

printf(〃\n〃)；

return(t->data);

)

(三)調(diào)試分析：

1.本程序運(yùn)行后的結(jié)果應(yīng)是如下提示：

Exitpleaseinput'O'OrGoon

Pleaseinputthetataloftheteam:

輸入隊(duì)伍總?cè)藬?shù)

Pleaseinputtheexcursion:

輸入間隔人數(shù)

結(jié)果顯示：Thewantedpositionis

選擇的位置

2.在程序調(diào)試