經(jīng)典的過(guò)河問(wèn)題：一個(gè)人（獵人）帶了：一只雞（羊）伯顶，一條狗（狼）囚灼，一袋米（草），遇到一條河祭衩，河邊有一條船灶体，船太小每次只能帶一樣?xùn)|西，此人如何將自己的三件物品完好的帶到對(duì)岸掐暮？
（注：若是VS2010開(kāi)發(fā)工具源碼復(fù)制可直接運(yùn)行蝎抽，若是其他開(kāi)發(fā)工具，可能要小部分修改路克，源碼核心算法不用改動(dòng)樟结。具體實(shí)現(xiàn)請(qǐng)查看相應(yīng)注釋养交！此文僅供學(xué)習(xí)參考！）
程序源碼：
// CrossRiver.cpp :定義控制臺(tái)應(yīng)用程序的入口點(diǎn)瓢宦。
//開(kāi)發(fā)工具：VS2010旗艦版
//系統(tǒng)環(huán)境：window7旗艦版
//實(shí)現(xiàn)語(yǔ)言：C語(yǔ)言
//作者：柳XX
//班級(jí)：計(jì)算機(jī)XXX班
//學(xué)號(hào)：20XXXXXXXXXX
#include"stdafx.h"
#include
boolisEnd(int [],int );//判斷是否結(jié)束
int_tmain(int argc, _TCHAR* argv[])
{
intA[4]={0,0,0,0};//定義人碎连、狗、雞刁笙、米的初始狀態(tài)破花，此時(shí)四者都在此岸
//定義過(guò)渡狀態(tài)谦趣，包括：人自己過(guò)河疲吸，人載狗過(guò)河，人載雞過(guò)河前鹅，人載米過(guò)河摘悴，四種狀態(tài)。
//注：其中最后的一維用來(lái)標(biāo)記該向量是否已被使用舰绘，使用記為1蹂喻，未使用記為0，在數(shù)組中即是a[x][4]存放的變量捂寿。
inta[4][5]={{1,0,0,0,0},{1,1,0,0,0},{1,0,1,0,0},{1,0,0,1,0}};
//保存輸出的對(duì)應(yīng)步驟的字符串
char* str[4]={"人劃船過(guò)河","人劃船載狗過(guò)河","人劃船載雞過(guò)河","人劃船載米過(guò)河"};
//問(wèn)題描述
printf(">>>>>>>>某日口四，路人甲在河邊遇到了一個(gè)難題:\n");
printf("\t他帶了三件物品：一只狗、一只雞秦陋、一袋米要到河的對(duì)岸去蔓彩，然而河邊的\n");
printf("\t小船載重太小，每次只允許載三件物品里的一件過(guò)河驳概。但是赤嚼，人不在的\n");
printf("\t時(shí)候，雞和米或狗和雞在一邊時(shí)顺又，雞會(huì)去吃米更卒，狗會(huì)去咬雞。\n");
printf(">>>>>>>>那么他該如何過(guò)河才能保證三件物品完好無(wú)損呢稚照？\n");
printf("\n---解---過(guò)河步驟如下：\n");
//記錄步驟
int n=1;
//開(kāi)始進(jìn)行狀態(tài)轉(zhuǎn)移
while(!isEnd(A,4)){
for(int i=0;i<4;i++){
//當(dāng)過(guò)渡狀態(tài)向量未被使用時(shí)
if(!a[i][4]){
//保存轉(zhuǎn)換中間態(tài)
int B[4];
//異或運(yùn)算蹂空，求轉(zhuǎn)換態(tài)
for(int k=0;k<4;k++){
B[k]=A[k]^a[i][k] ;
}
//狀態(tài)（1,0,0,x）是不允許的，此時(shí)人在河的彼岸果录，有沒(méi)有載米過(guò)去腌闯，狗和雞都會(huì)出現(xiàn)問(wèn)題。
//狀態(tài)（0,1,1,x）是不允許的雕憔，此時(shí)人在河的此岸姿骏，有沒(méi)有載米回來(lái)，狗和雞都會(huì)出現(xiàn)問(wèn)題斤彼。
if((!B[1]&&!B[2]&&B[0])||(B[1]&&B[2]&&!B[0]))continue;
//狀態(tài)（1,x,0,0）是不允許的分瘦，此時(shí)人在河的彼岸蘸泻，有沒(méi)有載狗過(guò)去，雞和米都會(huì)出現(xiàn)問(wèn)題嘲玫。
//狀態(tài)（0,x,1,1）是不允許的悦施，此時(shí)人在河的此岸，有沒(méi)有載狗回來(lái)去团，雞和米都會(huì)出現(xiàn)問(wèn)題抡诞。
elseif((!B[2]&&!B[3]&&B[0])||(B[2]&&B[3]&&!B[0]))continue;
//其它狀態(tài)允許
else {
//改變狀態(tài)
for(int j=0;j<4;j++){
A[j]=B[j];
}
//表示該狀態(tài)已被使用
a[i][4]=1;
//輸出對(duì)應(yīng)的步驟描述
printf("\n-%d-%s\n",n,str[i]);//輸出相應(yīng)步驟
//步驟加一
n++;
}
}
//當(dāng)過(guò)渡向量已被使用時(shí)，修改其使用狀態(tài)值土陪，以便于下一次使用昼汗。
else a[i][4]=0;
}
}
printf("\n----------------------此時(shí)，人鬼雀、狗顷窒、雞、米已全部過(guò)河源哩！\n");
system("pause");
//結(jié)束
return 0;
}
boolisEnd(int L[],int n){//判斷是否結(jié)束鞋吉，只要狀態(tài)向量有一個(gè)為零，即還未結(jié)束励烦。
for(int i=0;i
//判斷狀態(tài)向量的各個(gè)值谓着，為零即停止循環(huán)，返回false
if(!L[i])return false;
}
//狀態(tài)向量的各個(gè)值都為1坛掠，這表示四者都已在彼岸赊锚。過(guò)河完成！
return true;
}
運(yùn)行結(jié)果：
