課程設(shè)計(jì)--修道士野人過河問題

1、<p><b>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)</b></p><p><b>　　修道士野人過河問題</b></p><p><b>　　修道士與野人問題</b></p><p>　　假設(shè)有n個(gè)修道士和n個(gè)野人準(zhǔn)備渡河，但只有一條能容納c人的小船，為了防止野人侵犯修道士，要求無論在何處，修道士的個(gè)數(shù)

2、不得少于野人的人數(shù)（除非修道士個(gè)數(shù)為0）。如果兩種人都會(huì)劃船，試設(shè)計(jì)一個(gè)算法，確定他們能否渡過河去，若能，則給出一個(gè)小船來回次數(shù)最少的最佳方案。</p><p>　?。?）用一個(gè)三元組（x1,x2,x3）表示渡河過程中各個(gè)狀態(tài)。其中，x1表示起始岸上修道士個(gè)數(shù)，x2表示起始岸上野人個(gè)數(shù)，x3表示小船位置（0——在目的岸，1——在起始岸）。例如（2,1,1）表示起始岸上有兩個(gè)修道士，一個(gè)野人，小船在起始岸一邊。&l

3、t;/p><p>　　采用鄰接表做為存儲(chǔ)結(jié)構(gòu)，將各種狀態(tài)之間的遷移圖保存下來。</p><p>　?。?）采用廣度搜索法，得到首先搜索到的邊數(shù)最少的一條通路。</p><p><b>　?。?）輸出數(shù)據(jù)</b></p><p>　　若問題有解（能渡過河去），則輸出一個(gè)最佳方案。用三元組表示渡河過程中的狀態(tài)，并用箭頭指出這些狀

4、態(tài)之間的遷移</p><p>　　若問題無解，則給出“渡河失敗”的信息。</p><p>　　（4）求出所有的解。</p><p><b>　　1．需求分析</b></p><p>　　有n個(gè)修道士和n個(gè)野人準(zhǔn)備渡河，但只有一條能容納c人的小船，為了防止野人侵犯修道士，要求無論在何處，修道士的個(gè)數(shù)不得少于野人的人數(shù),否則

5、修道士就會(huì)有危險(xiǎn)，設(shè)計(jì)一個(gè)算法，確定他們能否渡過河去，若能，則給出一個(gè)小船來回次數(shù)最少的最佳方案。用三元組（x1,x2,x3）來表示渡河過程中各個(gè)狀態(tài)，其中，x1表示起始岸上修道士個(gè)數(shù)，x2表示起始岸上野人個(gè)數(shù)，x3表示小船位置（0——在目的岸，1——在起始岸）。若問題有解（能渡過河去），則輸出一個(gè)最佳方案。用三元組表示渡河過程中的狀態(tài)，并用箭頭指出這些狀態(tài)之間的遷移：目的狀態(tài)←…中間狀態(tài)←…初始狀態(tài)，若問題無解，則給出“渡河失敗”的信

6、息。</p><p><b>　　2．設(shè)計(jì)</b></p><p><b>　　2.1 設(shè)計(jì)思想</b></p><p><b>　?。?）數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)</b></p><p>　　邏輯結(jié)構(gòu)設(shè)計(jì): 圖型結(jié)構(gòu)</p><p>　　存儲(chǔ)結(jié)構(gòu)設(shè)計(jì): 鏈?zhǔn)酱鎯?chǔ)結(jié)

7、構(gòu)</p><p>　　采用這種數(shù)據(jù)結(jié)構(gòu)的好處：便于采用廣度搜索法，得到首先搜索到的邊數(shù)最少的一條通路，輸出一個(gè)最佳方案，采用圖的鄰接表存儲(chǔ)結(jié)構(gòu)搜索效率較高。</p><p><b>　?。?）算法設(shè)計(jì)</b></p><p>　　算法設(shè)計(jì)的總體設(shè)計(jì)思路為：在得到修道士人數(shù)和小船的容納人數(shù)后，用boatcase得到所有情況，然后再進(jìn)行安全性檢查

8、，以減去修道士少于野人的情況，接著用孩子兄弟結(jié)點(diǎn)表示法，將去對(duì)面的路作為孩子結(jié)點(diǎn)，路與路是兄弟關(guān)系，到達(dá)另一邊時(shí)，同樣以這種方法，直到找到（0，0,0）。主要分為4個(gè)模塊:boatcase生成所有情況，BFS得到邊數(shù)最少的最佳方案，safe安全性檢測(cè)，print輸出安全渡河的全過程。</p><p>　　各個(gè)模塊要完成的主要功能分別為：</p><p>　　生成模塊：生成所有的可能渡河情況

9、</p><p>　　安全檢測(cè)模塊：對(duì)所有的可能渡河情況進(jìn)行安全檢測(cè)，，以減去修道士少于野人的情況</p><p>　　廣度搜索模塊：采用廣度搜索法，得到首先搜索到的邊數(shù)最少的一條通路</p><p>　　輸出模塊：輸出所有安全渡河的全過程</p><p>　?。?）函數(shù)接口規(guī)格說明</p><p>　　void Li

10、nkinit(Link **head)</p><p>　　void insertson(Link *head, DataType x)</p><p>　　void insertbro(Link *head,DataType x)</p><p>　　int boatcase(DataType x,int n) </p><p>　　voi

11、d guangdu(Link *p,int n,int c)</p><p>　　int safe(DataType x,int n)</p><p>　　void print(Link *q,Link *p)</p><p><b>　　3．調(diào)試分析</b></p><p>　?。?）本題是采用鄰接表做為存儲(chǔ)結(jié)構(gòu)，將各

12、種狀態(tài)之間的遷移圖保存下來，并用孩子兄弟表示法，以實(shí)現(xiàn)廣度搜索；剛編好程序時(shí)出現(xiàn)死循環(huán)的現(xiàn)象，例如：帶過去2個(gè)野人又帶回來2個(gè)野人，在和其他同學(xué)討論后，采用了2個(gè)標(biāo)志位來避免出現(xiàn)死循環(huán)的現(xiàn)象，在進(jìn)行運(yùn)行的時(shí)候，曾出現(xiàn)了打印輸出錯(cuò)誤，經(jīng)過一步一步調(diào)試，發(fā)現(xiàn)在插入結(jié)點(diǎn)的時(shí)候出現(xiàn)了插入錯(cuò)誤，即沒有考慮到pre的改變，通過改正，重新運(yùn)行檢測(cè)，運(yùn)行結(jié)果正確，在排版時(shí)通過一步步調(diào)試，參考了課本和老師的課件，并與和其他同學(xué)討論后，終于通過調(diào)試和改正，

13、，能夠使輸出結(jié)果很明顯的渡河方案。</p><p>　?。?）可改進(jìn)內(nèi)容：顯示表示哪些是渡河次數(shù)最短的，最佳渡河方案一共有幾種，并輸出每種最佳渡河方案，另外，可嘗試用深度優(yōu)先搜索算法來找最佳方案。</p><p><b>　　4．用戶手冊(cè)</b></p><p>　　本程序在VC++6.0環(huán)境下運(yùn)行，根據(jù)提示輸入相應(yīng)的渡河人數(shù)和小船能容納的人數(shù)

14、即可。</p><p>　　5．測(cè)試數(shù)據(jù)及測(cè)試結(jié)果</p><p><b>　　測(cè)試用例1</b></p><p>　　測(cè)試輸入： n=3,c=2</p><p>　　測(cè)試目的： 檢驗(yàn)程序運(yùn)行時(shí)是否會(huì)陷入死循環(huán)</p><p><b>　　正確輸出： 見截屏</b></

15、p><p><b>　　輸入情況圖如上</b></p><p>　　統(tǒng)計(jì)及循環(huán)效果圖如上</p><p><b>　　6．源程序清單</b></p><p>　　#include <stdio.h></p><p>　　#include <malloc.h>

16、;</p><p>　　#include <stdlib.h></p><p>　　typedef struct </p><p><b>　　{</b></p><p>　　int xds; //修道士個(gè)數(shù)</p><p>　　int yr; //野人個(gè)數(shù)</p>

17、<p>　　int cw; //船的位置</p><p>　　}DataType;</p><p>　　DataType array[50000];</p><p>　　typedef struct node//結(jié)構(gòu)體定義</p><p><b>　　{</b></p><p>　

18、　DataType data;</p><p>　　struct node *son;//兒子</p><p>　　struct node *bro;//兄弟</p><p>　　struct node *par;//雙親</p><p>　　struct node *next;</p><p><b>　　

19、}Link;</b></p><p>　　void Linkinit(Link **head) //初始化操作</p><p><b>　　{</b></p><p>　　*head=(Link *)malloc(sizeof (Link)); //申請(qǐng)動(dòng)態(tài)空間</p><p>　　(*head)-&

20、gt;son=NULL;</p><p>　　(*head)->bro=NULL;</p><p>　　(*head)->par=NULL;</p><p>　　(*head)->next=NULL;</p><p><b>　　}</b></p><p>　　void inse

21、rtson(Link *head, DataType x) //在鄰接表中插入兒子結(jié)點(diǎn)的操作</p><p><b>　　{</b></p><p>　　Link *q,*s;</p><p>　　q=(Link *)malloc(sizeof (Link));</p><p>　　q->data=x;<

22、/p><p>　　head->son=q;//將x插入給頭結(jié)點(diǎn)的兒子指針</p><p><b>　　s=head;</b></p><p>　　while (s->next!=NULL)</p><p>　　s=s->next;</p><p>　　q->par=head;&

23、lt;/p><p>　　q->son=NULL;</p><p>　　q->bro=NULL;</p><p>　　s->next=q;</p><p>　　q->next=NULL;</p><p><b>　　}</b></p><p>　　void

24、 insertbro(Link *head,DataType x)//在鄰接表中插入兄弟結(jié)點(diǎn)的操作，</p><p>　　//所有的兄弟結(jié)點(diǎn)都指向他們右邊的結(jié)點(diǎn)</p><p><b>　　{</b></p><p>　　Link *q,*s;</p><p>　　q=(Link *)malloc(sizeof (Lin

25、k));</p><p>　　s=head->son;</p><p>　　q->data=x;</p><p>　　while (s->bro!=NULL)</p><p><b>　　s=s->bro;</b></p><p><b>　　s->bro=

26、q;</b></p><p>　　s->next=q;</p><p>　　q->next=NULL;</p><p>　　q->bro=NULL;</p><p>　　q->par=head;</p><p>　　q->son=NULL;</p><p&g

27、t;<b>　　}</b></p><p>　　int boatcase(DataType x,int n) //生成所有情況；</p><p><b>　　{</b></p><p>　　int i=0,a,b,t=0;</p><p>　　if(x.cw) //在此岸,上船的人多優(yōu)先<

28、/p><p><b>　　{</b></p><p>　　a=0;b=n-a; //a為修道士b為野人</p><p>　　while (a+b>=1)//當(dāng)船上有人時(shí)</p><p><b>　　{</b></p><p><b>　　t++;</b>

29、;</p><p>　　while (b>=0)//當(dāng)野人個(gè)數(shù)不為負(fù)數(shù)</p><p>　　{ </p><p>　　array[i].xds=a;</p><p>　　array[i].yr=b;</p><p><b>　　i++;</b></p

30、><p><b>　　a++;</b></p><p><b>　　b--;</b></p><p><b>　　}</b></p><p>　　a=0;//船上空位個(gè)數(shù)</p><p><b>　　b=n-a-t;</b></p

31、><p><b>　　}</b></p><p><b>　　}</b></p><p>　　else//在對(duì)岸,上船的人少優(yōu)先</p><p><b>　　{</b></p><p>　　a=1;b=0;t=0;</p><p>　

32、　while (a+b<=n)</p><p><b>　　{</b></p><p>　　t++;//船上的人數(shù)</p><p>　　while (a>=0)</p><p>　　{ </p><p>　　array[i].xds=a*(-1);<

33、/p><p>　　array[i].yr=b*(-1);</p><p><b>　　i++;</b></p><p><b>　　a--;</b></p><p><b>　　b++;</b></p><p><b>　　} </b>

34、</p><p>　　a=array[0].xds*(-1)+t;</p><p><b>　　b=0;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　return i; //i為總數(shù)量&l

35、t;/p><p><b>　　}</b></p><p>　　int safe(DataType x,int n)//安全性檢測(cè)</p><p><b>　　{ </b></p><p>　　if ((x.xds>=x.yr||x.xds==0)&&((n-x.xds)>=(

36、n-x.yr)||x.xds==n)&&x.xds>=0&&x.xds<=n&&x.yr>=0&&x.yr<=n)</p><p>　　return 1;//船上修道士</p><p><b>　　else</b></p><p><b>　　re

37、turn 0;</b></p><p><b>　　}</b></p><p>　　void print(Link *q,Link *p) //打印安全渡河的過程,當(dāng)船到對(duì)岸時(shí),把對(duì)岸當(dāng)作其始岸,此岸當(dāng)作彼岸</p><p><b>　　{</b></p><p>　　DataT

38、ype a[100];</p><p><b>　　int i=1;</b></p><p>　　a[0].cw=0;</p><p>　　a[0].xds=0;</p><p>　　a[0].yr=0;</p><p>　　while (q!=p)//避免出現(xiàn)相同情況而循環(huán)</p>

39、<p><b>　　{</b></p><p>　　a[i++]=q->data;//將一次過河的情況給b[i]</p><p><b>　　q=q->par;</b></p><p><b>　　}</b></p><p>　　while ((--i)

40、>-1) //輸出過河圖 </p><p><b>　　{</b></p><p>　　printf("( %d %d %d )",a[i].xds,a[i].yr,a[i].cw);</p><p>　　if (!(a[i].xds==0&&a[i].yr==0&&a[i].cw

41、==0)) </p><p><b>　　{</b></p><p>　　if(a[i].cw==1) </p><p>　　printf("-->(%d %d)-->(%d %d 0)\n",a[i].xds-a[i-1].xds,a[i].yr-a[i-1].yr,a[i-1].xds,a

42、[i-1].yr);</p><p>　　//a[i].xds-a[i-1].xds表示過河過程中船上的修道士數(shù),a[i].yr-a[i-1].yr表示過河過程中船上的野人數(shù)</p><p><b>　　else</b></p><p>　　printf(" <-- ( %d %d ) <-- ( %d %d 1 )\n&

43、quot;,(a[i].xds-a[i-1].xds)*(-1),(-1)*(a[i].yr-a[i-1].yr),a[i-1].xds,a[i-1].yr);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　printf("渡河成功!\n");<

44、;/p><p><b>　　}</b></p><p>　　void guangdu(Link *p,int n,int c)//廣度搜索 </p><p><b>　　{</b></p><p>　　Link *q,*t;</p><p>　　DataType tem;<

45、/p><p>　　int i,flag1,flag2,g=0,j,count=0;</p><p><b>　　q=p->son;</b></p><p>　　while (q!=NULL) </p><p><b>　　{</b></p><p>　　flag1=0;

46、 j=boatcase(q->data,c);//可能過河的情況</p><p>　　for (i=0;i<j;i++)//搜索兄弟結(jié)點(diǎn)</p><p><b>　　{</b></p><p>　　tem.xds=q->data.xds-array[i].xds;</p><p>　　tem.

47、yr=q->data.yr-array[i].yr;</p><p>　　tem.cw=1-q->data.cw;</p><p><b>　　t=q;</b></p><p>　　if (safe(tem,n))//是否安全</p><p><b>　　{</b></p>

48、<p>　　flag2=1;//1表示沒有死循環(huán)</p><p>　　while (t!=p)//保證不會(huì)出現(xiàn)循環(huán)</p><p><b>　　{</b></p><p>　　if(tem.xds== t->data.xds&&tem.yr==t->data.yr&&tem.cw==t-&

49、gt;data.cw)</p><p>　　{//出現(xiàn)相當(dāng)情況時(shí)候</p><p><b>　　flag2=0;</b></p><p>　　break; </p><p><b>　　}</b></p><p><b>　　t=t-&

50、gt;par;</b></p><p><b>　　}</b></p><p>　　if(flag2==1)</p><p><b>　　{</b></p><p>　　if (flag1==0) {</p><p>　　in

51、sertson(q, tem);</p><p><b>　　flag1=1;</b></p><p><b>　　}</b></p><p><b>　　else </b></p><p>　　insertbro(q,tem);

52、 </p><p>　　if (tem.xds==0&&tem.yr==0&&tem.cw==0)</p><p><b>　　{</b></p><p>　　print(q,p);</p><p><b>　　count+

53、+;</b></p><p><b>　　}</b></p><p>　　} </p><p><b>　　} </b></p><p><b>　　} </b></p><p>　　q=q->

54、next;</p><p><b>　　} </b></p><p>　　if (count==0)</p><p>　　printf("無法成功渡河!\n");</p><p><b>　　else</b></p><p>　　printf("

55、;有%d種渡河方式。\n",count);</p><p><b>　　}</b></p><p>　　int main()</p><p><b>　　{</b></p><p>　　int n,c,back;</p><p><b>　　Link *p

56、;</b></p><p>　　DataType tem;</p><p>　　while (back)</p><p><b>　　{</b></p><p>　　printf("請(qǐng)輸入修道士與野人的人數(shù)n:\n");</p><p>　　scanf("

57、%d",&n);</p><p><b>　　if (n==0)</b></p><p><b>　　break;</b></p><p>　　printf("請(qǐng)輸入船可容納的人數(shù)c:\n");</p><p>　　scanf("%d",&a

58、mp;c);</p><p>　　tem.xds=n;</p><p><b>　　tem.yr=n;</b></p><p><b>　　tem.cw=1;</b></p><p>　　Linkinit(&p); //初始化鄰接表;</p><p>　　inser

59、tson(p, tem); //將初始狀態(tài)作為頭結(jié)點(diǎn)的孩子結(jié)點(diǎn)；</p><p>　　guangdu(p,n,c); //進(jìn)行廣度搜索；</p><p>　　printf("是否繼續(xù)?(繼續(xù) 1 ,退出 0 )\n");</p><p>　　scanf("%d",&back);</p><p>