數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)五-修道士野人問題

數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)五——修道士野人問題數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)五——修道士野人問題全文共數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)五——修道士野人問題全文共9頁，當(dāng)前為第1頁。實(shí)驗(yàn)課名稱：數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)實(shí)驗(yàn)實(shí)驗(yàn)名稱：修道士野人問題班級：學(xué)號：姓名：時間：一、問題描述河的左岸有N個野人和N個修道士以及一條小船，修道士們想用這條小船把所有的人都運(yùn)到河的右岸，但又受到以下限制：所有人都會劃船，但船一次只能載C人在任意岸上，野人數(shù)不能超過修道士數(shù)，否則修道士將會被野人吃掉?，F(xiàn)假定野人服從任意過河安排，需要規(guī)劃出一種確保修道士安全的過河方案。二、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)typedefstruct{intnum1;//修道士intnum2;//野蠻人intan;//表示兩岸}DataType;//三元組typedefstructNode{intdest;//鄰接表的弧頭結(jié)點(diǎn)序號structNode*next;}Edge;//鄰接表單鏈表的結(jié)點(diǎn)結(jié)構(gòu)體typedefstruct{DataTypedata;//結(jié)點(diǎn)數(shù)據(jù)元素intsorce;//鄰接表的弧尾結(jié)點(diǎn)序號Edge*adj;//鄰接邊的頭指針intpre;//指向此點(diǎn)的點(diǎn)的序號}AdjLHeight;//數(shù)組的數(shù)據(jù)元素類型結(jié)構(gòu)體typedefstruct{AdjLHeighta[10000];//鄰接表數(shù)組intnumOfVerts;//結(jié)點(diǎn)個數(shù)intnumOfEdges;//邊個數(shù)}AdjLGraph;//鄰接表結(jié)構(gòu)體三、算法設(shè)計(jì)圖的初始化在G圖中插入結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)五——數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)五——修道士野人問題全文共9頁，當(dāng)前為第2頁。在G圖中插入邊<v1,v2>圖的撤銷數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)五——數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)五——修道士野人問題全文共9頁，當(dāng)前為第3頁。檢查當(dāng)前情況下，修道士是否安全用if語句判斷，左岸右岸的修道士人數(shù)都必須不小于野人數(shù)目才可生成在船上修道士仍安全的情況打印安全渡河的過程數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)五數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)五——修道士野人問題全文共9頁，當(dāng)前為第4頁。廣度搜索建立表數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)五數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)五——修道士野人問題全文共9頁，當(dāng)前為第5頁。數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)五——數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)五——修道士野人問題全文共9頁，當(dāng)前為第6頁。四、界面設(shè)計(jì)野人和修道士人數(shù)N:野人和修道士人數(shù)N:船可乘人數(shù)C:（船所在岸的人數(shù)）（修野岸）船上人數(shù)[修道士，野人]右邊岸上[修野岸]……(000)重復(fù)以上方式輸出所有的渡河方式五、運(yùn)行測試與分析輸入輸出實(shí)際12(111)船上人數(shù)[修道士，野人][11]右邊岸上[000](000)√35(331)船上人數(shù)[修道士，野人][32]右邊岸上[010](010)船上人數(shù)[修道士，野人][10]左邊岸上[111](111)船上人數(shù)[修道士，野人][11]右邊岸上[000](000)(331)船上人數(shù)[修道士，野人][32]右邊岸上[010](010)船上人數(shù)[修道士，野人][01]左邊岸上[021](021)船上人數(shù)[修道士，野人][02]右邊岸上[000](000)(331)船上人數(shù)[修道士，野人][32]右邊岸上[010](010)船上人數(shù)[修道士，野人][02]左邊岸上[031](031)船上人數(shù)[修道士，野人][03]右邊岸上[000](000)(331)船上人數(shù)[修道士，野人][32]右邊岸上[010](010)船上人數(shù)[修道士，野人][30]左邊岸上[311](311)船上人數(shù)[修道士，野人][31]右邊岸上[000](000)(331)船上人數(shù)[修道士，野人][32]右邊岸上[010](010)船上人數(shù)[修道士，野人][21]左邊岸上[221](221)船上人數(shù)[修道士，野人][22]右邊岸上[000](000)(331)船上人數(shù)[修道士，野人][32]右邊岸上[010](010)船上人數(shù)[修道士，野人][31]左邊岸上[321](321)船上人數(shù)[修道士，野人][32]右邊岸上[000](000)(331)船上人數(shù)[修道士，野人][22]右邊岸上[110]數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)五——數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)五——修道士野人問題全文共9頁，當(dāng)前為第7頁。(311)船上人數(shù)[修道士，野人][31]右邊岸上[000](000)(331)船上人數(shù)[修道士，野人][22]右邊岸上[110](110)船上人數(shù)[修道士，野人][11]左邊岸上[221](221)船上人數(shù)[修道士，野人][22]右邊岸上[000](000)(331)船上人數(shù)[修道士，野人][22]右邊岸上[110](110)船上人數(shù)[修道士，野人][21]左邊岸上[321](321)船上人數(shù)[修道士，野人][32]右邊岸上[000](000)(331)船上人數(shù)[修道士，野人][31]右邊岸上[020](020)船上人數(shù)[修道士，野人][01]左邊岸上[031](031)船上人數(shù)[修道士，野人][03]右邊岸上[000](000)(331)船上人數(shù)[修道士，野人][31]右邊岸上[020](020)船上人數(shù)[修道士，野人][20]左邊岸上[221](221)船上人數(shù)[修道士，野人][22]右邊岸上[000](000)(331)船上人數(shù)[修道士，野人][31]右邊岸上[020](020)船上人數(shù)[修道士，野人][30]左邊岸上[321](321)船上人數(shù)[修道士，野人][32]右邊岸上[000](000)(331)船上人數(shù)[修道士，野人][03]右邊岸上[300](300)船上人數(shù)[修道士，野人][01]左邊岸上[311](311)船上人數(shù)[修道士，野人][31]右邊岸上[000](000)(331)船上人數(shù)[修道士，野人][03]右邊岸上[300](300)船上人數(shù)[修道士，野人][02]左邊岸上[321](321)船上人數(shù)[修道士，野人][32]右邊岸上[000](000)(331)船上人數(shù)[修道士，野人][02]右邊岸上[310](310)船上人數(shù)[修道士，野人][01]左邊岸上[321](321)船上人數(shù)[修道士，野人][32]右邊岸上[000](000)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)五——修道士野人問題全文共9頁，當(dāng)前為第8頁。數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)五——修道士野人問題全文共9頁，當(dāng)前為第8頁。(220)船上人數(shù)[修道士，野人][10]左邊岸上[321](321)船上人數(shù)[修道士，野人][32]右邊岸上[000](000)√23(221)船上人數(shù)[修道士，野人][21]右邊岸上[010](010)船上人數(shù)[修道士，野人][10]左邊岸上[111](111)船上人數(shù)[修道士，野人][11]右邊岸上[000](000)(221)船上人數(shù)[修道士，野人][21]右邊岸上[010](010)船上人數(shù)[修道士，野人][01]左邊岸上[021](021)船上人數(shù)[修道士，野人][02]右邊岸上[000](000)(221)船上人數(shù)[修道士，野人][21]右邊岸上[010](010)船上人數(shù)[修道士，野人][20]左邊岸上[211](211)船上人數(shù)[修道士，野人][21]右邊岸上[000](000)(221)船上人數(shù)[修道士，野人][02]右邊岸上[200](200)船上人數(shù)[修道士，野人][01]左邊岸上[211](211)船上人數(shù)[修道士，野人][21]右邊岸上[000](000)(221)船上人數(shù)[修道士，野人][11]右邊岸上[110](110)船上