數據結構常見問題：12單元28 敢死隊問題

《數據結構》課程常見問題

一一單元28敢死隊問題

i.敢死隊問題求解

解析：

問題描述

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

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

隨便從某一個戰(zhàn)士開始計數，當數到5時，對應的戰(zhàn)士就去執(zhí)行任務，且此戰(zhàn)士不再參加下一輪計數。如

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

到任務完成為止。

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

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

要求：至少采用兩種不同的數據結構的方法實現。

一、單循環(huán)鏈表數據結構

（-）需求分析

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

初始位置。首先輸入隊伍人數n,然后輸入報數上限m（m〈=n）,從1號開始報數，當達到報數上限時，那名

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

視為排長位置，則1號即可視為最先報數的人，通過數學計算即可獲得所求。

2.功能模塊和流程：

1）功能模塊

該程序功能比較單一，主要是為解決敢死隊問題而設計。通過輸入隊伍人數和報數上限即可獲得

開始報數的位置。

2）程序流程

（1）構造鏈表（2）數據輸入（3）執(zhí)行刪除（4）輸出要求數值（5）結束

3.數據測試：

當n=10,m=5,輸出結果為：要求的位置是：9。

（二）詳細設計

1.算法設計：

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

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

置即位所有的開始報數的位置Z。則z=n-k+2?

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

(1)主程序模塊

(2)構造鏈表并初始化

(3)刪除結點

3.結點類型和指針類型

typedefstructnode

(

intdata;

structnode*next;

}LNode;/*定義結點類型*/

LNode*p;

4.每個模塊的分析

(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);

}/*通過數學思想求得實驗要求情況下的數值*/

(2)構造單循環(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;/*生成第一個結點并使其data值為1*/

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

(

s=(LNode*)malloc(sizeof(LNode));/*自動生成結點*/

q->next=s;

口-〉1^*58@1。=:1;/*給第i個結點賦值i*/

q=q->next;

)

q->next=t;

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

returnt;

)

(3)刪除結點模塊：

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

(

LNode*a;inti;

while(t->next!=t)

(

for(i=l;i<m-l;i++)/*查找要刪除結點的前一結點*/

t=t->next;

a=t->next;

t->next=a->next;

free(a);/*釋放結點*/

t=t->next;

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

printf(〃\n〃)；

return(t->data);

)

(三)調試分析：

1.本程序運行后的結果應是如下提示：

Exitpleaseinput'O'OrGoon

Pleaseinputthetataloftheteam:

輸入隊伍總人數

Pleaseinputtheexcursion:

輸入間隔人數

結果顯示：Thewantedpositionis

選擇的位置

2.在程序調試