渡河问题

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?

6 o2 r4 L) y& \3 e

程序代码：

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

7 S! j* c+ U) D

#include <stdio.h> #include <stdlib.h> #define MAX 50 + M& a8 m) P; o( L7 Y# Z, W) estruct state 2 `% J* @, p+ P& v* N& O8 V{ ( W; g7 x6 R& [% Q7 g& `) |& ?# e int man,sheep,wolf,cabbage;//0:在起始岸；1：在目的岸 0 _7 m6 z8 o/ q+ K' `4 b" B) r! b int m;//所采取的过河方法，(1--4) # t( T/ U+ w9 a: X0 b: ]& A* s6 K}s[MAX]; int count=0; FILE *fp=fopen("c:\\2.txt","w+");

R8 ?$ D$ E3 _7 O

void main() * W' G2 s$ i- R- @$ d( C# P# d3 e{ void f1(int ),f2();//f1试探递归 s[0].man=s[0].sheep=s[0].wolf=s[0].cabbage=0; 4 G; {, z5 Z, Z$ m( e s[0].m=4; # @/ k% C: I6 o, y; | s[1].man=s[1].sheep=s[1].wolf=s[1].cabbage=0; . }( G$ p% U2 \8 q f1(1); " d% b1 S# m( k" R //f2(); fclose(fp); * x' F. G: j% c! a9 h$ z printf("\n");

} 0 \' p# G. J4 P//用m值决定的方法渡河，成功返回1,否则返回0 int move(int top,int m) * r" O3 a$ O* w$ v! w{ 0 d, J/ D" B- G: ]5 w$ j$ T d switch(m) { : t& U; F, O7 S& { k! Z1 ]% l //人带羊过河 : B% a5 a/ j! W3 v! o+ @) s case 1: //判断人羊是否在同岸 if(s[top].man!=s[top].sheep) ! s. D' C. E" t8 i6 m2 C: [ return 0; s[top].sheep=s[top].man=(s[top].man==1)?0:1; 4 q" p* H+ W$ Q4 Z8 s s[top].m=m;//存储过河方法 % L9 q! v' r$ X0 h break; case 2: if(s[top].man!=s[top].wolf) & Q6 q1 }# R& `! ], g return 0; 7 G U+ C, U5 i) b- O s[top].wolf=s[top].man=(s[top].man==1)?0:1; s[top].m=m;//存储过河方法 break; % F0 H; t$ p& f5 v7 y E( ? case 3: if(s[top].man!=s[top].cabbage) " M+ p+ n6 p8 ]% Q0 f8 S4 _5 A8 ` return 0; * N) A& ?7 x/ Q- u s[top].cabbage=s[top].man=(s[top].man==1)?0:1; s[top].m=m;//存储过河方法 - @2 ?9 |6 K e! S1 e break; . j) b0 z3 Q% x! F" R //人单独过河 case 4: s[top].man=(s[top].man==1)?0:1; s[top].m=m;//存储过河方法 break; " R2 z& t% W' ?; @2 h/ n# s }//switch ; k$ }+ i& A) A3 x+ U' D) W return 1; ) j2 r7 m3 z: m; [}//move //打印过河步骤 void display(int top) 2 }6 _9 p3 h- r# b{ 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); ! I8 w* ^& m e/ i for(i=1;i<=top;i++) * U" A7 U& r1 S& \) W { % c! e' m6 V) ]9 z Z2 I switch(s.m) { case 1: if(s.man==1&&s[i-1].man==0) fprintf(fp,"人带羊从起始岸过河到目的岸\n"); * A, ~( F3 |" X# Z5 v else * U, L, t, V- X" R" c1 d fprintf(fp,"人带羊从目的岸过河到起始岸\n"); ( J3 E9 ]+ {( e' W$ e2 I( S' C break; case 2: - h: m4 _( ^* g% U if(s.man==1&&s[i-1].man==0) ' Z6 K( u: e$ u) v fprintf(fp,"人带狼从起始岸过河到目的岸\n"); else fprintf(fp,"人带狼从目的岸过河到起始岸\n"); ' j. _: |/ }: k4 \+ A/ E break; case 3: - w( V [! ?, |0 f if(s.man==1&&s[i-1].man==0) $ y; V0 j% N) ^ fprintf(fp,"人带菜从起始岸过河到目的岸\n"); else fprintf(fp,"人带菜从目的岸过河到起始岸\n"); " w' x ^+ E% X: W ^; A1 ?5 e9 R1 Y: _ break; % ~ A3 {- F& c) m case 4: 4 V5 ?, H9 ]& I/ C3 | if(s.man==1&&s[i-1].man==0) fprintf(fp,"人单独从起始岸过河到目的岸\n"); 5 x- ^" N& a/ A7 {" c K' z else . t$ \0 ^' ^2 l: `- m5 O fprintf(fp,"人单独从目的岸过河到起始岸\n"); break; }//switch " _& x5 ]6 l+ v9 V+ X fprintf(fp,"state%d: man: %d, sheep: %d,wolf: %d,cabbage: %d\n",i,s.man,s.sheep,s.wolf,s.cabbage); ' {* D& U, ~6 y9 L }//for / Y4 ]" z2 l! E) C! ]2 y/ efprintf(fp,"All ferried successfully!\n"); }//display

3 m+ A; `& B! q

//检查两岸合法性已经有无状态与历史重复性 ; ]& Y- c5 Z4 I% y$ Q! R3 ~int check(int top) { int i; //检查两岸合法性 6 S/ M7 X: Y2 r if((s[top].sheep!=s[top].man&&s[top].cabbage!=s[top].man)|| + r" @$ x) P3 `! G) K2 b. b' P (s[top].wolf!=s[top].man&&s[top].sheep!=s[top].man)) ; |# j! w4 o% y7 j* P return 0; //检查历史重复性 for(i=0;i<top;i++) 1 ^: C5 z7 L# X if(s.man==s[top].man&&s.sheep==s[top].sheep&&s.cabbage==s[top].cabbage&&s.wolf==s[top].wolf) # e, ~ m0 u. S+ J7 }- g% B2 T return 0; //ok return 1; ' `0 }6 k% {) g( e( T} $ h3 J8 J. q- [ b% a% Bvoid f1(int top) { int m; & k% d, N9 k" b( N if(top>0)//0状态(初试状态应该是预先设置好的，所以要做状态1，故，初试top进来应该是1 ) x' H! N) h( _6 Z { //对每次状态分别试探4中方案 for(m=1;m<5;m++) 7 u" a" i; _* x8 u, d { / G+ S0 x7 D G; ]) k% ~0 A! G' _ //每次方案的实施是在上次结果状态上做的 3 U' V' f6 K! K5 q 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; //用方案m移动，同时检查结果 5 K1 c* K' J5 @8 W% i if(move(top,m)&&check(top)) { if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf ) % N: d9 D2 l. Y { 0 d, U2 _$ H$ F7 H9 J g% e8 x1 x& s //打印渡河步骤 ( D+ a+ D) h! v/ t) U ] display(top); % O) z2 \& G4 S, _$ h# V //统计方案个数 count++; - G. |# O, U6 X0 d( |8 d" s fprintf(fp,"count=%d----------------------------\n\n",count); if(count>1000) exit(1); } + K8 L: Q& @1 {' d8 T else f1(top+1); 7 e5 s+ n; S6 ?7 @2 P } ! l4 y. u8 R# u: B# u/ B, V3 ^ }//for }//if(top>=0) }//f1

6 F) {3 h, {% V& R* I; w4 k6 W- F* [

q* a8 w1 l2 N2 |! b& k( vvoid f2() & [* G& U0 l3 c{ int top=0,i; 6 o O4 Y) B0 `; ?0 B* ~( \ //开始时都在起始岸 s[top].man=s[top].sheep=s[top].wolf=s[top].cabbage=0; //未开始渡河 s[top].m=4; + P: {: W- S9 X6 e while(top>=0) : k0 `$ c& ~) \6 C+ J$ Q { if(check(top)) { 9 t' e- f: |. l if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf ) / j/ g' L. q" Y4 f% Z( ^ { " J$ W4 W5 }3 f8 ] @ //打印渡河步骤 display(top); //统计方案个数 ! u( J5 `/ d) |" H0 ]8 N6 D! j count++; ) U! Y2 R7 f% Q$ H$ k) ]. U9 c fprintf(fp,"count=%d----------------------------\n\n",count); if(count>1000) exit(1); //回溯 while(top>=0&&s[top].m>=4) " i1 [) C B" x$ ]* j, O! Q0 L ? top--; if(top>=0) { 3 j7 S% E1 H, W: X0 b9 ^6 h //在上次状态基础上准备做move . {3 d' p% U) `' S0 X+ T8 F) u$ o s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; ! }% _: W1 F {/ t* W/ G! \0 [% Y1 Q s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf; i=1; while(s[top].m+i<5&&!move(top,s[top].m+i)) + e: x6 @; `5 x) T9 c$ H2 V i++; }

* S" ^+ l) k# J8 r) e T. D N

} + u6 a# ?4 D2 V4 b else " s: ]3 h/ B4 r& [ F. S, Z S! O { top++; //在上次状态基础上准备做move & h0 |0 N& w" t9 { 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; # r2 r$ {8 L; p- Z5 a. l: d i=1; while(i<5&&!move(top,i)) ' O4 q" U: a( ]3 U1 N G$ K+ U i++; }

} else { 8 r( }" @1 w. g; R0 ]' V //回溯 B9 {4 w0 v! m3 Q) b while(top>=0&&s[top].m>=4) top--; 6 p. K& o0 w5 D K! M' ` if(top>=0) { //在上次状态基础上准备做move 5 t" \7 @2 C2 I4 f: }8 Q0 A 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; # C) d, O: D' r0 p6 c i=1; while(!move(top,s[top].m+i)) 7 z& V$ z% s0 D, a& V4 d O0 J3 t i++; } } / S& `7 u8 R' q3 f3 W }//while * ~4 z% m$ J6 q$ A}//f2 //--------------------------------- 1 r* z% ~# m; I3 ^ F H

sally

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

huashi3483

呵呵，好搭档

lynn324

是用c编的吗?

mnpfc

呵呵，看过了