課程設(shè)計(jì)修道士野人過(guò)河問(wèn)題

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)修道士野人過(guò)河問(wèn)題班級(jí)：計(jì)師111學(xué)號(hào)：1113012027姓名：成粵任課老師：陳德裕時(shí)間：修道士與野人問(wèn)題假設(shè)有n個(gè)修道士和n個(gè)野人準(zhǔn)備渡河，但只有一條能容納c人的小船，為了防止野人侵犯修道士，要求無(wú)論在何處，修道士的個(gè)數(shù)不得少于野人的人數(shù)（除非修道士個(gè)數(shù)為0）。如果兩種人都會(huì)劃船，試設(shè)計(jì)一個(gè)算法，確定他們能否渡過(guò)河去，若能，則給出一個(gè)小船來(lái)回次數(shù)最少的最佳方案。（1）用一個(gè)三元組（x1,x2,x3）表示渡河過(guò)程中各個(gè)狀態(tài)。其中，x1表示起始岸上修道士個(gè)數(shù)，x2表示起始岸上野人個(gè)數(shù)，x3表示小船位置（0在目的岸，1在起始岸）。例如（2,1,1）表示起始岸上有兩個(gè)修道士，一個(gè)野

2、人，小船在起始岸一邊。采用鄰接表做為存儲(chǔ)結(jié)構(gòu)，將各種狀態(tài)之間的遷移圖保存下來(lái)。（2）采用廣度搜索法，得到首先搜索到的邊數(shù)最少的一條通路。（3）輸出數(shù)據(jù)若問(wèn)題有解（能渡過(guò)河去），則輸出一個(gè)最佳方案。用三元組表示渡河過(guò)程中的狀態(tài)，并用箭頭指出這些狀態(tài)之間的遷移 若問(wèn)題無(wú)解，則給出“渡河失敗”的信息。 （4）求出所有的解。1需求分析有n個(gè)修道士和n個(gè)野人準(zhǔn)備渡河，但只有一條能容納c人的小船，為了防止野人侵犯修道士，要求無(wú)論在何處，修道士的個(gè)數(shù)不得少于野人的人數(shù),否則修道士就會(huì)有危險(xiǎn)，設(shè)計(jì)一個(gè)算法，確定他們能否渡過(guò)河去，若能，則給出一個(gè)小船來(lái)回次數(shù)最少的最佳方案。用三元組（x1,x2,x3）來(lái)表示渡河

3、過(guò)程中各個(gè)狀態(tài)，其中，x1表示起始岸上修道士個(gè)數(shù)，x2表示起始岸上野人個(gè)數(shù)，x3表示小船位置（0在目的岸，1在起始岸）。若問(wèn)題有解（能渡過(guò)河去），則輸出一個(gè)最佳方案。用三元組表示渡河過(guò)程中的狀態(tài)，并用箭頭指出這些狀態(tài)之間的遷移：目的狀態(tài)中間狀態(tài)初始狀態(tài)，若問(wèn)題無(wú)解，則給出“渡河失敗”的信息。2設(shè)計(jì)2.1 設(shè)計(jì)思想（1）數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)邏輯結(jié)構(gòu)設(shè)計(jì):圖型結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)設(shè)計(jì):鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)采用這種數(shù)據(jù)結(jié)構(gòu)的好處：便于采用廣度搜索法，得到首先搜索到的邊數(shù)最少的一條通路，輸出一個(gè)最佳方案，采用圖的鄰接表存儲(chǔ)結(jié)構(gòu)搜索效率較高。（2）算法設(shè)計(jì)算法設(shè)計(jì)的總體設(shè)計(jì)思路為：在得到修道士人數(shù)和小船的容納人數(shù)后，用boat

4、case得到所有情況，然后再進(jìn)行安全性檢查，以減去修道士少于野人的情況，接著用孩子兄弟結(jié)點(diǎn)表示法，將去對(duì)面的路作為孩子結(jié)點(diǎn)，路與路是兄弟關(guān)系，到達(dá)另一邊時(shí)，同樣以這種方法，直到找到（0，0,0）。主要分為4個(gè)模塊:boatcase生成所有情況，BFS得到邊數(shù)最少的最佳方案，safe安全性檢測(cè)，print輸出安全渡河的全過(guò)程。各個(gè)模塊要完成的主要功能分別為：生成模塊：生成所有的可能渡河情況安全檢測(cè)模塊：對(duì)所有的可能渡河情況進(jìn)行安全檢測(cè)，以減去修道士少于野人的情況廣度搜索模塊：采用廣度搜索法，得到首先搜索到的邊數(shù)最少的一條通路輸出模塊：輸出所有安全渡河的全過(guò)程（2）函數(shù)接口規(guī)格說(shuō)明void Lin

5、kinit(Link *head)void insertson(Link *head, DataType x)void insertbro(Link *head,DataType x)int boatcase(DataType x,int n) void guangdu(Link *p,int n,int c)int safe(DataType x,int n)void print(Link *q,Link *p)3調(diào)試分析（1）本題是采用鄰接表做為存儲(chǔ)結(jié)構(gòu)，將各種狀態(tài)之間的遷移圖保存下來(lái)，并用孩子兄弟表示法，以實(shí)現(xiàn)廣度搜索；剛編好程序時(shí)出現(xiàn)死循環(huán)的現(xiàn)象，例如：帶過(guò)去2個(gè)野人又帶回來(lái)2個(gè)野人，

6、在和其他同學(xué)討論后，采用了2個(gè)標(biāo)志位來(lái)避免出現(xiàn)死循環(huán)的現(xiàn)象，在進(jìn)行運(yùn)行的時(shí)候，曾出現(xiàn)了打印輸出錯(cuò)誤，經(jīng)過(guò)一步一步調(diào)試，發(fā)現(xiàn)在插入結(jié)點(diǎn)的時(shí)候出現(xiàn)了插入錯(cuò)誤，即沒(méi)有考慮到pre的改變，通過(guò)改正，重新運(yùn)行檢測(cè)，運(yùn)行結(jié)果正確，在排版時(shí)通過(guò)一步步調(diào)試，參考了課本和老師的課件，并與和其他同學(xué)討論后，終于通過(guò)調(diào)試和改正，能夠使輸出結(jié)果很明顯的渡河方案。（2）可改進(jìn)內(nèi)容：顯示表示哪些是渡河次數(shù)最短的，最佳渡河方案一共有幾種，并輸出每種最佳渡河方案，另外，可嘗試用深度優(yōu)先搜索算法來(lái)找最佳方案。4用戶手冊(cè)本程序在VC+6.0環(huán)境下運(yùn)行，根據(jù)提示輸入相應(yīng)的渡河人數(shù)和小船能容納的人數(shù)即可。5測(cè)試數(shù)據(jù)及測(cè)試結(jié)果測(cè)試用例

7、1測(cè)試輸入： n=3,c=2測(cè)試目的： 檢驗(yàn)程序運(yùn)行時(shí)是否會(huì)陷入死循環(huán)正確輸出： 見(jiàn)截屏輸入情況圖如上統(tǒng)計(jì)及循環(huán)效果圖如上6源程序清單#include <stdio.h>#include <malloc.h>#include <stdlib.h>typedef struct int xds; /修道士個(gè)數(shù) int yr; /野人個(gè)數(shù) int cw; /船的位置DataType;DataType array50000;typedef struct node/結(jié)構(gòu)體定義 DataType data; struct node *son;/兒子 struct nod

8、e *bro;/兄弟 struct node *par;/雙親 struct node *next;Link;void Linkinit(Link *head) /初始化操作 *head=(Link *)malloc(sizeof (Link); /申請(qǐng)動(dòng)態(tài)空間 (*head)->son=NULL; (*head)->bro=NULL; (*head)->par=NULL; (*head)->next=NULL;void insertson(Link *head, DataType x) /在鄰接表中插入兒子結(jié)點(diǎn)的操作 Link *q,*s; q=(Link *)mal

9、loc(sizeof (Link); q->data=x; head->son=q;/將x插入給頭結(jié)點(diǎn)的兒子指針 s=head; while (s->next!=NULL) s=s->next; q->par=head; q->son=NULL; q->bro=NULL; s->next=q; q->next=NULL;void insertbro(Link *head,DataType x)/在鄰接表中插入兄弟結(jié)點(diǎn)的操作， /所有的兄弟結(jié)點(diǎn)都指向他們右邊的結(jié)點(diǎn) Link *q,*s; q=(Link *)malloc(sizeof (Li

10、nk); s=head->son; q->data=x; while (s->bro!=NULL) s=s->bro; s->bro=q; s->next=q; q->next=NULL; q->bro=NULL; q->par=head; q->son=NULL;int boatcase(DataType x,int n) /生成所有情況； int i=0,a,b,t=0; if(x.cw) /在此岸,上船的人多優(yōu)先 a=0;b=n-a; /a為修道士b為野人 while (a+b>=1)/當(dāng)船上有人時(shí) t+; while (

11、b>=0)/當(dāng)野人個(gè)數(shù)不為負(fù)數(shù) arrayi.xds=a; arrayi.yr=b; i+; a+; b-; a=0;/船上空位個(gè)數(shù) b=n-a-t; else/在對(duì)岸,上船的人少優(yōu)先 a=1;b=0;t=0; while (a+b<=n) t+;/船上的人數(shù) while (a>=0) arrayi.xds=a*(-1); arrayi.yr=b*(-1); i+; a-; b+; a=array0.xds*(-1)+t; b=0; return i; /i為總數(shù)量int safe(DataType x,int n)/安全性檢測(cè) if (x.xds>=x.yr|x.xd

12、s=0)&&(n-x.xds)>=(n-x.yr)|x.xds=n)&&x.xds>=0&&x.xds<=n&&x.yr>=0&&x.yr<=n) return 1;/船上修道士 else return 0;void print(Link *q,Link *p) /打印安全渡河的過(guò)程,當(dāng)船到對(duì)岸時(shí),把對(duì)岸當(dāng)作其始岸,此岸當(dāng)作彼岸 DataType a100; int i=1; a0.cw=0; a0.xds=0; a0.yr=0; while (q!=p)/避免出現(xiàn)相同情況而循環(huán) ai

13、+=q->data;/將一次過(guò)河的情況給bi q=q->par; while (-i)>-1) /輸出過(guò)河圖 printf("( %d %d %d )",ai.xds,ai.yr,ai.cw); if (!(ai.xds=0&&ai.yr=0&&ai.cw=0) if(ai.cw=1) printf("->(%d %d)->(%d %d 0)n",ai.xds-ai-1.xds,ai.yr-ai-1.yr,ai-1.xds,ai-1.yr); /ai.xds-ai-1.xds表示過(guò)河過(guò)程中船上

14、的修道士數(shù),ai.yr-ai-1.yr表示過(guò)河過(guò)程中船上的野人數(shù) else printf(" <- ( %d %d ) <- ( %d %d 1 )n",(ai.xds-ai-1.xds)*(-1),(-1)*(ai.yr-ai-1.yr),ai-1.xds,ai-1.yr); printf("渡河成功!n");void guangdu(Link *p,int n,int c)/廣度搜索 Link *q,*t; DataType tem; int i,flag1,flag2,g=0,j,count=0; q=p->son; while

15、(q!=NULL) flag1=0; j=boatcase(q->data,c);/可能過(guò)河的情況 for (i=0;i<j;i+)/搜索兄弟結(jié)點(diǎn) tem.xds=q->data.xds-arrayi.xds; tem.yr=q->data.yr-arrayi.yr; tem.cw=1-q->data.cw; t=q; if (safe(tem,n)/是否安全 flag2=1;/1表示沒(méi)有死循環(huán) while (t!=p)/保證不會(huì)出現(xiàn)循環(huán) if(tem.xds= t->data.xds&&tem.yr=t->data.yr&&a

16、mp;tem.cw=t->data.cw) /出現(xiàn)相當(dāng)情況時(shí)候 flag2=0; break; t=t->par; if(flag2=1) if (flag1=0) insertson(q, tem); flag1=1; else insertbro(q,tem); if (tem.xds=0&&tem.yr=0&&tem.cw=0) print(q,p); count+; q=q->next; if (count=0) printf("無(wú)法成功渡河!n"); else printf("有%d種渡河方式。n",count);int main() int n,c,back;Link *p; DataType tem; while (back) printf("請(qǐng)輸入修道士與野人的人數(shù)n:n"); scanf("%d",&n); if (n=0) break