渡河问题

sally

渡河问题

4 J- X* D9 r% y/ j* i0 K

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?

3 |5 `$ h* ?$ {* E& L9 |9 a

程序代码：

% i5 y6 d2 y5 h" H, |$ T! J" T0 G

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

, ?- \" O1 D: B4 O/ Z. Z* f+ I

#include <stdio.h> ! F3 k; P/ V, {) E#include <stdlib.h> #define MAX 50 struct state { * M+ I) x* m, p. n" U9 i1 S5 t. P int man,sheep,wolf,cabbage;//0:在起始岸；1：在目的岸 . t( q0 O' |( t) G& z* { int m;//所采取的过河方法，(1--4) # b# }( p0 K7 V/ F7 I+ u}s[MAX]; int count=0; FILE *fp=fopen("c:\\2.txt","w+");

+ h" N+ F( K# C0 r6 q

void main() S$ n! ^' }+ p: G# u: X1 l! a$ l{ void f1(int ),f2();//f1试探递归 ' D5 X1 S- `. m8 a s[0].man=s[0].sheep=s[0].wolf=s[0].cabbage=0; 6 R1 q- b+ i5 w, {4 A( O7 P" z r s[0].m=4; ' v* q, g, H5 | a3 _ s[1].man=s[1].sheep=s[1].wolf=s[1].cabbage=0; ) _1 e, U4 W4 f5 ` B f1(1); 6 `/ w) R( d; }; w //f2(); fclose(fp); 6 R) K- Q: c4 E4 K printf("\n");

} //用m值决定的方法渡河，成功返回1,否则返回0 int move(int top,int m) 5 M" G s% s' o( L. N{ - `# j/ L/ K+ O9 \ switch(m) { //人带羊过河 case 1: //判断人羊是否在同岸 ) J$ M9 A e/ W if(s[top].man!=s[top].sheep) ! f# Y" F- \9 P return 0; s[top].sheep=s[top].man=(s[top].man==1)?0:1; s[top].m=m;//存储过河方法 break; case 2: if(s[top].man!=s[top].wolf) return 0; 8 H& f% C9 X# ^# U/ z3 _& n5 i s[top].wolf=s[top].man=(s[top].man==1)?0:1; s[top].m=m;//存储过河方法 " }' @, o& X$ ^% H break; case 3: if(s[top].man!=s[top].cabbage) . g2 e6 X" P% M. k3 D6 k; D/ J return 0; s[top].cabbage=s[top].man=(s[top].man==1)?0:1; s[top].m=m;//存储过河方法 break; //人单独过河 case 4: s[top].man=(s[top].man==1)?0:1; & g; S3 G6 m7 l6 P; W# s s[top].m=m;//存储过河方法 ) h# f( F* T& g break; " O& {, ^2 q/ m) M8 G' w: F% y9 X) i }//switch + ^- H0 G7 {) ~7 h# D; o9 C return 1; }//move ' E3 R7 ^/ I8 L8 P+ ?6 [//打印过河步骤 void display(int top) . f1 _. ?, g3 {: {4 r r: Q{ 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++) + K7 C2 o* Z3 h) Y8 ~6 A9 c { ( M+ l; [2 s9 q" r' m+ }& O/ m switch(s.m) / q6 k/ A& ]" N* e { ) e8 r. }9 u. Y% W+ F case 1: ( ~4 ]2 [4 u, p6 A if(s.man==1&&s[i-1].man==0) fprintf(fp,"人带羊从起始岸过河到目的岸\n"); # l. u( o4 ^% K" V' h3 i: p) t else L; L) S' B+ Y0 u, a9 X fprintf(fp,"人带羊从目的岸过河到起始岸\n"); 7 Y# T. S! g3 ^1 _5 P2 {" Q- ~ break; 5 o' x: ^' i, [8 \9 m; e( l2 B1 V0 | case 2: ) ]- |4 e) \$ e3 S$ K if(s.man==1&&s[i-1].man==0) fprintf(fp,"人带狼从起始岸过河到目的岸\n"); $ N6 N( @. f; |& O1 U% \ else ' R5 |& L; _) K2 g' u! h3 m fprintf(fp,"人带狼从目的岸过河到起始岸\n"); break; & Z% G: R$ M2 j/ O9 n6 r* g case 3: ! {& q; D4 u. f9 x& H" F4 Y if(s.man==1&&s[i-1].man==0) fprintf(fp,"人带菜从起始岸过河到目的岸\n"); ) ?. Z# X) |( h: d+ e! T) l$ u else $ O2 D$ x% i) t" Q. v fprintf(fp,"人带菜从目的岸过河到起始岸\n"); break; $ i; |0 r. M1 _/ u6 n, ^* d9 \2 T case 4: 9 [/ i9 a/ L/ ?; k& E' a if(s.man==1&&s[i-1].man==0) / N$ {( g7 g1 R3 t0 ]- x+ v4 x fprintf(fp,"人单独从起始岸过河到目的岸\n"); E: I( [! I1 M, t9 }7 @ else % O* o, c4 `- P! s1 U( X( H fprintf(fp,"人单独从目的岸过河到起始岸\n"); break; . ?9 N; q4 k$ q4 J) t6 d5 M }//switch 7 J$ m6 a# y2 L- f8 m$ l/ w fprintf(fp,"state%d: man: %d, sheep: %d,wolf: %d,cabbage: %d\n",i,s.man,s.sheep,s.wolf,s.cabbage); ( v' M8 E3 T! _+ w! K) } }//for 2 k9 [6 C: y* Y ^fprintf(fp,"All ferried successfully!\n"); }//display

/ {: z2 p7 X, U

//检查两岸合法性已经有无状态与历史重复性 int check(int top) ! |2 X) g/ t: ^) {) W! L{ int i; //检查两岸合法性 9 Y: e; q+ G- \6 x( ^ H* c! D 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)) return 0; 1 H. {2 N" V3 |. K5 n //检查历史重复性 for(i=0;i<top;i++) - ]9 Y3 z# @% Z if(s.man==s[top].man&&s.sheep==s[top].sheep&&s.cabbage==s[top].cabbage&&s.wolf==s[top].wolf) return 0; //ok return 1; } void f1(int top) - f5 F8 Y' [2 N; O/ X3 H( @{ % w9 ~* ~- N% ], Y; s8 J int m; if(top>0)//0状态(初试状态应该是预先设置好的，所以要做状态1，故，初试top进来应该是1 { //对每次状态分别试探4中方案 4 L0 X$ }- ^# Q/ G6 m for(m=1;m<5;m++) . o9 a% _# G2 W" X2 o { //每次方案的实施是在上次结果状态上做的 s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; , @1 z% ]( R j2 B) K s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf; " L2 p) q7 d( W0 N7 U //用方案m移动，同时检查结果 if(move(top,m)&&check(top)) , v0 ?" ^1 N- j/ J( K! B0 [" T { if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf ) { 7 b! A- Z8 o8 b8 [$ \0 y, R //打印渡河步骤 4 }/ v: q1 u2 I6 ^* X' [ display(top); 1 L5 k& X& p5 u6 Q( } //统计方案个数 / {- t' V- p6 a( K; A count++; $ G1 h; X6 w9 @* W4 |6 S Z fprintf(fp,"count=%d----------------------------\n\n",count); if(count>1000) exit(1); } else f1(top+1); ' @; ^/ ]- O1 { } }//for }//if(top>=0) }//f1

7 a5 | C5 } x% l, j% v7 q

0 C( b! q& K n* q5 T3 y

void f2() 3 r& M/ b$ C4 N$ H5 ?{ 2 ~. [9 E7 Z$ w6 {" A6 S1 ~: J) g" A int top=0,i; //开始时都在起始岸 * `0 e1 U4 |6 q* b s[top].man=s[top].sheep=s[top].wolf=s[top].cabbage=0; : T k" C) V) H/ a$ S; J# }9 q0 J4 s //未开始渡河 9 F, I& z8 L+ l. |4 [4 z" l) P2 \ y s[top].m=4; . l- ]. @5 |6 b; u+ V6 [ while(top>=0) { if(check(top)) { ) a; `7 ]- S& P# G if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf ) { //打印渡河步骤 & p# l$ i* g, }; E( {- h; P% T% q display(top); 9 r. d7 T! Z4 J4 e3 E" Q# ^4 L //统计方案个数 % ?1 G' u6 Y$ q' `1 j count++; fprintf(fp,"count=%d----------------------------\n\n",count); ' ` f6 K$ ~( F1 C5 Z if(count>1000) exit(1); 0 Q% u/ h& v2 ~% n& a( E //回溯 while(top>=0&&s[top].m>=4) top--; 1 H0 c, H" [( x# v* f0 z if(top>=0) { ' ]7 t; ]1 l2 P+ Z! x" f; { Q //在上次状态基础上准备做move X) a; `- {1 a7 Q* ^" l }* Q4 i s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; $ N( D6 K' n- ]. P. Z _ s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf; ; Z7 N; p. b3 F: D i=1; while(s[top].m+i<5&&!move(top,s[top].m+i)) 7 Y6 ~9 ]- o6 f8 H+ a, o i++; # F3 w; T2 @7 X4 x( E }

7 v* S5 Y( U. R3 ^

} * Q( w" G0 R3 K( y7 {& O0 j/ F else * \3 e: G9 K2 D& w7 S$ Y { % f8 d. J9 u9 u' B top++; //在上次状态基础上准备做move s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; + o$ u! S# r+ |9 G: H. L. ^ s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf; % {" \9 W6 E' `& j. K$ n i=1; - J8 A, }% [- T; r3 V6 ]2 G: E9 h while(i<5&&!move(top,i)) i++; % c6 S* ?$ X( u }

} " e% F3 c( r2 q1 N/ c, _/ ?1 u else " ^/ j. N6 m5 M { * ]7 Z, J8 D! j# R# ~ //回溯 3 a8 Z. g. S% E c1 ?& G0 A6 ? while(top>=0&&s[top].m>=4) top--; 7 p" x8 ]) d, j* H if(top>=0) { ) U$ D( Y4 H* Q2 E2 [3 _3 o2 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; 9 ^& U2 t2 _) Y6 i4 k4 s i=1; while(!move(top,s[top].m+i)) i++; } 5 u8 R2 {6 O! k2 O } # `& O T+ T; W4 R ^# G* ? }//while }//f2 //---------------------------------

sally

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

huashi3483

呵呵，好搭档

lynn324

是用c编的吗?

mnpfc

呵呵，看过了