扬州大学信息工程学院
《数据结构》
---课程设计报告
题目：农夫过河
班级：网络1501
学号：1524
姓名：王
指导教师：王
一、课程题目
一个农夫带着一只狼，一只羊和一棵白菜，身处河的南岸。
他要把这些东西全部运到北岸。
他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。
如果农夫在场，则狼不能吃羊，羊不能吃白菜，否则狼会吃羊，羊会吃白菜，所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不吃白菜。
二、需求分析
求出农夫将所有的东西运过河的方案。
三、概要设计
求解这个问题的简单的方法是一步一步进行试探，每一步搜索所有可能的选择，对前一步合适的选择再考虑下一步的各种方案。
要模拟农夫过河问题，首先需要对问题中每个角色的位置进行描述。
一个很方便的办法是用四位二进制数顺序分别表示农夫、狼、白菜和羊的位置。
用0表示农夫或者某东西在河的南岸，1表示在河的北岸。
例如整数5(其二进制表示为0101) 表示农夫和白菜在河的南岸，而狼和羊在北岸。
现在问题变成：从初始状态二进制0000(全部在河的南岸) 出发，寻找一种全部由安全状态构成的状态序列，它以二进制1111(全部到达河的北岸)为最终目标，并且在序列中的每一个状态都可以从前一状态到达。
为避免瞎费功夫，要求在序列中不出现重复的状态。
四、详细设计
实现上述求解的搜索过程可以采用策略广度优先(breadth_first) 搜索。
广度优先就是在搜索过程中总是首先搜索下面一步的所有可能状态，再进一步考虑更后面的各种情况。
要实现广度优先搜索，可以使用队列。
把下一步所有可能的状态都列举出来，放在队列中，再顺序取出来分别进行处理，处理过程中把再下一步的状态放在队列里。
由于队列的操作遵循先进先出的原则，在这个处理过程中，只有在前一步的所有情况都处理完后，才能开始后面一步各情况的处理。
这样，具体算法中就需要用一个整数队列moveTo，它的每个元素表示一个可以安全到达的中间状态。
另外还需要一个数据结构记录已被访问过的各个状态，以及已被发现的能够到达当前这个状态的路径。
由于在这个问题的解决过程中需要列举的所有状态（二进制0000 －1111）一共16种，所以可以构造一个包含16个元素的整数顺序表来实现。
顺序表的第i个元素记录状态i是否已被访问过，若已被访问过则在这个顺序表元素中记入前驱状态值，把这个顺序表叫做route。
route的每个分量初始值均为-1。
route的一个元素具有非负值表示这个状态已访问过，或是正被考虑。
最后可以利用route顺序表元素的值建立起正确的状态路径。
于是得到农夫过河问题的广度优先算法。
在具体应用时，采用链队和顺序队均可，为叙述的方便，不妨设为使用顺序队。
模块划分
1、void BA() //农夫从B岸到A岸
2、void xu() //初始化三样东西的位置
3、void f() //判断农夫的位置
4、int g() //判断羊的位置
5、void huan () //农夫返回
6、void AB() //农夫从A岸到B岸
五，测试数据及运行结果
运行结果：
六，源程序
#include<stdio.h>
int s[100],t=0;
void BA(int a[4],int b[4]);
void xu(int a[4])
{int i,j,k;
for(i=0;i<3;i++)
for(j=i+1;j<4;j++)if(a[i]<a[j])
{k=a[i];a[i]=a[j];a[j]=k; }}
int f(int a[4],int x)
{int i,j=0,b[4];
for(i=0;a[i];i++)
{if(i==x)continue;
b[j]=a[i];
if(j&&b[j]==b[j-1]-1)return 1;j++;} return 0;}
int g()
{int i,r;
for(i=t-1;i>=t/2;i-=2)
{for(r=0;r<t-i;r++)
if(s[t-r]!=s[i-r]) break;
if(r==t-i)break;}
if(i<t/2)return 0;
else return 1;}
void huan(int a[4],int b[4],int x)
{int i;
for(i=0;a[i]!=x;i++);
a[i]=0;b[3]=x;xu(a);xu(b);}
void AB(int a[4],int b[4])
{int i;
for(i=0;a[i-1]||i==0;i++)
{if(f(a,i)) continue;
s[t]=a[i];
if(g()) continue;
huan(a,b,s[t]);
t++;
if(a[0]==0) break;
BA(a,b);
if(a[0]==0) break;
t--;
huan(b,a,s[t]);
}
}
void BA(int a[4],int b[4])
{int i;
for(i=0;b[i-1]||i==0;i++)
{if(f(b,i)) continue;
s[t]=b[i];
if(g()) continue;
huan(b,a,s[t]);
t++;
AB(a,b);
if(a[0]==0) break;
t--;
huan(a,b,s[t]);}}
void main()
{int i,a[4]={3,2,1},b[4]={0};
AB(a,b);
for(i=0;i<t;i++)
{if(i%2)printf("农夫从B岸到A岸:");
else printf("农夫从A岸到B岸:");
switch(s[i])
{case 0:printf("什么都不带");break;
case 1:printf("把狼带过河");break;
case 2:printf("把羊带过河");break;
case 3:printf("把菜带过河");break;
}
printf("\n");} }。