C語言——農夫過河問題解決方法，小程序！

問題描述

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

問題分析

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

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

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

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

演算法設計

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

想要一起學習C++的可以加裙六二六八七一九一六，裙內有各種資料滿足大家，歡迎加裙

定義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

{

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

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

if(memcmp(a[i],a[Step],16) == 0)

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

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

下面是完整的代碼：

#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

想要一起學習C++的可以加裙六二六八七一九一六，裙內有各種資料滿足大家，歡迎加裙

{

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("

");

if(i

printf(" the %d time
",i+1);

if(i>0 && i

{

if(a[i][3] == 0) /*農夫在本岸*/

{

printf(" -----> farmer ");

printf("%s
", name[b[i] + 1]);

}

else /*農夫在對岸*/

{

printf("

printf("%s
", name[b[i] + 1]);

}

}

}

printf("

");

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

{

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("

農夫過河問題，解決方案如下：

");

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

想要一起學習C++的可以加裙六二六八七一九一六，裙內有各種資料滿足大家，歡迎加裙

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！