|
渡河问题 & L4 R4 ]5 ~4 n- m
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?
- s$ s- {" Z1 H/ C8 M7 j ) N& h( e. v! a
程序代码:
/ M. _ {1 u/ ]: E2 h//以下程序在Win98+vc6.0运行通过 6 X3 W5 [/ E$ L. M1 `' {
#include <stdio.h>! S" x% y) p9 J; d- s9 i
#include <stdlib.h>
0 D, e% k7 x, o5 w#define MAX 50
@9 ?1 P( r" F7 p+ Fstruct state
3 h6 S' t" D. O& B0 k) U$ a{; D3 s# s/ {# z6 W
int man,sheep,wolf,cabbage;//0:在起始岸;1:在目的岸3 k0 [4 n2 _+ ^5 e, h
int m;//所采取的过河方法,(1--4)8 c7 I: t' y5 B9 f8 W; s# i/ T
}s[MAX];! k9 o5 S) O) Z
int count=0;3 W ?. [1 o! v! T( \
FILE *fp=fopen("c:\\2.txt","w+"); * ?1 f8 j8 [" y8 Z- [8 B" r
void main()
& L; ]! a0 N; A7 J' H0 w4 Z6 }$ t{
( V, v) { D/ @ void f1(int ),f2();//f1试探递归" p3 _9 c. @+ D6 s' g* h0 H* b3 ?" c9 {
s[0].man=s[0].sheep=s[0].wolf=s[0].cabbage=0;) I4 x) _! J8 y8 E, K
s[0].m=4;9 V3 I) s% @7 l3 m
s[1].man=s[1].sheep=s[1].wolf=s[1].cabbage=0;
+ j4 l' }2 m2 x* Z, @ f1(1);
+ J( W D7 m' j) b1 E7 q //f2();
( A) [" D/ i; {1 k! s1 [5 J fclose(fp);$ Q7 U2 i- m5 j
printf("\n");
% M9 d% H( H" M3 @, {2 s6 M}
8 S8 Y" l { H8 V//用m值决定的方法渡河,成功返回1,否则返回0% P* C. L7 M( C' t7 k) ^
int move(int top,int m)
7 z- r( q4 U+ x3 D& [. y{' t: J0 Q2 N) s2 _& [
switch(m)
6 a, B! k2 q2 ~ z- U$ |* J {
/ @! r4 h* w- ?# _# O! R //人带羊过河* B" t' ^' W4 ^2 x6 e1 K ^+ e
case 1: 6 g2 O9 ]( l: M
//判断人羊是否在同岸
# L4 t! Q/ |. C2 V3 r if(s[top].man!=s[top].sheep)
& x: J- E0 y0 q' W3 w3 { return 0;
, q. Q+ I1 k7 w5 v; P s[top].sheep=s[top].man=(s[top].man==1)?0:1;# C( ]' u& V: v# |) _
s[top].m=m;//存储过河方法
9 W1 _$ w0 T. Z' }: G7 S2 Z5 l break;
% c, x4 ]3 D: x1 c: J6 X case 2:, ~# p" j+ R$ u1 S# p
if(s[top].man!=s[top].wolf)
# F( B2 J' ^6 p* | return 0; A* r k& A! t- m! Z# m7 [& S
s[top].wolf=s[top].man=(s[top].man==1)?0:1;3 C' {$ b2 E5 x
s[top].m=m;//存储过河方法
+ ]6 F B# H) |& o; x break;
2 L% R, L# ~4 L- f# c case 3:
, Z! s" j2 X' i/ { if(s[top].man!=s[top].cabbage)# A9 n7 A% h5 C
return 0;+ N* i; S3 e% L! J) A4 u7 i
s[top].cabbage=s[top].man=(s[top].man==1)?0:1;
( _5 c7 l7 j* T; r8 P, {# @& e, b s[top].m=m;//存储过河方法* b0 j- X Z/ Y& g3 N2 n
break;5 Z9 f* }' R* A8 [) g
//人单独过河
: w! B% q' | l6 V# `) \# z7 Z# v case 4:
5 m5 K" z; ]2 d& g- b$ x s[top].man=(s[top].man==1)?0:1;2 v/ D3 ?/ F* Y! b
s[top].m=m;//存储过河方法3 W! c$ U# H+ {
break;
) q6 E5 S2 T- F- Y2 L$ w: [ }//switch
, O" A3 s; |7 R6 a" k return 1;4 K: S9 P' x# `1 V7 W
}//move. v- H( @. t) A' _* \: z: O& k- j8 [
//打印过河步骤
+ l- R. D: ^% I8 U: d% hvoid display(int top)& l* Q$ ?5 I# J5 }7 I! z. ~
{* ]1 Y( B% T" @
int i=0;5 Y5 }; ^; b. _4 o2 S
fprintf(fp,"state%d: man: %d, sheep: %d,wolf: %d,cabbage: %d\n",i,s.man,s.sheep,s.wolf,s.cabbage);
3 K" m6 f; ?4 z7 ]& f for(i=1;i<=top;i++)- k, O4 \" O7 l; I! a
{& u1 a$ F3 a; Q! N Q a
switch(s.m)/ E8 E4 F* k+ S% v6 t
{
0 a! | f6 U# Q+ E v case 1:
6 r. u- K" u" o! X# M. j) J. q if(s.man==1&&s[i-1].man==0)
& m- E4 ^( A5 o fprintf(fp,"人带羊从起始岸过河到目的岸\n"); k( f; z/ R4 V6 V8 M6 X
else/ G, ?: ]1 ^+ b- d& q
fprintf(fp,"人带羊从目的岸过河到起始岸\n");
, p O: l* c5 m' U9 A% q break;
* |$ ~# ^. i$ F) p case 2:: ]) d- I: C+ T1 H1 {9 U, r
if(s.man==1&&s[i-1].man==0)
1 X; }+ s* V9 E" a0 b3 w% S fprintf(fp,"人带狼从起始岸过河到目的岸\n");8 F; `8 n4 O+ r0 @
else. v/ Y) Y% {& ^) G5 X7 e# t
fprintf(fp,"人带狼从目的岸过河到起始岸\n");
% N2 x& N; x# _2 j6 d1 n( L4 o2 X8 K break;* `" W$ ?1 c8 o1 r3 J. O1 a
case 3:4 B$ B' f$ K$ Y! T, F2 ~
if(s.man==1&&s[i-1].man==0)7 W7 ~' W6 H( F5 L( S1 Z( n: ~
fprintf(fp,"人带菜从起始岸过河到目的岸\n");
! b& z3 J+ q% m. D else
6 V& ~: b' r6 Y7 K# n) [; W! B% R fprintf(fp,"人带菜从目的岸过河到起始岸\n");1 M% X# [# l. F; _( C6 _' e, _
break;* y. k& F- c+ {: P; P: C
case 4:
: P4 Z! W% x) z8 L if(s.man==1&&s[i-1].man==0) v- g; I9 y. \4 C
fprintf(fp,"人单独从起始岸过河到目的岸\n");: |) ^. U( A. w6 j- L
else l! t; s; C4 V$ ~7 O1 _
fprintf(fp,"人单独从目的岸过河到起始岸\n");
2 t$ h5 l* e: }7 b# W break;" a) C( e( ^4 }; ]5 I* r& i
}//switch
% U3 ~- v% b7 g9 a6 K- w: x fprintf(fp,"state%d: man: %d, sheep: %d,wolf: %d,cabbage: %d\n",i,s.man,s.sheep,s.wolf,s.cabbage);& [3 I9 U& i9 s
5 c8 a1 c4 T- f3 r% I B }//for
$ Z0 N' d) b$ u3 q) Lfprintf(fp,"All ferried successfully!\n");
; \: l( N! [5 Q. k}//display _ u, B7 ~' Z
//检查两岸合法性已经有无状态与历史重复性4 j$ T9 W4 v, M9 q0 ]) F
int check(int top)/ h' H2 `- W' T6 G
{2 { ^& F1 `5 Q+ H, [4 U
int i;
7 I3 _: B# T+ M5 ^//检查两岸合法性
4 v: |" f+ u. c# d( N if((s[top].sheep!=s[top].man&&s[top].cabbage!=s[top].man)||
- n8 S. j$ o; w; Q (s[top].wolf!=s[top].man&&s[top].sheep!=s[top].man))
" E4 e) z% }" J! x! ~ return 0;% G6 |6 c7 I% p- ?3 a
//检查历史重复性
& @* z q) ]' M3 L: u/ p$ q0 E for(i=0;i<top;i++)
# q( Z t6 p9 ^9 y if(s.man==s[top].man&&s.sheep==s[top].sheep&&s.cabbage==s[top].cabbage&&s.wolf==s[top].wolf). F5 W6 L4 E# ]+ P x3 s
return 0;/ |' H+ h ?' {5 z, E( ~+ v; d
//ok
( b; O- X+ b) ]2 {0 K return 1;* P. c- E8 U6 L: T. M r Q) V0 B0 r
}
3 R8 d0 T. a* R- U7 @void f1(int top)
w( K% \/ c& T/ v0 \: O, Z{
5 j: ?* e0 c3 H. ^ int m;# f9 Q- f' C V
if(top>0)//0状态(初试状态应该是预先设置好的,所以要做状态1,故,初试top进来应该是1" ^* r* L6 @& S& f6 t# |: K
{ //对每次状态分别试探4中方案
$ V2 Z$ Y( ]' A1 R; [- E for(m=1;m<5;m++)" A& ^1 ~1 E6 I/ Y3 j2 K
{
$ Y, o9 i! e8 r1 s" v //每次方案的实施是在上次结果状态上做的
; W# `+ l) v5 t; H& Y# x8 h s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep;# M/ I' R/ ?% q
s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf;
: l. U1 E* s# b ^6 w _( \5 K //用方案m移动,同时检查结果6 s9 N; |4 x8 Q+ K1 u
if(move(top,m)&&check(top))2 q0 Z6 h0 q" Y( J2 ?1 Z$ g1 d
{
+ o$ V% I$ U' | a* T- f% E" H if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf )7 L( n/ A. N& H! @' |
{, ^7 e+ C# ~* b) v% F
//打印渡河步骤
6 A) _* ]7 X$ Y# n display(top);
( Z8 Y9 Q, E6 g" @1 l# \9 V. H, I //统计方案个数& I) [) o( d, }' n* z3 v1 H
count++;
' B+ u% \( J7 C' j( Z fprintf(fp,"count=%d----------------------------\n\n",count);6 }9 d7 p6 ?* Y' E6 C( ?
if(count>1000) exit(1);
) S* A2 W3 B; O/ g) w }: v8 O+ M& `, ?# R* q1 ]
else
# l) }5 v9 J w$ V f1(top+1);! r% G7 @) d" g+ I$ ~
}1 m ~+ T( X9 I E g2 C7 g+ T
}//for
- s2 }+ ~" `( Y6 Y( o) v. u }//if(top>=0)4 J& o: \" Q6 K# s% q/ |# K
}//f1
* j0 [& h! Y/ Y3 ?$ ? ; K# D1 H! {4 a, k+ R
( e; i+ q$ A. h; Y2 D
' O* N, ?# Z9 V% x/ \9 svoid f2()
7 ?. N6 r5 k; T0 f, ~3 I6 y{; j0 \. p# G* x+ J% k1 c
int top=0,i;. N3 P) B$ ]* d" L# y2 a( u1 x
//开始时都在起始岸& @ T& W8 x: n4 [' e8 B
s[top].man=s[top].sheep=s[top].wolf=s[top].cabbage=0;5 ?5 w9 E2 R! m' n
//未开始渡河9 y; s& T7 `4 ~$ \2 N$ q- u
s[top].m=4;
. y( P# f7 I k* H; \ while(top>=0)
8 O; C) N" T" ?: l$ c8 E1 } {5 `& a& ~# J& z3 u; X$ I
if(check(top))# r" m) }1 Z' I& H8 @ v
{
1 o! R h% m; B: x if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf )
/ T% i/ r. ^# I: g {
) P Z3 E: V% J& ]0 h: Q0 I/ ^2 [ h //打印渡河步骤
" e* e/ q9 T) j0 F0 | display(top);( E% v/ o& P. r
//统计方案个数* n' f0 e" C0 `
count++; - W; Z, f' c" e. D1 ^% k/ T
fprintf(fp,"count=%d----------------------------\n\n",count);3 n+ W4 G: I* E- e+ H( S. R
if(count>1000) exit(1);
' \( \' |: q; p+ |. S. \: o //回溯
3 f$ n8 r* }1 i0 J while(top>=0&&s[top].m>=4)
2 `6 [: m" l4 _' l3 c% } top--;+ b+ ^9 W: g1 B) U8 s. I
if(top>=0)
& e3 M, ?( q1 a0 A% O/ r2 n {
7 [' k" }- X9 b //在上次状态基础上准备做move
1 ^7 m1 `) x* i2 o% b2 M s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep;9 y. `: d ?+ V
s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf;
% y: E( M/ A+ L( P7 [ i=1;
5 ]$ I. n& C/ \! s while(s[top].m+i<5&&!move(top,s[top].m+i)). w4 Q. w0 e$ a4 n% o) x
i++;$ f# R) \; ? ^) R" C# i
}
; j* g" \5 O4 |( ?8 Q2 J }
* S7 ^) s/ U4 Z5 |6 \9 E+ I else, X; V. j7 s$ \: C/ E" ]
{; ]7 v. g+ ~% ]; b! V0 N1 s
top++;
$ `2 n9 d% ^, Z0 E8 h+ ~7 P* Q //在上次状态基础上准备做move4 a4 A. G* a9 K/ s" P4 \) {
s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep;; `" w4 x: q) ]2 L' X0 e4 {- @
s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf;
3 f2 o% `4 H: ?/ a i=1;. {7 u& L' x" R
while(i<5&&!move(top,i))! f+ b+ x5 g X/ ^
i++;* b; y3 n6 V+ O0 n
} 3 I' y9 D3 R! M! {
}
% v; M6 X! p7 _; p+ G8 L/ r: K V else
* c0 S5 K) b& G, q {3 q! b6 v3 O/ e4 W
//回溯
; y ?* [) R: x while(top>=0&&s[top].m>=4)
' L+ Q8 Y4 I K9 Q top--;) b% R; R$ f+ k6 _* I# a; @
if(top>=0)
5 c8 @; c6 T6 U1 f E {7 I/ O& F$ t% W) h
//在上次状态基础上准备做move
* n* P* _( i5 w5 u s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep;+ Z& ?6 Y6 D. x- ? q& j
s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf;
3 [. }- J7 Y8 I. ~. N' ^3 U i=1; . U' W/ X; o& e% w5 h
while(!move(top,s[top].m+i))
9 D/ b: Y4 S n/ e7 P i++;; ]6 X1 N8 m8 a6 o f4 M4 @4 S
}$ V; M5 e5 h7 [7 O; g
}
! I0 Y+ y5 Y4 ~/ V9 C. {2 v; ? }//while
% ]; K! Q2 N# t( U8 c}//f2. J* P$ U9 V4 Z9 f
//---------------------------------/ {" {" j1 r6 c8 n
|