渡河问题

sally

渡河问题

A wolf, a goat and a cabbage are on one bank of a river. A ferryman wants to take them across, but since his boat is small, he can take only one of them at a time. For obvious reasons, neither the wolf and the goat nor the goat and the cabbage can be left unguarded. How is the ferryman going to get them across the river?

' v, x+ d; K3 `4 ?, L; E

程序代码：

//以下程序在Win98＋vc6.0运行通过

#include <stdio.h> #include <stdlib.h> # j5 ~ Y/ n O9 z9 J! ?#define MAX 50 : O+ Y0 h2 R( Y7 L; [, a, P B; lstruct state { int man,sheep,wolf,cabbage;//0:在起始岸；1：在目的岸 * N3 U1 T+ d5 J int m;//所采取的过河方法，(1--4) % P; u6 @. _9 G) e5 `}s[MAX]; ; i8 i) P' B2 x1 A) uint count=0; FILE *fp=fopen("c:\\2.txt","w+");

, N+ i* K9 h' j7 b" U( m$ H8 e( A

void main() 8 w$ R5 e! z. d& I7 T+ s! ^2 I* i{ ) k9 y( C6 ?' \/ C8 ` void f1(int ),f2();//f1试探递归 ' v( a9 H. {/ B( W3 W( d+ Y s[0].man=s[0].sheep=s[0].wolf=s[0].cabbage=0; . ^8 H3 e4 }( U( b7 F9 H% {$ W* z s[0].m=4; 7 m) g) |7 o( e o3 ^3 o+ W5 ~5 D s[1].man=s[1].sheep=s[1].wolf=s[1].cabbage=0; 0 _ e! I" w1 u* {0 T8 w8 _' f8 a/ T f1(1); //f2(); . X: D; C. s0 ?2 F* M/ j fclose(fp); printf("\n");

} ! v! u# d, I" f9 }% m) m0 B* M4 M//用m值决定的方法渡河，成功返回1,否则返回0 8 c: h7 V! X3 f9 ~8 f dint move(int top,int m) 5 |9 S8 k' x1 U$ x* n* m/ k8 x{ switch(m) : k) N$ E' m# N# L5 k5 w { //人带羊过河 case 1: //判断人羊是否在同岸 2 K- Z6 ]0 h w4 K% Y, X3 b if(s[top].man!=s[top].sheep) return 0; s[top].sheep=s[top].man=(s[top].man==1)?0:1; # t j& V# C- C4 G* n4 m6 f s[top].m=m;//存储过河方法 break; case 2: * }% i }* O0 |4 h% c- w; _& q if(s[top].man!=s[top].wolf) 7 J I* V; Z* E9 O5 P return 0; s[top].wolf=s[top].man=(s[top].man==1)?0:1; $ X! L4 A7 ~/ q* p- y s[top].m=m;//存储过河方法 break; case 3: 7 S2 w% R. d9 s" w if(s[top].man!=s[top].cabbage) 6 o/ n$ \1 _5 F* t/ H return 0; s[top].cabbage=s[top].man=(s[top].man==1)?0:1; s[top].m=m;//存储过河方法 break; ' K, {. W8 R0 ]3 s& e0 Z% h9 C6 g //人单独过河 : \+ P i. V M case 4: s[top].man=(s[top].man==1)?0:1; s[top].m=m;//存储过河方法 break; : ]! m9 V' w0 S }//switch 0 [4 x& p8 H! Z5 s) g: \3 ?: ~ return 1; }//move //打印过河步骤 void display(int top) { int i=0; fprintf(fp,"state%d: man: %d, sheep: %d,wolf: %d,cabbage: %d\n",i,s.man,s.sheep,s.wolf,s.cabbage); * [# `" ^7 A. r: }8 s for(i=1;i<=top;i++) { switch(s.m) { + q) O Z+ y% q' o case 1: . O% G' E. v1 y! H3 ?& X9 E if(s.man==1&&s[i-1].man==0) fprintf(fp,"人带羊从起始岸过河到目的岸\n"); 9 w. z7 }! q' |" d; c, {3 ? else fprintf(fp,"人带羊从目的岸过河到起始岸\n"); break; . L+ e0 C: D( | ]" e7 k9 Q case 2: if(s.man==1&&s[i-1].man==0) / b( ^/ m- _, V fprintf(fp,"人带狼从起始岸过河到目的岸\n"); 3 L4 _# u$ t+ z* Y else fprintf(fp,"人带狼从目的岸过河到起始岸\n"); ) I$ D* h) Y) [7 t- k break; . V% ~2 z, Q. ^0 R3 S% ] case 3: if(s.man==1&&s[i-1].man==0) ! i5 F' ~& @/ h5 l% I( X6 f fprintf(fp,"人带菜从起始岸过河到目的岸\n"); else fprintf(fp,"人带菜从目的岸过河到起始岸\n"); , _0 X1 X- n: \ }% \* i break; ( {/ D# G* X& [3 [7 @7 T% v3 u8 S% O) H case 4: 1 S$ B7 |7 |7 A) n% F( t if(s.man==1&&s[i-1].man==0) 4 q' {6 {5 i1 o fprintf(fp,"人单独从起始岸过河到目的岸\n"); else fprintf(fp,"人单独从目的岸过河到起始岸\n"); break; }//switch % F/ L6 c. }& T! F fprintf(fp,"state%d: man: %d, sheep: %d,wolf: %d,cabbage: %d\n",i,s.man,s.sheep,s.wolf,s.cabbage); ; i2 t, P9 l7 {5 d: s }//for / ]/ U, \- s v) y3 `8 R6 Gfprintf(fp,"All ferried successfully!\n"); 3 W0 d: P7 I* P}//display

+ P5 _$ w& W$ Q. {: j

//检查两岸合法性已经有无状态与历史重复性 int check(int top) 9 K2 Q" T0 y6 x/ ^% b( D{ int i; ' n( ?8 | a, O4 e) o//检查两岸合法性 / H6 d* E/ g+ @& @& R! g if((s[top].sheep!=s[top].man&&s[top].cabbage!=s[top].man)|| (s[top].wolf!=s[top].man&&s[top].sheep!=s[top].man)) / d! a! Q" H. u' R6 s return 0; //检查历史重复性 : b8 n8 l6 V. _5 u" _7 X/ q for(i=0;i<top;i++) if(s.man==s[top].man&&s.sheep==s[top].sheep&&s.cabbage==s[top].cabbage&&s.wolf==s[top].wolf) return 0; . n5 X- k+ ~8 |4 Y //ok ) M. E# s5 O, i4 u# B3 u! Y return 1; } void f1(int top) { int m; if(top>0)//0状态(初试状态应该是预先设置好的，所以要做状态1，故，初试top进来应该是1 , \( X3 B5 r! D+ \) v1 l { //对每次状态分别试探4中方案 0 U2 f$ n: a. S for(m=1;m<5;m++) 2 ?( r% e! ^$ J- p. r m- t4 a2 J$ u& p { 4 X' y- m P. `& ?: f& I8 ]5 S) O //每次方案的实施是在上次结果状态上做的 9 L! C* [( U0 ?3 d7 i6 y s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf; 3 x% A1 N) P. I3 c& }, v //用方案m移动，同时检查结果 , \2 Q4 U: g& N4 W) o/ Y- V( Q if(move(top,m)&&check(top)) { & V. Z2 P3 b# E1 d+ j; V if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf ) 3 h0 _; K1 g6 r( P { //打印渡河步骤 & \9 @7 S: t# S" k) m: ]( @ display(top); //统计方案个数 count++; fprintf(fp,"count=%d----------------------------\n\n",count); + b8 L- @* D I3 F2 T' D i if(count>1000) exit(1); ) N% T S/ v" f1 I } ) Z- G# D+ w1 h else f1(top+1); } }//for }//if(top>=0) }//f1

' @$ k! y8 X! S+ Y# c9 x+ h1 ]" K) N

4 o2 \' S0 h( D5 r9 I# R# c

* K# W7 Y r* k0 N5 r6 W: \: yvoid f2() 9 v1 `+ x1 V- L) G9 g$ d+ v ^4 J{ int top=0,i; //开始时都在起始岸 # r9 y. o) i# t7 K+ e) A s[top].man=s[top].sheep=s[top].wolf=s[top].cabbage=0; //未开始渡河 ' K0 s: c) k/ \' Y. ?2 }' v/ z s[top].m=4; while(top>=0) " u5 ^ m) e* K4 ~ { if(check(top)) { if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf ) 9 D* v" }+ B; w { ) |; s I/ z. w //打印渡河步骤 # A8 {) r4 Y9 D1 N display(top); 2 C" `! O$ p2 }: Q0 g. a% ^) z/ p5 r //统计方案个数 count++; 6 L l2 k$ E- ? fprintf(fp,"count=%d----------------------------\n\n",count); if(count>1000) exit(1); 1 i9 X- G( W/ B' } //回溯 while(top>=0&&s[top].m>=4) top--; if(top>=0) { # f l. E1 I% c% @8 i3 L! R //在上次状态基础上准备做move s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; , R4 W, x/ o) K% s s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf; ! _# \" u5 L; y+ r/ Z8 M i=1; while(s[top].m+i<5&&!move(top,s[top].m+i)) ( t. J% V5 w" H# H) }( X( e3 \, \- r i++; }

6 b: j# L8 ~5 Y! R

} J6 i1 r: K% x0 S9 Z else 4 C/ R" @' D, M5 A { % v2 ?# Y: M5 A* A" V( w0 n9 D q top++; . t2 a2 U0 t* W //在上次状态基础上准备做move 6 m; j$ m u4 }1 R' t9 I+ F s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf; i=1; while(i<5&&!move(top,i)) : y( u8 v# r: Z/ y i++; 4 |$ ]! m6 u" a# I5 W2 s3 M }

} * ]6 w0 D* L2 @: Q, J. I$ k else 2 R) j7 Y) w( m8 r& c { //回溯 while(top>=0&&s[top].m>=4) top--; if(top>=0) { //在上次状态基础上准备做move s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf; i=1; while(!move(top,s[top].m+i)) 7 `* _' W) @+ N7 T7 B+ o! f i++; 3 v2 z* `! O8 T5 g% e } 6 e {+ \0 y! X; z3 ~1 i } $ D+ L% u1 O8 [ }//while * j& a' K7 N7 `3 H}//f2 //---------------------------------

mnpfc

呵呵，看过了

lynn324

是用c编的吗?

huashi3483

呵呵，好搭档

sally

也可以转化为图的遍历问题