渡河问题

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?

0 |1 X; {! T. U

程序代码：

: N9 J' G' E8 Q

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

7 a: i. \: Y0 t, G( T

#include <stdio.h> #include <stdlib.h> ' L! H7 d" ?( W) ^" B#define MAX 50 struct state { int man,sheep,wolf,cabbage;//0:在起始岸；1：在目的岸 int m;//所采取的过河方法，(1--4) , F, T' s. M% w, c' K}s[MAX]; , b$ k: f" H) E- Pint count=0; FILE *fp=fopen("c:\\2.txt","w+");

void main() # I6 r) z0 h& G. o9 \{ void f1(int ),f2();//f1试探递归 s[0].man=s[0].sheep=s[0].wolf=s[0].cabbage=0; & N/ o/ u. Z3 A x( @7 L s[0].m=4; + S, s3 u. w- O3 Z+ {0 W: }5 s s[1].man=s[1].sheep=s[1].wolf=s[1].cabbage=0; 8 p1 D" X, [$ E, d1 I* t f1(1); % Q0 _% j. H/ T7 e6 j //f2(); 0 v) r: I. p' K" w) {: e fclose(fp); & p5 \- }: H- {: E9 d. n6 M& ^ printf("\n");

8 G' K2 i0 G( Z1 c; M

} //用m值决定的方法渡河，成功返回1,否则返回0 int move(int top,int m) # Z7 z- d j! R' d2 i4 e+ j" A; O{ & Y# [2 _7 _0 o6 U9 A' m switch(m) { //人带羊过河 6 L0 k6 o5 r$ @# v! G% A case 1: //判断人羊是否在同岸 if(s[top].man!=s[top].sheep) return 0; s[top].sheep=s[top].man=(s[top].man==1)?0:1; s[top].m=m;//存储过河方法 break; 0 n n) D( c4 a2 `0 u- U+ }* O) r% v0 \ case 2: 9 g' O- H3 N3 {: h B! t6 | if(s[top].man!=s[top].wolf) return 0; * C. ]& q/ C9 X/ E/ V1 C! c s[top].wolf=s[top].man=(s[top].man==1)?0:1; s[top].m=m;//存储过河方法 break; case 3: if(s[top].man!=s[top].cabbage) 2 W3 `. x. U' r, Z" o9 D return 0; s[top].cabbage=s[top].man=(s[top].man==1)?0:1; s[top].m=m;//存储过河方法 break; //人单独过河 3 g/ P2 a' w8 _/ b case 4: s[top].man=(s[top].man==1)?0:1; s[top].m=m;//存储过河方法 break; }//switch return 1; }//move //打印过河步骤 void display(int top) { : v9 B j" V5 G) Y+ N, T 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); for(i=1;i<=top;i++) - k" {2 c! z/ G/ R9 _ { 0 u4 q/ k- Q a( _5 N+ s switch(s.m) 9 W; f5 a) A( k0 M6 M5 q6 x4 _% c { : k$ S6 _2 G) Y ^( n; c case 1: if(s.man==1&&s[i-1].man==0) fprintf(fp,"人带羊从起始岸过河到目的岸\n"); else 2 {+ m# R$ Y8 Y6 L, {) \! f fprintf(fp,"人带羊从目的岸过河到起始岸\n"); $ R/ c: w% j3 t6 k3 \1 R break; ; ?2 H& G4 t D# z& E case 2: if(s.man==1&&s[i-1].man==0) fprintf(fp,"人带狼从起始岸过河到目的岸\n"); " u: m$ u3 ^) X9 t* A4 m& H; W else 9 m; T4 a! y( K! C* c- S fprintf(fp,"人带狼从目的岸过河到起始岸\n"); break; case 3: - Q. }- n' r$ c o! m0 o/ F if(s.man==1&&s[i-1].man==0) 9 ]' e6 F; |$ c fprintf(fp,"人带菜从起始岸过河到目的岸\n"); $ y' m0 n' L- a, G else fprintf(fp,"人带菜从目的岸过河到起始岸\n"); break; 0 H# V. L% ^) _1 w3 t3 Q. l case 4: if(s.man==1&&s[i-1].man==0) fprintf(fp,"人单独从起始岸过河到目的岸\n"); else fprintf(fp,"人单独从目的岸过河到起始岸\n"); + p+ l; q+ T8 w break; 4 r a( {( {$ ] h5 X }//switch ) j( x" `0 B: E" {7 k0 p fprintf(fp,"state%d: man: %d, sheep: %d,wolf: %d,cabbage: %d\n",i,s.man,s.sheep,s.wolf,s.cabbage); + G2 U7 \4 k6 w# _ }//for fprintf(fp,"All ferried successfully!\n"); ! X/ F6 c$ V0 O3 }. c9 u/ a6 O}//display

1 f' ^9 C: ]# }6 K7 u

//检查两岸合法性已经有无状态与历史重复性 int check(int top) 4 `/ a" ` n- W, I1 [# _6 _{ . e! X \) w! T6 Y; v int i; //检查两岸合法性 if((s[top].sheep!=s[top].man&&s[top].cabbage!=s[top].man)|| 2 E8 D0 H6 h( x! ^- n (s[top].wolf!=s[top].man&&s[top].sheep!=s[top].man)) return 0; . d% K! D# x- d/ J5 x //检查历史重复性 - i, {* Y$ f7 _: `, q9 s 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; $ D, l+ [4 L0 d' R' x# h% V3 ` //ok return 1; } void f1(int top) ; g- k" J) G- S" o% ]{ 9 F0 F! ~* z- I( s3 D int m; if(top>0)//0状态(初试状态应该是预先设置好的，所以要做状态1，故，初试top进来应该是1 3 \* j" z9 H! k5 w { //对每次状态分别试探4中方案 for(m=1;m<5;m++) { $ Q# ]. I+ X0 P3 Y0 \3 u" M8 [0 S. u9 x //每次方案的实施是在上次结果状态上做的 2 J" d' Y* m% z0 P# a s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; $ z8 y$ I4 t/ y; v a* d+ X: j s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf; //用方案m移动，同时检查结果 if(move(top,m)&&check(top)) + ]% M( J8 O- [ B1 X { if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf ) " `- D! p! m+ n- _ { //打印渡河步骤 " a! t, r0 x7 o9 Q( m' h; d display(top); 7 B# e( r( g9 ^ //统计方案个数 0 V6 N& J5 J/ s9 L l0 g0 V* o count++; ) D6 c8 O6 m: U( g, q fprintf(fp,"count=%d----------------------------\n\n",count); if(count>1000) exit(1); 9 b' Z& V! e* ~' F, L } else 4 r6 Y* d2 }( c3 e# P) n f1(top+1); 2 ?1 i$ W1 ~7 W: j } 1 V; q! H U9 v) l6 {. `/ ]: a3 W& v7 S }//for }//if(top>=0) # \, R8 {3 N. o: g& ~2 L d8 M}//f1

8 U: ~' L, ~* G* d8 s$ }- |

( a1 b! u& Y8 ]# V' _

' Z0 u& D. @3 F5 z! X# J' D3 P' A7 _void f2() ; w2 n, _# E5 C+ }5 m5 h( A{ 6 w5 a) ^3 V2 n8 u+ R/ ^+ U& D) g int top=0,i; //开始时都在起始岸 3 v' T' Z4 O a& b0 c s[top].man=s[top].sheep=s[top].wolf=s[top].cabbage=0; //未开始渡河 7 p0 h7 t: t" X+ L0 }5 v! z s[top].m=4; while(top>=0) { ( b$ y4 G. @/ J/ I7 A' H7 L if(check(top)) 5 D8 }% r* I! M- c9 e/ S { 9 z5 G5 P- o& O6 Q& q8 q if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf ) 1 T+ L. t T3 |2 M { //打印渡河步骤 display(top); //统计方案个数 5 `) ^7 O: D. O0 Q W count++; fprintf(fp,"count=%d----------------------------\n\n",count); if(count>1000) exit(1); //回溯 while(top>=0&&s[top].m>=4) " D5 M4 q2 r+ k+ c+ |$ { top--; : j0 V7 D5 W$ K3 \8 c. p7 R if(top>=0) { //在上次状态基础上准备做move s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; + h* @8 \. y& ? s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf; 7 h2 e; _* m3 i* q& ` i=1; while(s[top].m+i<5&&!move(top,s[top].m+i)) ) `$ O" r' H" C5 M7 { i++; }

6 q: G& h& u4 O6 r3 X% m

} * }7 t, K" V1 `: q& U7 [' Q else { ) n! H; E' y$ H. ` top++; 1 Y" c6 D7 l) d/ }+ F //在上次状态基础上准备做move ; [* Y- D1 k+ {% I$ B 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 . J3 O! T( J9 o# A% E3 H { //回溯 while(top>=0&&s[top].m>=4) top--; % A" j, j) a5 k' p- P7 q$ ^( j9 n if(top>=0) 4 i4 _8 p: d. S" v) M9 _/ G { ' _$ W' X5 x0 N! h& M3 U2 m, b //在上次状态基础上准备做move s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; : X& P# |+ \& w0 n; ^+ ?4 U s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf; 8 ~9 q! Z+ H3 k+ A) S& y i=1; while(!move(top,s[top].m+i)) 5 Z$ o) }0 m9 M0 `( E2 J i++; } 7 g4 t$ U) W% ~( X- _# {3 h } }//while - }' S! s3 j" M& m* p}//f2 //---------------------------------

sally

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

huashi3483

呵呵，好搭档

lynn324

是用c编的吗?

mnpfc

呵呵，看过了