數(shù)據(jù)結(jié)構(gòu)常見問題:12單元28 敢死隊(duì)問題
-
資源ID:161296887
資源大?。?span id="24d9guoke414" class="font-tahoma">57.50KB
全文頁數(shù):4頁
- 資源格式: DOC
下載積分:10積分
快捷下載
會(huì)員登錄下載
微信登錄下載
微信掃一掃登錄
友情提示
2、PDF文件下載后,可能會(huì)被瀏覽器默認(rèn)打開,此種情況可以點(diǎn)擊瀏覽器菜單,保存網(wǎng)頁到桌面,就可以正常下載了。
3、本站不支持迅雷下載,請(qǐng)使用電腦自帶的IE瀏覽器,或者360瀏覽器、谷歌瀏覽器下載即可。
4、本站資源下載后的文檔和圖紙-無水印,預(yù)覽文檔經(jīng)過壓縮,下載后原文更清晰。
5、試題試卷類文檔,如果標(biāo)題沒有明確說明有答案則都視為沒有答案,請(qǐng)知曉。
|
數(shù)據(jù)結(jié)構(gòu)常見問題:12單元28 敢死隊(duì)問題
數(shù)據(jù)結(jié)構(gòu)課程常見問題 -單元28 敢死隊(duì)問題1敢死隊(duì)問題求解解析:?jiǎn)栴}描述有M個(gè)敢死隊(duì)員要炸掉敵人的一碉堡,誰都不想去,排長(zhǎng)決定用輪回?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ù)完成為止。排長(zhǎng)是不愿意去的,假設(shè)排長(zhǎng)為1號(hào),請(qǐng)你設(shè)計(jì)一程序,求出從第幾號(hào)戰(zhàn)士開始計(jì)數(shù)才能讓排長(zhǎng)最后一個(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,輸出使排長(zhǎng)最后一個(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ì)伍中的位置,記下該位置視為排長(zhǎng)位置,則1號(hào)即可視為最先報(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ù)測(cè)試:當(dāng) n=10,m=5, 輸出結(jié)果為:要求的位置是:9。(二) 詳細(xì)設(shè)計(jì)1.算法設(shè)計(jì):本程序其實(shí)質(zhì)是約瑟夫環(huán)問題。從排長(zhǎng)位置即1號(hào)開始報(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)位置即位所有的開始報(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)類型和指針類型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); 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:n%dn",z); else printf("the position is:n%dn",(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;/* 生成第一個(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ì)伍)中的位置 */ return t;(3)刪除結(jié)點(diǎn)模塊:DELETE (LNode* t,int m)/* 鏈表的刪除 */ LNode *a;int i; while (t->next!=t) for (i=1;i<m-1;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)是如下提示: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)行如下:顯示輸出如圖: