傳教士與野人過(guò)河問(wèn)題-wenkub
2022-08-20 08:09:36 本頁(yè)面
【正文】 , c, b狀 態(tài) m, c, bS03,3,1S81,3,1S163,3,0S241,3,0S13,2,1S91,2,1S173,2,0S251,2,0S23,1,1S101,1,1S183,1,0S261,1,0S33,0,1S111,0,1S193,0,0S271,0,0S42,3,1S120,3,1S202,3,0S280,3,0S52,2,1S130,2,1S212,2,0S290,2,0S62,1,1S140,1,1S222,1,0S300,1,0S72,0,1S150,0,1S232,0,0S310,0,0值得注意的是按照題目規(guī)定的條件，我們應(yīng)該劃去不合法的狀態(tài)，這樣可以加快搜索求解的效率。 根據(jù)上述分析，共有16個(gè)合法狀態(tài)和允許的操作，可以劃出傳教士和食人者問(wèn)題的狀態(tài)空間圖，如圖6—4所示。源代碼：include include include define maxloop 100 /* 最大層數(shù)，對(duì)于不同的擴(kuò)展方法自動(dòng)調(diào)整取值 */ define pristnum 3 /*初始化時(shí)設(shè)定有3個(gè)野人3個(gè)傳教士，實(shí)際可以改動(dòng)*/ define slavenum 3struct SPQ{ int sr,pr。 /* 去時(shí)（由右向左時(shí)）船上的人數(shù) */ int loop。/* 記錄總的擴(kuò)展次數(shù) */ int openednum。 struct SPQ *oend。 void initiate()。 int search()。 void addtoopened(struct SPQ *ntx) /*擴(kuò)展節(jié)點(diǎn)*/ { unopened = unopened nextnode。 oend = ntx。 struct SPQ *ntx。 for( i = 0 。 exit(0)。 newnode pl = ntx pl。 newnode spr = ntx spr。 newnode nextnode = result。 struct SPQ* nodefree。 opened = opened nextnode。 i++ ) { nodefree = unopened。 int fsr , fpr 。 printf(%d個(gè)野人 ,result sr)。 i resultnum 。 printf(\n\n\t左岸人數(shù) 船上人數(shù)及方向 右岸人數(shù)\n)。 fsl = result sl result sst + result ssr。 printf(傳教士%8d%8d\t\t%8d\n,result pl,result spr,result pr result spr)。 } void goon() /*循環(huán)操作選擇*/ { char choice。choice)。)break。 } }int main() { int flag。 flag = search ()。 goon()。 } }system(pause)。 uend = unopened = (struct SPQ*)malloc(sizeof(spq))。 openednum=0。 unopened pr = pristnum。 unopened spt = 0。 printf(*********************************************************************\n)。在任何時(shí)候，如果野人人數(shù)超過(guò)傳教士人數(shù)，野人\n)。 printf(\n默認(rèn)的n、m值皆為3\n)。choice)。) { printf(\n請(qǐng)輸入傳教士人數(shù))。 if(x0) { unopened pr = x。 for(。 break。N39。 /* 提供將要擴(kuò)展的結(jié)點(diǎn)的指針 */ for( 。 /* 將ntx加入已擴(kuò)展鏈表，并將這個(gè)節(jié)點(diǎn)從待擴(kuò)展鏈表中去掉 */ flag = stretch(ntx)。 /* 在左岸上的人數(shù) */ int sst , spt 。 sst = 2 。 fpl = ntx pl。 fsr = fsr sst。 (fsr == 0))/* 搜索成功 */ { newnode = (struct SPQ*) malloc (sizeof(spq)
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1