C语言（过河问题）

50分 标签：c语言 过河 父亲 男孩 女儿
答复：1   浏览：1226   提问时间：2006-11-30 15:55 C语言（过河问题）
有一个警察，抓了一个贼，来到河边要过河。当他们来到河边时，创造河水上涨，只能坐船过河，同时，河边有一对夫妻带着两个儿子和两个女儿也要过河。请你编程输出他们过河的步骤。
限定条件：
（1） 渡口只有一条船，一次只能渡两个人，而且只有大人才干够划船，到河对岸后需要一个人将船送回到河这边。
（2） 贼只能和警察在一块，因为当警察不在身边时，贼就会伤害那对夫妻及他们的孩子。
（3） 贼不敢逃跑。
（4） 当母亲不在女儿身边时，父亲会责骂女儿。
（5） 当父亲不在儿子身边时，结亲也会责骂儿子。

输出成果（部分）：
第1步：警察和贼同时过河
第2步：警察驾船回来（即：将贼独自留在对岸）
第3步：警察和男孩一同时过河
第4步：警察和贼一同驾船回来（即：将男孩一单独留在对岸）
第5步：父亲和男孩二同时过河
第6步：父亲驾船回来（即：将两个男孩留在对岸了）
第7步：父亲和母亲一同过河
第8步：母亲驾船回来（即：将父亲和两个男孩留在对岸了）
…
编程提示：
可以分辨用8个不同的数来表现这8个人，如警察用128、贼用64、父亲用32、男孩一用16、男孩二用8、母亲用4、女儿一用2、女儿二用1表现。初始状态为255（即128＋64＋32＋16＋8＋4＋2＋1的和），全部过河后的状态为0。每次两人过河后，从总数里减掉表现他们的数，回来一个人再将表现他（她）的数加到总数里。
可以用递归来做。 共0条评论... 最佳答案 此答案由提问者自己选择，并不代表爱问知识人的观点 揪错 ┆ 评论 ┆ 举报
云淡风轻
[学者] 程序我做完了，但至少要50的悬赏分。
只是对我的劳动的起码的尊重，下边给你贴几个，由于不同的规矩排列次序，产生的几种不同的解。

//pastriver.c
/***********************************
This code is used to answer the past
river question.
Note: 12/2/2006
coded by YunDanFengQing
***********************************/


#include <stdio.h>

#define MAX 100

typedef enum BOOL
{
FALSE = 0, TRUE = 1
}BOOL;

typedef union Items
{
struct
{
char boy : 1;
char girl : 1;
char father : 1;
char mother : 1;
char police : 1;
char thief : 1;
char : 0;
};
char c;
}*pItems, Items;

struct
{
Items item[MAX];
int boat[MAX];
int length;
}stack;

int Boat[2];
Items ItemMask[12];
char* msg[4] = { "comes back single.", "comes back together.",
"pasts the river single.", "past the river together." };
char* msgn[12] = { "father", "mother", "police", "thief",
"police and the thief", "police and the father",
"police and the mother", "police and the boy",
"police and the girl", "father and the boy",
"mother and the girl", "father and the mother"};

BOOL IsLegal ( Items item )
{
Items t1, t2, t3;
Items t4, t5, t6;
t1.c = 0, t2.c = 0, t3.c = 0;
t4.c = 0, t5.c = 0, t6.c = 0;

t1.girl = 1, t1.father = 1, t1.mother = 0;
t4.girl = 1, t4.father = 1, t4.mother = 1;
t2.boy = 1, t2.father = 0, t2.mother = 1;
t5.boy = 1, t5.father = 1, t5.mother = 1;
t3.thief = 1, t3.police = 0;
t6.thief = 1, t6.police = 1;

if (( t4.c & item.c ) == t1.c ) {
return FALSE;
}
if (( t5.c & item.c ) == t2.c ) {
return FALSE;
}
if ((( item.c & t6.c ) == t3.c ) && (( item.c ^ t3.c ) != 0)) {
return FALSE;
}
return TRUE;
}

BOOL IsInStack ( Items item, int boat )
{
int i = 0;
for ( i = 0; i < stack.length; ++i ) {
if (( item.c == stack.item[i].c ) && ( boat == stack.boat[i] )) {
return TRUE;
}
}
return FALSE;
}

BOOL IsStackFull ()
{
return stack.length >= MAX ? TRUE : FALSE;
}

BOOL Rule ( pItems itemL, pItems itemR, int boat, int i )
{
Items left, right;
if ( 0 == boat ) {
left.c = itemL->c;
right.c = itemR->c;
}
else {
left.c = itemR->c;
right.c = itemL->c;
}

if (( left.c & ItemMask[i].c ) != ItemMask[i].c ) {
return FALSE;
}
left.c ^= ItemMask[i].c;
right.c ^= ItemMask[i].c;

if ( 0 == boat ) {
itemL->c = left.c;
itemR->c = right.c;
}
else {
itemL->c = right.c;
itemR->c = left.c;
}
return TRUE;
}

BOOL PastRiver ( Items itemL, Items itemR, int boat )
{
Items newL, newR;
int i = 0, j = 0;

if ( itemL.c == 0 ) {
return TRUE;
}

for ( i = 0; i < 12; ++i ){
newL.c = itemL.c, newR.c = itemR.c;
if ( TRUE == Rule ( &newL, &newR, boat, i )) {
if (( TRUE == IsLegal (newL)) && ( TRUE == IsLegal (newR) )) {
if (( FALSE == IsInStack ( newL, boat )) && ( FALSE == IsStackFull() )) {
stack.item[stack.length].c = newL.c;
stack.boat[stack.length] = boat;
stack.length ++;
if ( TRUE == PastRiver ( newL, newR, Boat[boat] )) {
if (( 0 == boat ) && ( i < 4 )) {
j = 2;
}
if (( 0 == boat ) && ( i >= 4 )) {
j = 3;
}
if (( 1 == boat ) && ( i < 4 )) {
j = 0;
}
if (( 1 == boat ) && ( i >= 4 )) {
j = 1;
}
printf ( "The %s %s\n", msgn[i], msg[j] );
return TRUE;
}
}
}
}
}
return FALSE;
}

void Init()
{
int i = 0;
stack.length = 0;
Boat[0] = 1;
Boat[1] = 0;
for ( i = 0; i < 12; ++i ) {
ItemMask[i].c = 0;
}
ItemMask[0].father = 1;
ItemMask[1].mother = 1;
ItemMask[2].police = 1;
ItemMask[3].thief = 1;
ItemMask[4].police = 1, ItemMask[4].thief = 1;
ItemMask[5].police = 1, ItemMask[5].father = 1;
ItemMask[6].police = 1, ItemMask[6].mother = 1;
ItemMask[7].police = 1, ItemMask[7].boy = 1;
ItemMask[8].police = 1, ItemMask[8].girl = 1;
ItemMask[9].father = 1, ItemMask[9].boy = 1;
ItemMask[10].mother = 1, ItemMask[10].girl = 1;
ItemMask[11].father = 1, ItemMask[11].mother = 1;
}


int main ()
{
Items itemL, itemR;
itemL.c = 0, itemR.c = 0;
itemL.father = 1, itemL.mother = 1;
itemL.boy = 1, itemL.girl = 1;
itemL.police = 1, itemL.thief = 1;

Init();
stack.item[stack.length].c = itemL.c;
stack.boat[stack.length] = 1;
stack.length++;
if ( FALSE == PastRiver ( itemL, itemR, 0 )) {
printf ("BAD!!\n");
}
getchar();
return 0;
}screen.width*0.35) this.width=screen.width*0.40"> 答复：2006-12-02 14:28 提问者对答案的评价： 十分感谢 共1条评论...