谢谢楼上啦
找到如下代码:
struct INFO
{
int nSavage; // 岸边野人的数量 开始为3 全部到对岸为0
int nBoanerges; // 岸边传教士的数量 开始为3 全部到对岸为0
int nSide; // 船的位置 在此岸为-1 彼岸为1
int nMoveSavage; // 渡河的野人的数量，用于递归时记录操作状态
int nMoveBoanerges; // 渡河的传教士的数量，用于递归时记录操作状态
INFO* pPrevious;
INFO* pNext;
};
// 判断是否有下一个满足条件的渡河方案
bool GetNextMove(INFO* pInfo)
{
// 渡船的优先顺序
// 此岸数量多优先，野人优先，彼岸数量少优先，传教士优先。
const int nStoreCount = 5;
struct STORE
{
int nSavage;
int nBoanerges;
};
STORE listStore[nStoreCount];
if (pInfo->nSide == -1)
{
listStore[0].nSavage = 2;
listStore[0].nBoanerges = 0;
listStore[1].nSavage = 1;
listStore[1].nBoanerges = 1;
listStore[2].nSavage = 0;
listStore[2].nBoanerges = 2;
listStore[3].nSavage = 1;
listStore[3].nBoanerges = 0;
listStore[4].nSavage = 0;
listStore[4].nBoanerges = 1;
}
else
{
listStore[0].nSavage = 0;
listStore[0].nBoanerges = 1;
listStore[1].nSavage = 1;
listStore[1].nBoanerges = 0;
listStore[2].nSavage = 0;
listStore[2].nBoanerges = 2;
listStore[3].nSavage = 1;
listStore[3].nBoanerges = 1;
listStore[4].nSavage = 2;
listStore[4].nBoanerges = 0;
}
int iStart;
if (pInfo->nMoveSavage == 0 && pInfo->nMoveBoanerges == 0)
{
iStart = 0;
}
else
{
for (iStart=0; iStart<nStoreCount; iStart++)
{
if (pInfo->nMoveSavage == listStore[iStart].nSavage && pInfo->nMoveBoanerges == listStore[iStart].nBoanerges)
break;
}
iStart++;
}
if (iStart < nStoreCount)
{
int i;
for (i=iStart; i<nStoreCount; i++)
{
int nSideSavage = pInfo->nSavage + listStore.nSavage * pInfo->nSide;
int nSideBoanerges = pInfo->nBoanerges + listStore.nBoanerges * pInfo->nSide;
int nBesideSavage = 3 - nSideSavage;
int nBesideBoanerges = 3 - nSideBoanerges;
// 传教士数量大于等于野人或为零
if ((nSideSavage<=nSideBoanerges || nSideBoanerges == 0) &&
(nBesideSavage<=nBesideBoanerges || nBesideBoanerges == 0) &&
nSideSavage>=0 && nSideBoanerges>=0 && nBesideSavage>=0 && nBesideBoanerges>=0)
{
// 如果本此解等于上次，放弃
if (pInfo->pPrevious != NULL)
{
if (pInfo->pPrevious->nMoveBoanerges == listStore.nBoanerges &&
pInfo->pPrevious->nMoveSavage == listStore.nSavage)
continue;
}
break;
}
}
if (i < nStoreCount)
{
pInfo->nMoveSavage = listStore.nSavage;
pInfo->nMoveBoanerges = listStore.nBoanerges;
return true;
}
}
return false;
}
// 递归函数
bool Ship(INFO* pInfo)
{
if (GetNextMove(pInfo))
{
INFO* pNew = new INFO;
pNew->nSavage = pInfo->nSavage + pInfo->nMoveSavage * (pInfo->nSide);
pNew->nBoanerges = pInfo->nBoanerges + pInfo->nMoveBoanerges * (pInfo->nSide);
pNew->nSide = (pInfo->nSide) * (-1);
pNew->pPrevious = pInfo;
pNew->pNext = NULL;
pNew->nMoveSavage = 0;
pNew->nMoveBoanerges = 0;
pInfo->pNext = pNew;
if (pNew->nSavage == 0 && pNew->nBoanerges == 0) return true; // 完成
return Ship(pNew);
}
else
{
INFO* pPre = pInfo->pPrevious;
if (pPre == NULL) return false; // 无解
delete pInfo;
pPre->pNext = NULL;
return Ship(pPre);
}
return true;
}
int main(int argc, char* argv[])
{
INFO* pHead = new INFO;
pHead->nSavage = 3;
pHead->nBoanerges = 3;
pHead->nSide = -1;
pHead->pPrevious = NULL;
pHead->pNext = NULL;
pHead->nMoveSavage = 0;
pHead->nMoveBoanerges = 0;
if (Ship(pHead))
{
printf("渡河过程如下：\n");
INFO* pInfo = pHead;
while (pInfo->pNext)
{
printf("渡河方向：%s 人数：野人%d - 传教士%d 此岸野人数：%d, 传教士数：%d\n",
(pInfo->nSide == -1) ? "-->" : "<--", pInfo->nMoveSavage,
pInfo->nMoveBoanerges, pInfo->nSavage, pInfo->nBoanerges);
pInfo = pInfo->pNext;
}
printf("渡河完成。");
}
else
{
printf("此题无解！");
}
// 删除链表
while (pHead)
{
INFO* pTemp = pHead->pNext;
delete pHead;
pHead=pTemp;
}
pHead = NULL;
printf("请结束程序。");
return 0;
}
程序结果
渡河过程如下：
渡河方向：--> 人数：野人2 - 传教士0 此岸野人数：3, 传教士数：3
渡河方向：<-- 人数：野人1 - 传教士0 此岸野人数：1, 传教士数：3
渡河方向：--> 人数：野人2 - 传教士0 此岸野人数：2, 传教士数：3
渡河方向：<-- 人数：野人1 - 传教士0 此岸野人数：0, 传教士数：3
渡河方向：--> 人数：野人0 - 传教士2 此岸野人数：1, 传教士数：3
渡河方向：<-- 人数：野人1 - 传教士1 此岸野人数：1, 传教士数：1
渡河方向：--> 人数：野人0 - 传教士2 此岸野人数：2, 传教士数：2
渡河方向：<-- 人数：野人1 - 传教士0 此岸野人数：2, 传教士数：0
渡河方向：--> 人数：野人2 - 传教士0 此岸野人数：3, 传教士数：0
渡河方向：<-- 人数：野人0 - 传教士1 此岸野人数：1, 传教士数：0
渡河方向：--> 人数：野人1 - 传教士1 此岸野人数：1, 传教士数：1
渡河完成。请结束程序。Press any key to continue
