《數(shù)據(jù)結(jié)構(gòu)常見(jiàn)問(wèn)題:12單元28 敢死隊(duì)問(wèn)題》由會(huì)員分享,可在線閱讀,更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)常見(jiàn)問(wèn)題:12單元28 敢死隊(duì)問(wèn)題(4頁(yè)珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、數(shù)據(jù)結(jié)構(gòu)課程常見(jiàn)問(wèn)題 -單元28 敢死隊(duì)問(wèn)題1敢死隊(duì)問(wèn)題求解解析:?jiǎn)栴}描述有M個(gè)敢死隊(duì)員要炸掉敵人的一碉堡,誰(shuí)都不想去,排長(zhǎng)決定用輪回?cái)?shù)數(shù)的辦法來(lái)決定哪個(gè)戰(zhàn)士去執(zhí)行任務(wù)。如果前一個(gè)戰(zhàn)士沒(méi)完成任務(wù),則要再派一個(gè)戰(zhàn)士上去?,F(xiàn)給每個(gè)戰(zhàn)士編一個(gè)號(hào),大家圍坐成一圈,隨便從某一個(gè)戰(zhàn)士開(kāi)始計(jì)數(shù),當(dāng)數(shù)到5時(shí),對(duì)應(yīng)的戰(zhàn)士就去執(zhí)行任務(wù),且此戰(zhàn)士不再參加下一輪計(jì)數(shù)。如果此戰(zhàn)士沒(méi)完成任務(wù),再?gòu)南乱粋€(gè)戰(zhàn)士開(kāi)始數(shù)數(shù),被數(shù)到第5時(shí),此戰(zhàn)士接著去執(zhí)行任務(wù)。以此類(lèi)推,直到任務(wù)完成為止。排長(zhǎng)是不愿意去的,假設(shè)排長(zhǎng)為1號(hào),請(qǐng)你設(shè)計(jì)一程序,求出從第幾號(hào)戰(zhàn)士開(kāi)始計(jì)數(shù)才能讓排長(zhǎng)最后一個(gè)留下來(lái)而不去執(zhí)行任務(wù)。要求:至少采用兩種不同的數(shù)據(jù)結(jié)
2、構(gòu)的方法實(shí)現(xiàn)。一、單循環(huán)鏈表數(shù)據(jù)結(jié)構(gòu)(一) 需求分析 1.本程序任務(wù)是通過(guò)輸入任意隊(duì)伍人數(shù)n和報(bào)數(shù)上限m,輸出使排長(zhǎng)最后一個(gè)執(zhí)行任務(wù)而開(kāi)始記數(shù)的初始位置。首先輸入隊(duì)伍人數(shù)n,然后輸入報(bào)數(shù)上限m(m=n),從1號(hào)開(kāi)始報(bào)數(shù),當(dāng)達(dá)到報(bào)數(shù)上限時(shí),那名士兵出列執(zhí)行任務(wù),從下個(gè)人開(kāi)始記數(shù),再次循環(huán),直到只剩一人,得到其在隊(duì)伍中的位置,記下該位置視為排長(zhǎng)位置,則1號(hào)即可視為最先報(bào)數(shù)的人,通過(guò)數(shù)學(xué)計(jì)算即可獲得所求。2.功能模塊和流程: 1)功能模塊該程序功能比較單一,主要是為解決敢死隊(duì)問(wèn)題而設(shè)計(jì)。通過(guò)輸入隊(duì)伍人數(shù)和報(bào)數(shù)上限即可獲得開(kāi)始報(bào)數(shù)的位置。2)程序流程 (1)構(gòu)造鏈表(2)數(shù)據(jù)輸入(3)執(zhí)行刪除(4)輸
3、出要求數(shù)值(5)結(jié)束3.數(shù)據(jù)測(cè)試:當(dāng) n=10,m=5, 輸出結(jié)果為:要求的位置是:9。(二) 詳細(xì)設(shè)計(jì)1.算法設(shè)計(jì):本程序其實(shí)質(zhì)是約瑟夫環(huán)問(wèn)題。從排長(zhǎng)位置即1號(hào)開(kāi)始報(bào)數(shù),共有n個(gè)人,達(dá)到報(bào)數(shù)上限m=5的戰(zhàn)士出列,繼續(xù)進(jìn)行報(bào)數(shù),直到剩余最后一人,記下該位置為k。若將該位置視為排長(zhǎng)位置,則原先的1號(hào)位置即位所有的開(kāi)始報(bào)數(shù)的位置z。則z=n-k+2。2.以單循環(huán)鏈表為存儲(chǔ)結(jié)構(gòu),包含三個(gè)模塊: (1)主程序模塊 (2)構(gòu)造鏈表并初始化(3)刪除結(jié)點(diǎn) 3.結(jié)點(diǎn)類(lèi)型和指針類(lèi)型typedef struct node int data; struct node *next;LNode;/* 定義結(jié)點(diǎn)類(lèi)型 *
4、/LNode *p;4.每個(gè)模塊的分析(1)主程序模塊:main() LNode *p; int m,n,z,y; do printf( Please input the people number:n); scanf (%d,&n); while (n=0); do printf( Please input the excursion:n); scanf(%d,&m); while (mdata=1;/* 生成第一個(gè)結(jié)點(diǎn)并使其data值為1 */ for(i=2;inext=s; q-next-data=i;/*給第i個(gè)結(jié)點(diǎn)賦值i*/ q=q-next; q-next=t; /* 生成后續(xù)結(jié)
5、點(diǎn),并使其data值即為它所在鏈表(隊(duì)伍)中的位置 */ return 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)到的士兵 */ 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)行的過(guò)程中產(chǎn)生了各種各樣的問(wèn)題,有的是多了空格,有的是拼寫(xiě)錯(cuò)誤,還有的是少了括號(hào),類(lèi)似的問(wèn)題有很多。解決的辦法是一遍遍嘗試,不斷逐行逐句進(jìn)行修改。例如程序調(diào)試過(guò)程中遇到警告:發(fā)現(xiàn)錯(cuò)誤為 if(m=1)后改正為 if(m=1)程序運(yùn)行正確了,運(yùn)行如下:顯示輸出如圖: