渡河问题

sally

渡河问题

3 e# w+ X/ I% Y7 i0 C

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?

7 V; @* w) c l* p0 P* m

程序代码：

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

9 L+ f3 ]5 p: e+ h+ g

#include <stdio.h> 3 q7 H. R* s1 D9 h#include <stdlib.h> 8 a2 n( v1 p* v) F ]4 `; [, C#define MAX 50 % `" Y% o+ l3 i e4 T& mstruct state 1 F/ f% r4 J+ r1 f{ int man,sheep,wolf,cabbage;//0:在起始岸；1：在目的岸 int m;//所采取的过河方法，(1--4) 5 G" l3 q2 \: K6 Q4 t}s[MAX]; int count=0; 0 a) ~5 ~+ ~3 H m' E# Q$ b2 m& [FILE *fp=fopen("c:\\2.txt","w+");

0 y2 ^4 U6 r9 e. j6 Z

void main() " p# a! e, k) [( I; t{ - L4 G; W) T6 Z6 P void f1(int ),f2();//f1试探递归 5 p. @; }4 o. _" Q0 { J s[0].man=s[0].sheep=s[0].wolf=s[0].cabbage=0; s[0].m=4; 4 v/ E& k. C! g/ W5 O; z, C! y s[1].man=s[1].sheep=s[1].wolf=s[1].cabbage=0; f1(1); - q' V+ n% y0 ^9 M( G- @% h) d5 r //f2(); / [, j: g- K! g6 j! L fclose(fp); printf("\n");

} ' t7 E8 P/ G- \: g$ F, T" S, L0 D" M% Y: F//用m值决定的方法渡河，成功返回1,否则返回0 $ `: s/ D* B3 R4 Oint move(int top,int m) { " E, ~3 W5 K3 w# s; v1 U switch(m) - Y* L0 e+ I4 F( u { //人带羊过河 Q7 D5 b- S- v- ^: x9 v case 1: 3 r- n- X. i/ S5 D, G4 x //判断人羊是否在同岸 ( |. d6 |) z! Y. `8 J if(s[top].man!=s[top].sheep) * @7 N* l8 A7 b R- T return 0; & e8 w' X7 {) O s[top].sheep=s[top].man=(s[top].man==1)?0:1; 9 q3 S& w: L& V% p# Q s[top].m=m;//存储过河方法 0 b9 n7 \4 L- ~# c' e break; 2 v% y4 g, Q$ z# {* W6 d; e, N! I6 _ case 2: + O+ p) g5 k* F9 |9 x! F) c if(s[top].man!=s[top].wolf) return 0; s[top].wolf=s[top].man=(s[top].man==1)?0:1; ' E: Z: E4 G H% \ s[top].m=m;//存储过河方法 break; 6 `0 i. U {7 K% v2 J1 t case 3: . h1 w0 X$ e' B; B( B+ H4 f4 M if(s[top].man!=s[top].cabbage) " Z, O+ s' B+ y2 l return 0; s[top].cabbage=s[top].man=(s[top].man==1)?0:1; # [3 i% J& [ p, P s[top].m=m;//存储过河方法 9 _+ u5 S& T) m* j8 y; J+ c break; 5 C8 A; A. g# R; p //人单独过河 case 4: 6 Q; L" n$ d& @3 W s[top].man=(s[top].man==1)?0:1; s[top].m=m;//存储过河方法 / c2 _1 _# c/ N3 f' J: G; @5 d break; }//switch return 1; 0 g+ N0 k) E6 K' x& w. _9 n) [}//move Z! |! `) ]% e o" S5 ]8 k, Y: d//打印过河步骤 0 I6 r/ Z8 Y0 H4 A# @4 h, i3 l( Ivoid display(int top) 6 R, q6 I/ B# M* r{ int i=0; * H* s* \1 x1 f' I: i% H& q* s( t fprintf(fp,"state%d: man: %d, sheep: %d,wolf: %d,cabbage: %d\n",i,s.man,s.sheep,s.wolf,s.cabbage); for(i=1;i<=top;i++) / ?- E @2 O2 r; I0 N9 r { switch(s.m) 5 w4 {8 u k7 |; S5 o3 R3 h { 7 k5 ~: K" q K+ @ s: @3 E2 z' E case 1: if(s.man==1&&s[i-1].man==0) fprintf(fp,"人带羊从起始岸过河到目的岸\n"); else fprintf(fp,"人带羊从目的岸过河到起始岸\n"); break; 1 i0 W6 O& A" `. A( ]& j case 2: - X' c" S% d& x/ y3 O6 J! F if(s.man==1&&s[i-1].man==0) fprintf(fp,"人带狼从起始岸过河到目的岸\n"); 7 c- ]8 Q. w, U7 U% i else fprintf(fp,"人带狼从目的岸过河到起始岸\n"); break; ; A( [& x- L+ F) W2 p- e1 Y case 3: + l. \8 J6 N `- {8 i) ~ if(s.man==1&&s[i-1].man==0) ) A7 V, F4 I* ~- ^/ j% A fprintf(fp,"人带菜从起始岸过河到目的岸\n"); ! X- M# r. I% X6 D else ' }3 _+ C; z* f! R fprintf(fp,"人带菜从目的岸过河到起始岸\n"); break; case 4: 2 n9 T1 Z4 V. s1 e' O if(s.man==1&&s[i-1].man==0) 0 o/ H8 D6 Z) M. m3 K. s, k fprintf(fp,"人单独从起始岸过河到目的岸\n"); / Y& C6 i* x/ I! l% l& _$ ^8 q& z else fprintf(fp,"人单独从目的岸过河到起始岸\n"); break; 8 T4 x2 P" o [ }//switch 6 `) d8 q( U4 q4 A fprintf(fp,"state%d: man: %d, sheep: %d,wolf: %d,cabbage: %d\n",i,s.man,s.sheep,s.wolf,s.cabbage); ; C: v0 ~9 N r4 B }//for 2 t& U4 Y4 n* ~$ T5 }% Z) Ufprintf(fp,"All ferried successfully!\n"); ( Z0 n$ w7 f5 @. P* X, t( S2 }}//display

//检查两岸合法性已经有无状态与历史重复性 8 r" f% V5 Q: n- c( Lint check(int top) { 4 K9 o; f8 ~: H8 N5 H( ?0 I. o int i; //检查两岸合法性 if((s[top].sheep!=s[top].man&&s[top].cabbage!=s[top].man)|| - a9 R w+ j) z3 ] (s[top].wolf!=s[top].man&&s[top].sheep!=s[top].man)) return 0; //检查历史重复性 2 f; e( H' s; x: Q for(i=0;i<top;i++) . e {7 q; ?; Q2 N: Y' X if(s.man==s[top].man&&s.sheep==s[top].sheep&&s.cabbage==s[top].cabbage&&s.wolf==s[top].wolf) 8 P1 W: e7 T" b7 e, S; u- f, K return 0; + M& a2 F$ G7 A( h& z //ok : K1 X6 Q7 O! T0 k6 T' I return 1; } void f1(int top) ) C+ V0 t, P$ S9 \{ int m; if(top>0)//0状态(初试状态应该是预先设置好的，所以要做状态1，故，初试top进来应该是1 { //对每次状态分别试探4中方案 for(m=1;m<5;m++) ! H# f* s9 i$ H' Y4 ~! ] { 6 ]% ?3 \ r* N; |, z8 p //每次方案的实施是在上次结果状态上做的 " ^' T: B% [) J$ e+ t% Y s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; ' i% O0 Q6 K4 {5 n6 @" N& ^ s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf; //用方案m移动，同时检查结果 if(move(top,m)&&check(top)) { # {. c& o: X7 R if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf ) # M8 z5 V* Y: i2 Q6 l0 i8 w) f { //打印渡河步骤 o0 l; W0 s' D/ _" f display(top); //统计方案个数 count++; fprintf(fp,"count=%d----------------------------\n\n",count); " b; Y3 A$ [) [5 C+ K K if(count>1000) exit(1); / K9 k5 F$ H& ]1 V+ C6 | } + }$ O4 S( t4 O5 J8 g: N else f1(top+1); , W! r; t9 M0 a7 h( y K } # Y6 {2 u3 F2 x- Y }//for }//if(top>=0) ; i6 p' B7 ]1 g: z& W6 n- l7 Q}//f1

# t" Z6 X! |/ h9 l

) W0 L _% Q6 y0 z2 y7 U

: d1 G4 m! f4 l' O; ?& Avoid f2() " v" }( F, d8 p$ x# k; o& m$ u8 M- _{ 0 l7 E' w/ i' j+ X* U/ a int top=0,i; //开始时都在起始岸 5 H6 O/ @" N) I7 L1 A8 O( C s[top].man=s[top].sheep=s[top].wolf=s[top].cabbage=0; : F/ D e* M/ _ //未开始渡河 7 E7 m; p* B" y3 ~ s[top].m=4; ( q+ S3 K5 F: {' M/ P1 c8 N0 [ while(top>=0) ( `$ ~- S0 h/ Y( t) p. j; @0 D1 b { ) _, G4 x# _% c3 c; L6 ~" d if(check(top)) { 4 d" N9 u" ]: L' P5 `# d" d; D if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf ) { : N9 d9 n, _$ @% A; m. ^( } //打印渡河步骤 display(top); 8 v1 L! |2 ~$ d* }( b3 X& U- h5 Z //统计方案个数 count++; 9 J I Z8 A2 ]8 g. R. C0 P fprintf(fp,"count=%d----------------------------\n\n",count); if(count>1000) exit(1); ) P; ?3 w. \9 j //回溯 while(top>=0&&s[top].m>=4) 7 S* f+ B- ^9 h+ C top--; if(top>=0) { - j, t" e9 b4 S" {6 K* X! J; ] //在上次状态基础上准备做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; ) x9 u& Z( |" D1 o* r. ? i=1; ) m; V. {9 v& J) z while(s[top].m+i<5&&!move(top,s[top].m+i)) & G( y5 [1 P+ t! D% S- n i++; }

0 a2 [9 E- T: v6 u. [" |8 d, U

} else ( r' v0 c4 s4 V5 X/ w" c { top++; % V5 G0 t: [* f0 l b8 o //在上次状态基础上准备做move s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; 4 R' p: V: c- d9 d! m& w) A+ \) n# I s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf; 1 O' @5 `; B/ |, Z8 @. f i=1; while(i<5&&!move(top,i)) 8 S' q0 Z; C" [& c' l i++; }

} # t4 q6 _/ q( x2 n0 }$ b else ) O) ?4 m8 j% W# ^" l3 ] { //回溯 while(top>=0&&s[top].m>=4) top--; & i# p2 z2 }+ I4 _ if(top>=0) % F" h: p" _9 o _! l! S { //在上次状态基础上准备做move + n R/ `/ J% P9 E2 k+ p+ m- \ s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; 2 g+ R+ X% |& W& w3 t8 w s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf; i=1; while(!move(top,s[top].m+i)) / `' [# H2 X% a: O1 k i++; / ^$ R+ W. x, E! \9 @( u# q f# a } } 8 f* J! F2 }7 b/ x4 h# h/ x5 }$ C }//while }//f2 & f& P3 x* _6 P& o1 G" b" @//---------------------------------

sally

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

huashi3483

呵呵，好搭档

lynn324

是用c编的吗?

mnpfc

呵呵，看过了