問題如下：
一對父母帶着2個女兒和2個兒子，一個警察帶着一個小偷，他們都要過河去對岸。
隻有一條船，每次最多隻能乘坐2個人，并且隻有爸爸、媽媽、警察可以開船。
小偷不能在離開警察的情況下和其他人在一起；兒子不能在沒有爸爸的情況下和媽媽在一起；女兒不能在沒有媽媽的情況下和爸爸在一起。
遞歸法實作如下：
#include <stdio.h>
#define TRUE 1
#define FALSE 0
class RiverCrosser
{
#define PERSON_NUM 8
#define START_STATE 0
#define FINISH_STATE 1
enum PersonNo
{
DAD,
BOY1,
BOY2,
MUM,
GIRL1,
GIRL2,
POLICE,
THIEF,
BOAT
} ;
struct Record
{
#define RECORD_MAX (1000)
Record()
{
initRecord();
}
void recordState( int state )
{
__beginState[__steps] = state;
++__steps;
}
bool isStateExist( int state ) const //判斷目前狀态是否已經被記錄
{
for ( int i = 0; i < __steps; ++i )
{
if ( state == __beginState[i] )
{
return true;
}
}
return false;
}
void initRecord() //初始化記錄數組
{
__steps = 1;
__beginState[0] = 0x1ff;
}
int __steps;
int __beginState[RECORD_MAX]; //記錄發生過的狀态
};
public:
//初始狀态:人和船都在河岸的這邊
RiverCrosser():_begin(0x1ff)
{
}
int crossing(); //遞歸完成渡河操作
static void printfInfo( int state ); //輸出河岸這邊的資訊
private:
bool isCrossOK() const; //判斷渡河是否成功
static bool isAllowed( int state ); //此次渡河是否允許
static bool canCross( int i ) //是否有能力渡河（隻有爸爸媽媽警察能開船）
{
return (i == POLICE) || (i == DAD) || (i == MUM);
}
int _begin; //高位表示船的位置
Record _record;
const static int personMask[];
const static char * personName[];
};
const int RiverCrosser::personMask[] = { 1, 2, 4, 8, 16, 32, 64, 128, 256 } ;
const char* RiverCrosser::personName[] = { "DAD-----", "BOY1----", "BOY2----", "MUM-----", "GIRL1---", "GIRL2---",
"POLICE--", "THIEF---", "BOAT----", "****----" } ;
///
bool RiverCrosser::isCrossOK() const
{
return _begin == 0;
}
bool RiverCrosser::isAllowed( int state )
{
if ( (state & personMask[THIEF]) && !(state & personMask[POLICE]) ) //小偷在且警察不在
{
if ( state & (~personMask[THIEF]&0xff) )
{
return false;
}
}
if ( (state & personMask[DAD]) && !(state & personMask[MUM]) ) //爸爸在并且媽媽不在
{
if ( (state & personMask[GIRL1]) || (state & personMask[GIRL2] ) ) //至少有一個女兒在
{
return false;
}
}
if ( (state & personMask[MUM]) && !(state & personMask[DAD]) ) //媽媽在并且爸爸不在
{
if ( (state & personMask[BOY1] ) || (state & personMask[BOY2] ) ) //至少有一個兒子在
{
return false;
}
}
return true;
}
void RiverCrosser::printfInfo( int state )
{
for ( int i = 0; i <= PERSON_NUM; ++i )
{
if ( state & personMask[i] )
{
printf( personName[i] );
}
else
{
printf( personName[PERSON_NUM+1] );
}
}
printf( " " );
}
//遞歸完成每次過河操作
int RiverCrosser::crossing()
{
if ( isCrossOK() ) //渡河是否成功
{
return TRUE;
}
//臨時儲存目前狀态
const int oldBegin = _begin;
const int oldEnd = oldBegin ^ 0x1ff;
for ( int P1 = 0; P1 < PERSON_NUM; ++P1 )
for ( int P2 = 0; P2 <= P1; ++P2 ) //P1 == P2時,表示隻有一個人渡河
{
int currState[2] = { oldBegin, oldBegin } ;
currState[(oldBegin&personMask[BOAT])>>BOAT] = oldEnd;
if ( (currState[START_STATE] & personMask[P1]) && (currState[START_STATE] & personMask[P2]) && ( canCross(P1)||canCross(P2) ) )
{
currState[START_STATE] ^= (personMask[P1] | personMask[BOAT]);
currState[FINISH_STATE] ^= (personMask[P1] | personMask[BOAT]);
if ( P1 != P2 )
{
currState[START_STATE] ^= personMask[P2];
currState[FINISH_STATE] ^= personMask[P2];
}
if ( isAllowed( currState[START_STATE] ) && isAllowed( currState[FINISH_STATE] ) ) //過河後是否符合要求
{
//允許渡河
if ( _record.isStateExist( currState[(oldEnd&personMask[BOAT])>>BOAT] ) )//判斷狀态是否存在
{
//忽略此次渡河
continue;
}
//成功渡河,修改目前狀态,并做記錄
_begin = currState[(oldEnd&personMask[BOAT])>>BOAT];
_record.recordState( _begin ); //記錄
if ( crossing() ) //準備下一次渡河
{
//輸出渡河經過
printfInfo( oldBegin );
return TRUE;
}
}
}
}
return FALSE;
}
int main(int argc, char* argv[])
{
RiverCrosser riverCross;
riverCross.crossing();
return 0;
}
P.S. 用遞歸實作，效率可能較低，一時也沒想到好方法。
輸出每次渡河後的狀态（從下往上）：
****----****----****----****----****----****----POLICE--THIEF---BOAT----
****----****----****----****----****----****----****----THIEF---****----
****----****----****----****----****----GIRL2---POLICE--THIEF---BOAT----
****----****----****----****----****----GIRL2---****----****----****----
****----****----****----MUM-----GIRL1---GIRL2---****----****----BOAT----
****----****----****----****----GIRL1---GIRL2---****----****----****----
DAD-----****----****----MUM-----GIRL1---GIRL2---****----****----BOAT----
****----****----****----MUM-----GIRL1---GIRL2---****----****----****----
****----****----****----MUM-----GIRL1---GIRL2---POLICE--THIEF---BOAT----
****----****----****----****----GIRL1---GIRL2---POLICE--THIEF---****----
DAD-----****----****----MUM-----GIRL1---GIRL2---POLICE--THIEF---BOAT----
****----****----****----MUM-----GIRL1---GIRL2---POLICE--THIEF---****----
DAD-----****----BOY2----MUM-----GIRL1---GIRL2---POLICE--THIEF---BOAT----
DAD-----****----BOY2----MUM-----GIRL1---GIRL2---****----****----****----
DAD-----BOY1----BOY2----MUM-----GIRL1---GIRL2---POLICE--****----BOAT----
DAD-----BOY1----BOY2----MUM-----GIRL1---GIRL2---****----****----****----
DAD-----BOY1----BOY2----MUM-----GIRL1---GIRL2---POLICE--THIEF---BOAT----
![與專家面對面：Android開發入門問與答[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)