渡河问题

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?

7 d# h$ B- ?7 F1 [3 p- I1 Q

程序代码：

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

# u* L" F8 ~3 @( t$ R q, u

#include <stdio.h> #include <stdlib.h> #define MAX 50 struct state { int man,sheep,wolf,cabbage;//0:在起始岸；1：在目的岸 5 m3 F+ t+ M# s# S6 @ int m;//所采取的过河方法，(1--4) }s[MAX]; int count=0; FILE *fp=fopen("c:\\2.txt","w+");

0 y% s( }* V- }4 u# C1 Y

void main() # Q6 z; J- t3 O8 K{ # T7 `8 L# T4 w void f1(int ),f2();//f1试探递归 + V7 N# V$ I. w A9 r- } s[0].man=s[0].sheep=s[0].wolf=s[0].cabbage=0; % B, L/ @. O- v Y5 u, `4 v s[0].m=4; s[1].man=s[1].sheep=s[1].wolf=s[1].cabbage=0; f1(1); //f2(); fclose(fp); ) z2 f1 c: J! b9 u& i printf("\n");

5 m* w" R {/ T2 h7 [5 \

} //用m值决定的方法渡河，成功返回1,否则返回0 / Y) K I/ q2 [- m) Jint move(int top,int m) % P3 m l0 i5 A4 M' k. d{ , N- i/ X; j2 t5 G- }& x switch(m) ; b" t& b% F; K! P+ O { //人带羊过河 ?- I: o4 u1 f5 N4 S! e case 1: 6 }6 X$ y9 P& G- J! L- \/ Y //判断人羊是否在同岸 4 Y. ^' S2 ~+ O4 Q& f if(s[top].man!=s[top].sheep) , H1 c* X) S7 |5 ^% h: a0 D$ H return 0; " C1 W6 c n3 w6 y) W: d s[top].sheep=s[top].man=(s[top].man==1)?0:1; s[top].m=m;//存储过河方法 : O% h2 b; v- D8 ?5 ^9 f4 x1 j, F break; " N( o: u J, {. x# i case 2: . u5 J" U0 r/ L/ C0 Z- i2 M# w if(s[top].man!=s[top].wolf) y6 R* x7 K* r- O7 R- H' o5 ~ return 0; 0 y) z/ M$ |+ \; C s[top].wolf=s[top].man=(s[top].man==1)?0:1; ) s' u! o1 ]; s0 X" Z s[top].m=m;//存储过河方法 break; 1 }" E4 d: Y0 }- \% F5 k case 3: 4 u' T1 ]+ b( R' g. u if(s[top].man!=s[top].cabbage) return 0; s[top].cabbage=s[top].man=(s[top].man==1)?0:1; s[top].m=m;//存储过河方法 6 t P* O1 k+ k0 ^# Q9 N9 g; n break; - S: j5 w. {* L# ~$ x5 f1 f //人单独过河 ( ~$ ^) I$ B7 o; n1 S8 _, y case 4: s[top].man=(s[top].man==1)?0:1; s[top].m=m;//存储过河方法 break; 3 [9 H! E6 Q1 l& Y q: y& { }//switch $ J/ j5 v9 y, M7 W3 V: \. X return 1; / V5 t H% `7 _# T7 J7 O}//move //打印过河步骤 void display(int top) , A m. |" z/ L$ S! f. j1 @{ ! I1 d6 d) ~) \, f+ j4 } 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); " a4 i' T0 }! p+ y; Y9 l for(i=1;i<=top;i++) ( m! }! e' I6 ]% ?. B) w- k { 9 O, P* V3 t& e3 P# n4 U0 O" L switch(s.m) 9 s# J# ?1 Y# v3 I z! O: u& l { case 1: if(s.man==1&&s[i-1].man==0) - A/ `$ m$ ~' n3 h) T2 j: I- d% q5 b fprintf(fp,"人带羊从起始岸过河到目的岸\n"); ; a% ^& F7 B- P5 u. g$ i% P else fprintf(fp,"人带羊从目的岸过河到起始岸\n"); - P3 b2 V! H6 b k2 K2 E break; A5 N/ Y6 D; C: f' c, o7 U; o case 2: if(s.man==1&&s[i-1].man==0) fprintf(fp,"人带狼从起始岸过河到目的岸\n"); else fprintf(fp,"人带狼从目的岸过河到起始岸\n"); break; case 3: if(s.man==1&&s[i-1].man==0) 1 G8 s$ A( I. n/ | p5 G fprintf(fp,"人带菜从起始岸过河到目的岸\n"); else fprintf(fp,"人带菜从目的岸过河到起始岸\n"); break; case 4: if(s.man==1&&s[i-1].man==0) 9 }0 h# z, E' \* c' c- p fprintf(fp,"人单独从起始岸过河到目的岸\n"); else fprintf(fp,"人单独从目的岸过河到起始岸\n"); break; 5 A6 ~! p" h: ^/ w0 P4 h; U }//switch 3 A/ y% [/ @% `- h fprintf(fp,"state%d: man: %d, sheep: %d,wolf: %d,cabbage: %d\n",i,s.man,s.sheep,s.wolf,s.cabbage); * A* F1 [9 d7 C9 X2 }5 I* G6 @ }//for fprintf(fp,"All ferried successfully!\n"); }//display

//检查两岸合法性已经有无状态与历史重复性 $ o" O- W: }6 \( \ |int check(int top) { ! ?: Z8 p4 f' L: l/ T, V& N int i; + Z7 W, o( ]6 M. o//检查两岸合法性 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)) ; c" J$ s M% E' Z( h, g# v return 0; //检查历史重复性 4 i/ z2 P; d; o" O% N* m4 F for(i=0;i<top;i++) 7 }2 `5 B5 @4 M/ [3 F$ J& } if(s.man==s[top].man&&s.sheep==s[top].sheep&&s.cabbage==s[top].cabbage&&s.wolf==s[top].wolf) & M& k3 g& ~4 r; z2 K2 f return 0; //ok ! H! U4 N+ H% t- O5 p1 ~7 ^7 w, e return 1; ) b" e2 T) u# N6 p} ' L4 G0 b6 I' ?3 wvoid f1(int top) { B( u4 }- a* G0 G6 a% Q; Q' B int m; 2 F! E7 b( K) F* v o( y if(top>0)//0状态(初试状态应该是预先设置好的，所以要做状态1，故，初试top进来应该是1 { //对每次状态分别试探4中方案 for(m=1;m<5;m++) 1 E0 f# E. S( n { //每次方案的实施是在上次结果状态上做的 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; % L+ V( n& V; N) o* h //用方案m移动，同时检查结果 if(move(top,m)&&check(top)) ( W2 Z4 |* ~) Y& d4 @ { if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf ) , K" p0 Q5 Y+ o, |2 W* M1 v { //打印渡河步骤 display(top); //统计方案个数 count++; fprintf(fp,"count=%d----------------------------\n\n",count); if(count>1000) exit(1); } 5 W/ {: T6 `6 m- w2 g U! u* j else / }2 u& C4 Y" g: z1 z% b* O f1(top+1); 8 S e+ _/ B2 \& x; o1 E5 [ K } }//for }//if(top>=0) }//f1

! }- d( Z( a# n8 k4 l# Y$ H2 a

7 G+ K0 F8 ^7 Avoid f2() { : I' d1 `- r4 T1 a6 h int top=0,i; ! s' Z& @3 `/ F, O! s //开始时都在起始岸 . `7 t2 e1 V6 O% R- W! f; G* d s[top].man=s[top].sheep=s[top].wolf=s[top].cabbage=0; //未开始渡河 1 I$ m' p0 t/ N9 z/ F, |0 K) p4 Z- d s[top].m=4; G# f! R+ Q' o, ` while(top>=0) { if(check(top)) ; n1 i& O- |) D& v { if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf ) 3 k8 h6 {% Z) b+ F0 } { //打印渡河步骤 display(top); ) ]$ ~2 h& e ^ //统计方案个数 count++; fprintf(fp,"count=%d----------------------------\n\n",count); if(count>1000) exit(1); //回溯 7 y* N$ s8 Y) p: ^* H" k while(top>=0&&s[top].m>=4) top--; * b, s, K: b' ]" Y" y$ c if(top>=0) { //在上次状态基础上准备做move % L. g$ |; d& [ s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; 1 j' A4 g% L, y& @$ m( e) G 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)) i++; 2 d, P. `; u" B5 V$ C$ k }

} - J5 v# S0 o6 {$ e( M6 A" | C( H else { top++; . w5 j) A4 O3 `6 u* n //在上次状态基础上准备做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(i<5&&!move(top,i)) i++; }

} else & c/ ]7 s" F) e { //回溯 , Y3 K* U, J! T% m) a- p while(top>=0&&s[top].m>=4) top--; F s$ M' Q$ I) Y- d if(top>=0) { ; l; ^: x0 ^: p2 V$ o/ T! Z //在上次状态基础上准备做move ) H I+ \! S" M6 d, A. j7 R! S- U 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)) / x3 Z3 c; T/ e1 m0 _/ [* J i++; } # m" K$ G4 O. r } G" B0 O; h4 M3 V- N# b e1 G }//while }//f2 //---------------------------------

sally

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

huashi3483

呵呵，好搭档

lynn324

是用c编的吗?

mnpfc

呵呵，看过了