1、问题描述
从前,一个农夫带着一只狼,一只羊和一棵白菜要河(注意该狼被农夫训服了,但还会
吃羊)。他要将所有东西安全的带到河的对岸,不幸的是河边只有一条船,只能装下农夫和
他的一样东西,并且农夫必须每次都随船过,因为只有他能撑船。在无人看管的情况下,狼
要吃羊,羊要吃白菜,因此,农夫不能在河的某边岸上单独留下狼和羊,也不能单独留下羊
和白菜。那么农夫如何才能使三样东西平安过河呢?
2、需求分析
1)、农夫必须把狼,羊,白菜全部都载过河,且一次只能载一个;
2)、要求狼和羊不能单独在一起,羊和白菜也不能单独在一起,即要么羊单
独在河的一边,要么羊和农夫在一起。
3、系统概述设计
对于上述情况,可以将河的两岸抽象成成数学问题,即将河的本岸抽象成数
字‘0’,将对岸抽象成‘1’;且将狼,羊,白菜,农夫,分别抽象成数字‘0’,
‘1’,‘2’,‘3’。而用数组 a[i][j](取值只能为 0 和 1)表示第 i 次运载是,j
(j=0,1,2,3。分别表示狼,羊,白菜,农夫)所在的位置。而用 b[i]表示第 i
次运载时船上运载的东西(因为农夫每次都必须在船上,所以不用记录,除非穿
上只有农夫一人)。
如此一来,是否全部过河的问题就转化为判断 a[i][0],a[i][1],a[i][2],
a[i][3]是否全为 1 了,即相加之和是否为 4 的问题了;而四者中的两者是否能
在一起的问题就转化它们各自的 a[i][j]是否相等的问题了。
4、系统详细设计
创建一个数组 a[MAXTIMES][4]用于存放农夫,狼,羊,白菜的位置,用 0
表示本岸,1 表示对岸 ;
b[MAXTIMES]用于存放狼,羊,白菜,农夫的编号; 0: 狼,1:羊,2:白菜,
3:农夫;
编写一个递归函数 Ferry(int ferryTimes),其中 ferryTimes 为渡河次数,
在函数中,应考虑 3 个问题:
1 )、 用 a[ferryTimes][0] + a[ferryTimes][1] + a[ferryTimes][2] +
a[ferryTimes][3] == 4 语句判断是否全部到达对岸,如果是,则直接输出结果,
否则,考虑第二个问题;
2 )、 狼 和 羊 是 否 单 独 在 一 起 , 羊 和 白 菜 是 否 单 独 在 一 起 , 用 语 句
==
a[ferryTimes][1]
(a[ferryTimes][2]
a[ferryTimes][1] || a[ferryTimes][0] == a[ferryTimes][1])来实现;
!=
a[ferryTimes][3]
&&
3)、如果上两个条件都不满,则可执行运输的动作,但每次都应考虑,该运
输情况以前是否执行过(即两岸以及船上的东西以及各自位置和以前完全相同),
如果没被执行过,则可以保存此时四者各自的状态,并递归的进行下一次运载。
5、系统测试
6、经验总结
解决实际问题时,应先分析实际问题,找出实际问题的所有约束条件,
然后对问题进行数学模型的抽象化,抓主要因素,省去一些不需要的因素,将其
抽象为数学问题,然后再从整体上设计算法,搭建程序的框架,最后一步步完善
细节,这样做,会使本来毫无头绪的问题变得清晰起来。
7、参考文献
《C++程序设计》
《数据结构》
《算法设计与分析》
程序代码如下:
#include
#include
#include
using namespace std;
const int MAXTIMES = 20;
int a[MAXTIMES][4];//存放农夫,狼,羊,白菜的位置,用 0 表示本岸,1 表示对岸
char *name[] = {"狼", "羊", "白菜", "农夫自己"};
int b[MAXTIMES]; //用于存放狼,羊,白菜,农夫的编号; 0: 狼,1:羊,2:白菜,3:农夫
void Ferry(int ferryTimes) //ferryTimes 为渡河次数
{
int i;
if (a[ferryTimes][0] + a[ferryTimes][1] + a[ferryTimes][2] + a[ferryTimes][3] == 4) //都到达
对岸
{
for (i = 0; i < ferryTimes; i++)
{
if (a[i][3] == 0)
{
cout<<"\t\t\t 载"<
}
}
//若没有出现,则将运载后抵达另一岸的结果记录下来,并进行下一次运载
for (i = 0; i <= 3; i++)
{
b[ferryTimes] = i;
a[ferryTimes + 1][0] = a[ferryTimes][0];
a[ferryTimes + 1][1] = a[ferryTimes][1];
a[ferryTimes + 1][2] = a[ferryTimes][2];
a[ferryTimes + 1][3] = 1 - a[ferryTimes][3];
if (a[ferryTimes][i] == a[ferryTimes][3])
{
a[ferryTimes + 1][i] = a[ferryTimes + 1][3];
Ferry(ferryTimes + 1);
}
}
}
void main()
{
cout<<"\n
****************************************************************************\n";
------------------------
cout<<"
**
**\n";
cout<<"
**
**\n";
cout<<"
**
**\n";
cout<<"
|
农 夫 过 河 问 题
|
------------------------
****************************************************************************\n";
cout<<"\t 农夫使三样东西平安过河方法为:"<