int s[100],t=0
void BA(int a[4],int b[4])
void xu(int a[4])
{
int i,j,k
for(i=0i<3i++)for(j=i+1j<4j++)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=0a[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-1i>=t/2i-=2)
{
for(r=0r<t-ir++)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=0a[i]!=xi++)
a[i]=0
b[3]=x
xu(a)
xu(b)
}
void AB(int a[4],int b[4])
{
int i
for(i=0a[i-1]||i==0i++)
{
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=0b[i-1]||i==0i++)
{
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=0i<ti++)
{
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")
}
}
一、算法分析先来看看问题的初始状态和目标状态，假设和分为甲岸和乙岸：
乙岸，0野人，0牧师；
船停在甲岸，船上有0个人；
目标状态：甲岸，0野人，0牧师；
乙岸，3野人，3牧师；
船停在乙岸，船上有0个人；
整个问题就抽象成了怎样从初始状态经中间的一系列状态达到目标状态。问题状态的改变是通过划船渡河来引发的，所以合理的渡河 *** 作就成了通常所说的算符，根据题目要求，可以得出以下5个算符（按照渡船方向的不同，也可以理解为10个算符）：
渡1野人、渡1牧师、渡1野人1牧师、渡2野人、渡2牧师
算符知道以后，剩下的核心问题就是搜索方法了，本文采用深度优先搜索，通过一个FindNext(…)函数找出下一步可以进行的渡河 *** 作中的最优 *** 作，如果没有找到则返回其父节点，看看是否有其它兄弟节点可以扩展，然后用Process(…)函数递规调用FindNext(…)，一级一级的向后扩展。
搜索中采用的一些规则如下：
1、渡船优先规则：甲岸一次运走的人越多越好（即甲岸运多人优先），同时野人优先运走；
乙岸一次运走的人越少越好（即乙岸运少人优先），同时牧师优先运走；
2、不能重复上次渡船 *** 作（通过链表中前一 *** 作比较），避免进入死循环
3、任何时候河两边的野人和牧师数均分别大于等于0且小于等于3；
4、由于只是找出最优解，所以当找到某一算符（当前最优先的）满足 *** 作条件后，不再搜索其兄弟节点，而是直接载入链表。
5、若扩展某节点a的时候，没有找到合适的子节点，则从链表中返回节点a的父节点b，从上次已经选择了的算符之后的算符中找最优先的算符继续扩展b。
二、基本数据结构
仔细阅读问题，可以发现有些基本东西我们必须把握，例如：每时刻河两岸野人牧师各自的数目、船的状态、整个问题状态。所以我们定义如下几个数据结构：
typedef struct _riverside // 岸边状态类型
{
int wildMan// 野人数
int churchMan// 牧师数
}RIVERSIDE
typedef struct _boat // 船的状态类型
{
int wildMan// 野人数
int churchMan// 牧师数
}BOAT
typedef struct _question // 整个问题状态
{
RIVERSIDE riverSide1// 甲岸
RIVERSIDE riverSide2// 乙岸
int side// 船的位置, 甲岸为-1, 乙岸为1
BOAT boat// 船的状态
_question* pPrev// 指向前一渡船 *** 作
_question* pNext// 指向后一渡船 *** 作
}QUESTION
用QUESTION来声明一个最基本的链表。
三、程序流程及具体设计
本文只找出了最优解，据我所知，本问题有三种解。如果真要找出这三种解，^_^，那就得加强对链表的 *** 作了，比如说自己写一个动态链表类，顺便完成一些初始化工作，估计看起来会舒服些。
下面给出部分关键程序：
// 主函数
int main()
{
// 初始化
QUESTION* pHead = new QUESTION
pHead->riverSide1.wildMan = 3
pHead->riverSide1.churchMan = 3
pHead->riverSide2.wildMan = 0
pHead->riverSide2.churchMan = 0
pHead->side = -1// 船在甲岸
pHead->pPrev = NULL
pHead->pNext = NULL
pHead->boat.wildMan = 0
pHead->boat.churchMan = 0
if (Process(pHead))
{
// ......... 遍历链表输出结果
}
cout<<"成功渡河。"
}
else
cout<<"到底怎样才能渡河呢? 郁闷!"<<endl
// 回收内存空间
while (pHead)
{
QUESTION* pTemp = pHead->pNext
delete pHead
pHead=pTemp
}
pHead = NULL
return 0
}
// 渡船过程, 递规调用函数FindNext(...)
BOOL Process(QUESTION* pQuest)
{
if (FindNext(pQuest))
{
QUESTION* pNew = new QUESTION
pNew->riverSide1.wildMan = pQuest->riverSide1.wildMan + pQuest->boat.wildMan*(pQuest->side)
pNew->riverSide1.churchMan = pQuest->riverSide1.churchMan + pQuest->boat.churchMan*(pQuest->side)
pNew->riverSide2.wildMan = 3 - pNew->riverSide1.wildMan
pNew->riverSide2.churchMan = 3 - pNew->riverSide1.churchMan
pNew->side = (-1)*pQuest->side
pNew->pPrev = pQuest
pNew->pNext = NULL
pNew->boat.wildMan = 0
pNew->boat.churchMan = 0
pQuest->pNext = pNew
if (pNew->riverSide2.wildMan==3 &&pNew->riverSide2.churchMan==3)
return TRUE// 完成
return Process(pNew)
}
else
{
QUESTION* pPrev = pQuest->pPrev
if (pPrev == NULL)
return FALSE// 无解
delete pQuest
pPrev->pNext = NULL
return Process(pPrev)// 返回其父节点重新再找
}
return TRUE
}
// 判断有否下一个渡河 *** 作, 即根据比较算符找出可以接近目标节点的 *** 作
// 算符共5个: 1野/ 1牧 / 1野1牧 / 2野 / 2牧
BOOL FindNext(QUESTION* pQuest)
{
// 基本规则
// 渡船的优先顺序: 甲岸运多人优先, 野人优先乙岸运少人优先, 牧师优先.
static BOAT boatState[5]// 5个算符
if (pQuest->side == -1)
{
boatState[0].wildMan = 2
boatState[0].churchMan = 0
boatState[1].wildMan = 1
boatState[1].churchMan = 1
boatState[2].wildMan = 0
boatState[2].churchMan = 2
boatState[3].wildMan = 1
boatState[3].churchMan = 0
boatState[4].wildMan = 0
boatState[4].churchMan = 1
}
else
{
boatState[0].wildMan = 0
boatState[0].churchMan = 1
boatState[1].wildMan = 1
boatState[1].churchMan = 0
boatState[2].wildMan = 0
boatState[2].churchMan = 2
boatState[3].wildMan = 1
boatState[3].churchMan = 1
boatState[4].wildMan = 2
boatState[4].churchMan = 0
}
int i// 用来控制算符
if (pQuest->boat.wildMan == 0 &&pQuest->boat.churchMan == 0) // 初始状态, 第一次渡河时
i = 0// 取算符1
else
{
for (i=0i<5i++) // 扩展同一节点时, 已经用过的算符不再用, 按优先级来
if (pQuest->boat.wildMan == boatState[i].wildMan &&pQuest->boat.churchMan == boatState[i].churchMan)
break
i++
}
if (i <5)
{
int j
for (j=ij<5j++)
{
int nWildMan1 = pQuest->riverSide1.wildMan + boatState[j].wildMan * pQuest->side
int nChurchMan1 = pQuest->riverSide1.churchMan + boatState[j].churchMan * pQuest->side
int nWildMan2 = 3 - nWildMan1
int nChurchMan2 = 3 - nChurchMan1
// 判断本次 *** 作的安全性, 即牧师数量>=野人或牧师数为0
if ((nWildMan1 <= nChurchMan1 || nChurchMan1 == 0) &&
(nWildMan2 <= nChurchMan2 || nChurchMan2 == 0) &&
nWildMan1 >=0 &&nChurchMan1 >=0 &&nWildMan2 >=0 &&nChurchMan2 >= 0)
{
// 本 *** 作是否重复上次 *** 作,注意方向不同
if (pQuest->pPrev != NULL)
{
if (pQuest->pPrev->boat.wildMan == boatState[j].wildMan &&
pQuest->pPrev->boat.churchMan == boatState[j].churchMan)
continue
}
break// 该 *** 作可行, 推出循环，只找出当前最优节点
}
}
if (j <5)
{
pQuest->boat.wildMan = boatState[j].wildMan
pQuest->boat.churchMan = boatState[j].churchMan
return TRUE
}
}
return FALSE
}
程序过程是没问题的,只是在函数内声明的局部变量与全局变量同名,造成在函数内全局变量不起作用,在函数
int
boatf(int
im,int
ic,int
ii)
中,由于形参局部变量与全局变量同名,实际在该函数中起作用的只是局部变量,再加上函数里没有把局部变量运算后的值赋给全局变量,所以函数运行结束后,全局变量的值与函数运行前的值一样.在整个程序运行过程中,main
函数中的im
,ic的值始终都是3,结果就是一种死循环状态.
答案补充
不过我不清楚你设计从
"右岸到左岸用boatr"
的函数作用是什么.
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）