《數(shù)據(jù)結(jié)構(gòu)常見問題：12單元28 敢死隊(duì)問題》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)常見問題：12單元28 敢死隊(duì)問題（4頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。
1、
《數(shù)據(jù)結(jié)構(gòu)》課程常見問題
----單元28 敢死隊(duì)問題
1．敢死隊(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è)號(hào)，大家圍坐成一圈，隨便從某一個(gè)戰(zhàn)士開始計(jì)數(shù)，當(dāng)數(shù)到5時(shí)，對(duì)應(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è)排長為
2、1號(hào)，請你設(shè)計(jì)一程序，求出從第幾號(hào)戰(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號(hào)開始報(bào)數(shù)，當(dāng)達(dá)到報(bào)數(shù)上限時(shí)，那名士兵出列執(zhí)行任務(wù)，從下個(gè)人開始記數(shù)，再次循環(huán)，直到只剩一人，得到其在隊(duì)伍中的位置，記下該位置視為排長位置，則1號(hào)即可視為最先報(bào)數(shù)的人，通過數(shù)學(xué)計(jì)算即可獲得所求。
2.功能模塊和流程：
1）功能模塊
該程序功能比較
3、單一，主要是為解決敢死隊(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號(hào)開始報(bào)數(shù)，共有n個(gè)人，達(dá)到報(bào)數(shù)上限m=5的戰(zhàn)士出列，繼續(xù)進(jìn)行報(bào)數(shù)，直到剩余最后一人，記下該位置為k。若將該位置視為排長位置，則原先的1號(hào)位置即位所有的開始報(bào)數(shù)的位置z。則z=n-k+2。
2.以單循環(huán)鏈表為存儲(chǔ)結(jié)構(gòu)，包含三個(gè)模塊：
（1）主程序模塊
4、
（2）構(gòu)造鏈表并初始化
（3）刪除結(jié)點(diǎn)
3.結(jié)點(diǎn)類型和指針類型
typedef struct node
{
int data;
struct node *next;
}LNode;/* 定義結(jié)點(diǎn)類型 */
LNode *p;
4.每個(gè)模塊的分析
（1）主程序模塊：
main()
{
LNode *p;
int m,n,z,y;
do
{
printf(" Please input the people number:\n");
scanf ("%d",&n);
5、}
while (n<=0);
do
{
printf(" Please input the excursion:\n");
scanf("%d",&m);
}
while (m<=0);
if (n=1)
printf("the position is: 1");
else
{
p=CREAT(n);
y=DELETE(p,m);
z=n-y+2;
if(z%n==0) /* 排除特殊情況 */
printf ("the position is
6、:\n%d\n",z);
else
printf("the position is:\n%d\n",(n-y+2)%n);
}/* 通過數(shù)學(xué)思想求得實(shí)驗(yàn)要求情況下的數(shù)值 */
}
（2）構(gòu)造單循環(huán)鏈表并初始化模塊：
LNode* CREAT(int n) /* 創(chuàng)建循環(huán)鏈表 */
{
LNode *s,*q,*t;
int i;
if(n!=0)
{
t=q=(LNode *)malloc(sizeof(LNode));
q->data=1;/* 生成
7、第一個(gè)結(jié)點(diǎn)并使其data值為1 */
for(i=2;i<=n;i++)
{
s=(LNode *)malloc(sizeof(LNode));/*自動(dòng)生成結(jié)點(diǎn)*/
q->next=s;
q->next->data=i;/*給第i個(gè)結(jié)點(diǎn)賦值i*/
q=q->next;
}
q->next=t;
}/* 生成后續(xù)結(jié)點(diǎn)，并使其data值即為它所在鏈表（隊(duì)伍）中的位置 */
r
8、eturn t;
}
（3）刪除結(jié)點(diǎn)模塊：
DELETE (LNode* t,int m)/* 鏈表的刪除 */
{
LNode *a;int i;
while (t->next!=t)
{
for (i=1;inext;
a=t->next;
t->next=a->next;
free(a);/*釋放結(jié)點(diǎn)*/
t=t->next;
}/* while循環(huán)依次刪除被點(diǎn)到的士兵 */
9、printf("\n");
return (t->data);
}
(三) 調(diào)試分析：
1.本程序運(yùn)行后的結(jié)果應(yīng)是如下提示：
Exit please input '0' Or Go on
Please input the tatal of the team:
輸入隊(duì)伍總?cè)藬?shù)
Please input the excursion:
輸入間隔人數(shù)
結(jié)果顯示：The wanted position is
選擇的位置
2.在程序調(diào)試運(yùn)行的過程中產(chǎn)生了各種各樣的問題，有的是多了空格，有的是拼寫錯(cuò)誤，還有的是少了括號(hào)，類似的問題有很多。解決的辦法是一遍遍嘗試，不斷逐行逐句進(jìn)行修改。
例如程序調(diào)試過程中遇到警告：發(fā)現(xiàn)錯(cuò)誤為 if(m=1)
后改正為 if(m==1)程序運(yùn)行正確了，運(yùn)行如下：
顯示輸出如圖：
數(shù)據(jù)結(jié)構(gòu)常見問題：12單元28 敢死隊(duì)問題
