农夫过河c语言小程序

### C语言实现农夫过河问题 #### 代码结构说明 为了实现农夫过河问题，在C语言中可以采用深度优先搜索(DFS)的方法来遍历所有可能的状态组合，直到找到合法解为止。下面提供一段具体的源码示例。 ```c #include <stdio.h> #define MAX_STEP 10 // 假设最大步数不超过10次 // 定义状态数组，用于存储每一时刻两岸的情况以及当前是第几步 int state[MAX_STEP][4]; void dfs(int step, int farmer, int wolf, int goat, int cabbage); int main() { printf("Solution to the Farmer Crossing River Problem:\n"); dfs(0, 0, 0, 0, 0); // 初始状态下所有人都在左岸 return 0; } void dfs(int step, int farmer, int wolf, int goat, int cabbage){ if (step >= MAX_STEP || (wolf != goat && goat == cabbage)) { // 超过设定的最大步数或存在非法情况则停止探索此路径 return ; } if(farmer==1&&wolf==1&&goat==1&&cabbage==1){ // 当所有人到达右岸时打印解决方案并结束递归 for(int i=0;i<=step;i++){ printf("%d: F=%d W=%d G=%d C=%d\n",i,state[i][0],state[i][1],state[i][2],state[i][3]); } exit(0); } for(int choice=-1;choice<=2;choice++){ switch(choice){ case -1:// 单独移动农民 if(!farmer){ state[step+1][0]=!farmer; state[step+1][1]=wolf; state[step+1][2]=goat; state[step+1][3]=cabbage; dfs(step+1,!farmer,wolf,goat,cabbage); }else{ continue; } break; case 0:// 移动狼和农民 if(wolf==farmer&&!goat){ state[step+1][0]=!farmer; state[step+1][1]=!wolf; state[step+1][2]=goat; state[step+1][3]=cabbage; dfs(step+1,!farmer,!wolf,goat,cabbage); }else{ continue; } break; case 1:// 移动羊和农民 if(goat==farmer){ state[step+1][0]=!farmer; state[step+1][1]=wolf; state[step+1][2]=!goat; state[step+1][3]=cabbage; dfs(step+1,!farmer,wolf,!goat,cabbage); }else{ continue; } break; case 2:// 移动菜和农民 if(cabbage==farmer&&!goat){ state[step+1][0]=!farmer; state[step+1][1]=wolf; state[step+1][2]=goat; state[step+1][3]=!cabbage; dfs(step+1,!farmer,wolf,goat,!cabbage); }else{ continue; } break; default: break; } } } ``` 这段程序定义了一个`dfs()`函数来进行深度优先搜索尝试各种可能性，并且当发现一种可行方案后立即终止整个过程[^4]。此外还设置了全局变量`MAX_STEP`用来限制搜索树的高度以防无限循环的发生。