題目描述：農(nóng)夫需要把狼、羊、菜和自己運(yùn)到河對岸去，只有農(nóng)夫能夠劃船，而且船比較小，除農(nóng)夫之外每次只能運(yùn)一種東西，還有一個棘手問題，就是如果沒有農(nóng)夫看著，羊會偷吃菜，狼會吃羊。請考慮一種方法，讓農(nóng)夫能夠安全地安排這些東西和他自己過河。

想這個問題一連想了好幾天，本人沒有系統(tǒng)的學(xué)過算法，有些概念也不是很清楚，只因解決問題為目標(biāo)。

嘗試過圖論解決，但用floyed算法只能算出最短路徑值，如何輸出過程，一直沒想出好的解決方法。

然后看了下面這篇文章，嘗試拋棄圖論，用樹的思想來解決這個問題。建議閱讀下面代碼時，先看看這篇文章。

參考資料：http://blog.csdn.net/orbit/article/details/7563220

在寫代碼時，本人采用了上述文章中的思想，又借鑒了圖論中存儲結(jié)點(diǎn)的一些方法。

我覺得這樣寫應(yīng)該非常容易看懂了。具體思路見代碼。

1 #include

2 #define INF 9999

3 //8個動作

4 char *action[8]={"農(nóng)夫單獨(dú)過河","農(nóng)夫帶狼過河","農(nóng)夫帶羊過河","農(nóng)夫帶菜過河",

5 "農(nóng)夫單獨(dú)返回","農(nóng)夫帶狼返回","農(nóng)夫帶羊返回","農(nóng)夫帶菜返回"};

6 //10種狀態(tài)

7 char *state[10]={"人狼羊菜","人狼羊","人狼菜","人羊菜","人羊","狼菜","狼","羊","菜","空"};

8

9 //狀態(tài)轉(zhuǎn)換規(guī)則：GA[i][j]=k 表示【狀態(tài)i】可以通過【動作k】轉(zhuǎn)換到【狀態(tài)j】，GA[i][j]=INF表示不可直接轉(zhuǎn)換

10 int GA[10][10]={INF,INF,INF,INF,INF, 2,INF,INF,INF,INF,

11 INF,INF,INF,INF,INF,INF, 2, 1,INF,INF,

12 INF,INF,INF,INF,INF, 0, 3,INF, 1,INF,

13 INF,INF,INF,INF,INF,INF,INF, 3, 2,INF,

14 INF,INF,INF,INF,INF,INF,INF, 0,INF, 2,

15 6,INF, 4,INF,INF,INF,INF,INF,INF,INF,

16 INF, 6, 7,INF,INF,INF,INF,INF,INF,INF,

17 INF, 5,INF, 7, 4,INF,INF,INF,INF,INF,

18 INF,INF, 5, 6,INF,INF,INF,INF,INF,INF,

19 INF,INF,INF,INF, 6,INF,INF,INF,INF,INF};

20

21 //記錄每一步的動作

22 int record_action[20];

23 //記錄每一步動作后的狀態(tài)

24 int record_state[20];

25

26 //搜索從第step步開始、第i個結(jié)點(diǎn)到第n個結(jié)點(diǎn)的過程(step從0算起)

27 void search(int i,int n,int step)

28 {

29 int k;//動作

30 int j;//可能要轉(zhuǎn)換到的狀態(tài)

31 if(i==n)

32 {

33 for(k=0;k

34 printf("step %d: %s，左岸還剩 %s\n",k+1,action[record_action[k]],state[record_state[k]]);

35 printf("step count:%d\n\n",step);

36 return;

37 }

38 //查找在當(dāng)前【狀態(tài)i】下能轉(zhuǎn)換到的【其它狀態(tài)j】，并且【狀態(tài)j】不能在之前出現(xiàn)過

39 //查找時可能會出現(xiàn)多個 j，所以這是一個多叉樹

40 for(k=0;k<8;k++)

41 {

42 for(j=0;j<10;j++)

43 if(GA[i][j]!=INF&&GA[i][j]==k)//判斷狀態(tài)i能否通過動作k轉(zhuǎn)換到狀態(tài)j

44 {

45 int m;

46 //下面這個循環(huán)是判斷狀態(tài)j在之前是否出現(xiàn)過

47 for(m=0;m

48 if(j==record_state[m])break;

49 if(m

50 //如果j滿足前面所有條件，則記錄這一步

51 record_action[step]=k; //第step步所使用的動作

52 record_state[step]=j; //第step步所轉(zhuǎn)換的狀態(tài)

53 search(j,n,step+1); //繼續(xù)搜索下一步

54 }

55 }

56

57 }

58 int main()

59 {

60 search(0,9,0);

61 return 0;

62 }

來源：https://www.cnblogs.com/zandbin/p/5341656.html

總結(jié)

以上是生活随笔為你收集整理的车羊问题c语言编程,C语言-人狼羊菜问题-最容易看懂的解决方法及代码的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。