一個C語言經典編寫的經典小遊戲，帶注釋和解析

問題描述

一個農夫在河邊帶了一隻狼、一隻羊和一顆白菜，他需要把這三樣東西用船帶到河的對岸。然而，這艘船隻能容下農夫本人和另外一樣東西。如果農夫不在場的話，狼會吃掉羊，羊也會吃掉白菜。請編程為農夫解決這個過河問題。

問題分析

根據問題描述可知，該問題涉及的對象較多，而且運算步驟也較為複雜，因此，在使用C語言實現時，首先需要將具體問題數字化。

由於整個過程的實現需要多步，而不同步驟中各個事物所處的位置不同，因此可以定義一個二維數組或者結構體來表不四個對象狼（wolf）、羊（goat）、白菜（cabbage）和農夫（farmer）。對於東岸和西岸，可以用east和west表示，也可以用0和1來表示， 以保證在程序設計中的簡便性。

題目要求給出四種事物的過河步驟，沒有對先後順序進行約束，這就需要給各個事物依次進行編號，然後依次試探，若試探成功，再進行下一步試探。因此，解決該問題可以使用循環或者遞歸算法，以避免隨機盲目運算而且保證每種情況都可以試探到。

題目要求求出農夫帶一隻羊，一條狼和一顆白菜過河的所有辦法，所以依次成功返回運算結果後，需要繼續運算，直至求出所有結果，即給出農夫不同的過河方案。

算法設計

本程序使用遞歸算法，定義二維數組int a[N][4]存儲每一步中各個事物所處的位置。二維數組的一維下標表示當前進行的步驟，第二維下標可能的取值為0〜3，在這裡規定它與四種事物的具體對應關係為：0——狼、1——羊、2——白菜、3——農夫。接著再將東岸和西岸數字化，用0表示東岸，1表示西岸，該信息存儲在二維數組的對應元素中。

定義Step變量表示渡河的步驟，則成功渡河之後，a數組中的存儲狀態為:

a[Step][0] 1

a[Step][1] 1

a[Step][2] 1

a[Step][3] 1

因為成功渡河後，狼、羊、白菜和農夫都在河的西岸，因此有：

a[Step][0]+a[Step][1]+a[Step][2]+a[Step][3]=4

題目中要求狼和羊、羊和白菜不能在一起，因此若有下述情況出現：

a[Step][1]!=a[Step][3] && (a[Step][2]==a[Step][1] || a[Step][0]=a[Step][1])

則發生錯誤，應返回操作。

在程序實現時，除了定義a數組來存儲每一步中各個對象所處的位置以外，再定義一維數組b[N]來存儲每一步中農夫是如何過河的。

程序中實現遞歸操作部分的核心代碼為：

for(i=-1; i<=2; i++)
{
 b[Step]=i;
 memcpy(a[Step+1], a[Step], 16); /*複製上一步狀態，進行下一步移動*/
 a[Step+1][3]=1-a[Step+1][3]; /*農夫過去或者回來*/
 if(i == -1) 

 {
 search(Step+1); /*進行第一步*/
 }
 else
 if(a[Step][i] == a[Step][3]) /*若該物與農夫同岸，帶回*/
 {
 a[Step+1][i]=a[Step+1][3]; /*帶回該物*/
 search(Step+1); /*進行下一步*/
 }
}

每次循環從-1到2依次代表農夫渡河時為一人、帶狼、帶羊、帶白菜通過，利用語句“b[Step] = i”分別記錄每一步中農夫的渡河方式，語句“a[Step+1][i] = a[Step+1][3]”是利用賦值方式使該對象與農夫一同到對岸或者回到本岸。若渡河成功，則依次輸出渡河方式。“i<=2”為遞歸操作的界限，若i=2時仍無符合條件的方式，則渡河失敗。

上面代碼表示若當前步驟能使各值均為1，則渡河成功，輸出結果，進入迴歸步驟。若當前步驟與以前的步驟相同，則返回操作，代碼如下：

if(memcmp(a[i],a[Step],16) == 0)
{
 return 0;
}

若羊和農夫不在一塊而狼和羊或者羊和白菜在一塊，則返回操作，判斷代碼如下：

if(a[Step][1]!=a[Step][3] && (a[Step][2] == a[Step][1] || a[Step][0] == a[Step][1])) 

{
 return 0;
}

下面是完整的代碼：

#include 
#include 
#include 
#define N 15
int a[N][4];
int b[N];
char *name[]=
{
 " ",
 "and wolf",
 "and goat",
 "and cabbage"
};
int search(int Step)
{
 int i;
 /*若該種步驟能使各值均為1，則輸出結果，進入迴歸步驟*/
 if(a[Step][0]+a[Step][1]+a[Step][2]+a[Step][3] == 4)
 {
 
 for(i=0; i<=Step; i++) /*能夠依次輸出不同的方案*/
 {
 printf("east: ");
 if(a[i][0] == 0)
 printf("wolf ");
 if(a[i][1] == 0)
 printf("goat ");
 if(a[i][2] == 0)
 printf("cabbage ");
 if(a[i][3] == 0)
 printf("farmer ");
 if(a[i][0] && a[i][1] && a[i][2] && a[i][3])
 printf("none");
 printf(" ");
 printf("west: ");
 if(a[i][0] == 1) 

 printf("wolf ");
 if(a[i][1] == 1)
 printf("goat ");
 if(a[i][2] == 1)
 printf("cabbage ");
 if(a[i][3] == 1)
 printf("farmer ");
 if(!(a[i][0] || a[i][1] || a[i][2] || a[i][3]))
 printf("none");
 printf("\n\n\n");
 if(i printf(" the %d time\n",i+1);
 if(i>0 && i {
 if(a[i][3] == 0) /*農夫在本岸*/
 {
 printf(" -----> farmer ");
 printf("%s\n", name[b[i] + 1]);
 }
 else /*農夫在對岸*/
 {
 printf("  printf("%s\n", name[b[i] + 1]);
 }
 }
 }
 printf("\n\n\n\n");
 return 0;
 }
 for(i=0; i {
 if(memcmp(a[i],a[Step],16) == 0) /*若該步與以前步驟相同，取消操作*/
 {
 return 0;
 }
 }
 /*若羊和農夫不在一塊而狼和羊或者羊和白菜在一塊，則取消操作*/
 if(a[Step][1]!=a[Step][3] && (a[Step][2] == a[Step][1] || a[Step][0] == a[Step][1]))
 {
 return 0;
 }
 /*遞歸，從帶第一種動物開始依次向下循環，同時限定遞歸的界限*/
 for(i=-1; i<=2; i++) 

 {
 b[Step]=i;
 memcpy(a[Step+1], a[Step], 16); /*複製上一步狀態，進行下一步移動*/
 a[Step+1][3]=1-a[Step+1][3]; /*農夫過去或者回來*/
 if(i == -1)
 {
 search(Step+1); /*進行第一步*/
 }
 else
 if(a[Step][i] == a[Step][3]) /*若該物與農夫同岸，帶回*/
 {
 a[Step+1][i]=a[Step+1][3]; /*帶回該物*/
 search(Step+1); /*進行下一步*/
 }
 }
 return 0;
}
int main()
{
 printf("\n\n 農夫過河問題，解決方案如下：\n\n\n");
 search(0);
 return 0;
}

運行結果：

 農夫過河問題，解決方案如下：
east: wolf goat cabbage farmer west: none
 the 1 time
east: wolf cabbage west: goat farmer 
 the 2 time
 east: wolf cabbage farmer west: goat 
 the 3 time
 -----> farmer and wolf
east: cabbage west: wolf goat farmer  

 the 4 time
 east: goat cabbage farmer west: wolf 
 the 5 time
 -----> farmer and cabbage
east: goat west: wolf cabbage farmer 
 the 6 time
 east: goat farmer west: wolf cabbage 
 the 7 time
 -----> farmer and goat
east: none west: wolf goat cabbage farmer 
east: wolf goat cabbage farmer west: none
 the 1 time
east: wolf cabbage west: goat farmer 
 the 2 time
 east: wolf cabbage farmer west: goat 
 the 3 time
 -----> farmer and cabbage
east: wolf west: goat cabbage farmer 
 the 4 time
 east: wolf goat farmer west: cabbage 
 the 5 time
 -----> farmer and wolf
east: goat west: wolf cabbage farmer 
 the 6 time
 east: goat farmer west: wolf cabbage 
 the 7 time
 -----> farmer and goat
east: none west: wolf goat cabbage farmer 

閱讀更多 三世浮華 的文章

關鍵字: 小遊戲 編程語言 經典