|
渡河问题 : N* o" y3 c- u& R) W% Z
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?
% l1 m; H2 c0 ?' ]+ n6 d u6 A6 M _8 ~, W
程序代码: + r* K' i; q( j( B' l/ C' u: }
//以下程序在Win98+vc6.0运行通过 : E) ~: h- N5 |4 @/ ]; W, _# T
#include <stdio.h>
; F& c' I) i+ e6 X% I# S0 f. a. z#include <stdlib.h>9 s; c. ]3 Q. S) Q8 K
#define MAX 50
2 y- w. _( t2 a. L& F- Ustruct state
$ E4 n' g+ ?6 R4 p' J& M{
2 X& G- N/ H' ]# ?0 _, U/ T int man,sheep,wolf,cabbage;//0:在起始岸;1:在目的岸' o* ~- {+ w3 Z, @& t8 k" c" M' u
int m;//所采取的过河方法,(1--4)
' e- R: v. y- W5 q2 `}s[MAX];
/ _ W! c# p& Kint count=0;
t1 Q8 l( L: `! |9 b! y& BFILE *fp=fopen("c:\\2.txt","w+");
3 }; g' b, B. ~6 vvoid main()
0 N9 l7 G8 h2 Q. n% p{0 q) l! ]* o% r* k
void f1(int ),f2();//f1试探递归& [1 {7 D; O% ^% |2 B
s[0].man=s[0].sheep=s[0].wolf=s[0].cabbage=0;5 T L, S) J$ z# w! U
s[0].m=4;! ~; \6 z% F' a( u
s[1].man=s[1].sheep=s[1].wolf=s[1].cabbage=0;
, t; h% o3 M( P/ P* I. z f1(1);
7 M8 A' O8 F5 l5 k) R //f2();
6 q7 f; l2 y a7 T4 B fclose(fp);: o1 k! N, G/ p4 t: V- p& N" K
printf("\n"); # \) g$ }: V. ?+ ~( n& @8 n
}
2 u1 d0 O, t; k! ?5 Y: [( D8 z3 D//用m值决定的方法渡河,成功返回1,否则返回0
9 m) G C) w* c7 e0 O4 ^/ h# nint move(int top,int m): j# ^3 _3 d% I
{
( P* w5 K- h3 M3 ?3 @ switch(m)1 T5 J+ A2 Z4 x& Q- Q) T6 W
{9 n1 V4 Y/ Q% y1 @- F
//人带羊过河
- u* H3 f2 A1 x" d6 v8 {1 w case 1: / w7 M; y0 _! J! w: k; N
//判断人羊是否在同岸* O/ G8 m4 c: Q$ h
if(s[top].man!=s[top].sheep)
4 ^, z1 `7 x% }2 ~+ ^ return 0;
5 j- F. K0 |+ u1 \: M1 c. | M s[top].sheep=s[top].man=(s[top].man==1)?0:1;) V8 L) b7 h( R* H; \8 ]9 H
s[top].m=m;//存储过河方法- t+ |; Y8 F* ?. F5 u* v
break;
4 l+ i" M; H& p( ?$ U4 {! R( V# n case 2:) g/ B3 b4 M- Z; q. }% o
if(s[top].man!=s[top].wolf)
4 h: l: M* u. E% E3 ?' j return 0;! x8 f" U, C- Z1 S& y" G5 i
s[top].wolf=s[top].man=(s[top].man==1)?0:1;) b- q7 u9 l$ i- t. p- c5 |' w
s[top].m=m;//存储过河方法, |7 r9 e* a4 _ C
break;1 {7 C4 F* k+ `( H, u( O2 g" s) i
case 3:
! q! _$ a- Q2 m4 }+ h7 t$ U- t if(s[top].man!=s[top].cabbage)
$ L n8 z C) O, U return 0; N% f" l, f/ ?: {' |! Z
s[top].cabbage=s[top].man=(s[top].man==1)?0:1;# c* j9 ^4 d) \* K
s[top].m=m;//存储过河方法8 H4 k+ L" d! z" L" k. O: c
break;* ?, y1 R# i$ A: y1 }! X
//人单独过河. p7 T, P1 @: l4 x0 Q R
case 4:5 Q {4 e6 R R; `$ o$ O
s[top].man=(s[top].man==1)?0:1;2 Z' @ H7 G: A" X- x9 j- T$ U
s[top].m=m;//存储过河方法
& K( M1 q1 S. a5 @; Z break;
! Y, g$ v7 c9 D. ~) s, }' e6 g$ ? }//switch* X- m _- F8 ` J" }
return 1;5 E, o4 ^8 b% t7 S Y) `4 y: o
}//move4 l' B1 ^& K" {8 o5 C( {" f
//打印过河步骤! h% |5 M2 e9 z& o/ a/ R: G5 R
void display(int top)
' R2 O, ^) u6 p) K5 O4 M% q: E( U( |{
5 ~, p8 V2 C _ int i=0;8 v4 S3 f' [: {+ R2 D4 F$ I. F/ ^3 j
fprintf(fp,"state%d: man: %d, sheep: %d,wolf: %d,cabbage: %d\n",i,s.man,s.sheep,s.wolf,s.cabbage);
: f- b/ T7 P1 f. { for(i=1;i<=top;i++)
# o4 b7 D( V2 W: p {# H1 p$ D6 [4 U
switch(s.m); j8 ]. i3 r+ i3 f) I& l
{ E2 Q- g# _! t
case 1:
& O, V, T' U, C if(s.man==1&&s[i-1].man==0)
7 L; c& i5 f- ^9 G! ~& g6 J fprintf(fp,"人带羊从起始岸过河到目的岸\n");# b8 ]6 p" [- a0 r U
else! J3 Y1 @; w3 ]& \% }; e3 C/ z
fprintf(fp,"人带羊从目的岸过河到起始岸\n");
- x3 q$ i' @. H1 l; r; B break;
5 e+ ~/ y+ l9 R* @/ [ case 2:
4 w( R' \, V5 Y: Z2 f, Q- v+ t2 R5 `1 @ if(s.man==1&&s[i-1].man==0)" C( g& U! ?. h8 c# h
fprintf(fp,"人带狼从起始岸过河到目的岸\n"); D5 {" H/ c4 s- L1 ]
else
n9 W- f0 {' N7 J fprintf(fp,"人带狼从目的岸过河到起始岸\n");# ]+ q& B/ D( I. `! f S6 Q
break;
" S0 ?: E6 M' g9 }1 b0 b/ E4 ~2 K case 3:
4 @4 E6 ~* c3 W) C* l$ o if(s.man==1&&s[i-1].man==0)
% R- `) U+ z' a8 r, D& c fprintf(fp,"人带菜从起始岸过河到目的岸\n");) L, Q. z$ R& y, {7 ], O( F, x- ~
else. _' i9 t8 z5 @" `+ U) t& P$ L A8 e
fprintf(fp,"人带菜从目的岸过河到起始岸\n");, T. o l; V8 g1 A
break;& ~2 m4 u0 c) F1 C y8 m
case 4:
% f, W1 m' \8 H: `& @; K if(s.man==1&&s[i-1].man==0), W9 }. \ |( ?9 M- k
fprintf(fp,"人单独从起始岸过河到目的岸\n");
; r- }; G7 K7 e% b) {: w) g, u% h else1 G% `5 p' x3 g2 N/ r0 d! C/ x
fprintf(fp,"人单独从目的岸过河到起始岸\n");. M f: g8 ?" {
break;
2 T5 {8 ]0 t' @$ ~) z }//switch/ b3 \3 w$ U& J: N0 `; V
fprintf(fp,"state%d: man: %d, sheep: %d,wolf: %d,cabbage: %d\n",i,s.man,s.sheep,s.wolf,s.cabbage);# `. ?1 L6 L8 `
; E, \# D5 _! X. t. B
}//for5 D0 }8 ^! K8 @ }/ m( d
fprintf(fp,"All ferried successfully!\n");
8 O; j9 e2 _) g6 F% ]3 g% t7 Z: z}//display $ E% c% \6 g- n' ]# u
//检查两岸合法性已经有无状态与历史重复性
n; f2 Q; H$ n: Oint check(int top)3 Y+ }* v6 i' o# T ?
{) ], t- _6 c# @$ ~" F$ D
int i;/ S# Y9 _% d0 j+ @. D
//检查两岸合法性9 l4 m; j. f& B
if((s[top].sheep!=s[top].man&&s[top].cabbage!=s[top].man)||
* [0 _- U" I. m/ S* U7 ?9 d (s[top].wolf!=s[top].man&&s[top].sheep!=s[top].man))
% j N& W6 w7 d4 U" \# w return 0;& H. r$ p+ Q; M C1 C
//检查历史重复性
& K- f$ S8 g% p* N5 a for(i=0;i<top;i++)) g2 d& v2 H; B! Y( E
if(s.man==s[top].man&&s.sheep==s[top].sheep&&s.cabbage==s[top].cabbage&&s.wolf==s[top].wolf)
& q d1 W1 C" `- f4 s; ]5 W return 0;
8 v7 U+ N5 d" a' a7 V. j //ok5 I6 ]. m* ?) F$ `& r: w0 u
return 1;
. h5 R! X1 _, ^$ S. M! i; @, ~}4 _; Y' D$ @; Y x+ `
void f1(int top)" w" q% O4 ~+ |- z8 |2 F6 A
{
6 z2 g* f9 x* B; x int m;
P& p% X5 o* n: T3 R- z if(top>0)//0状态(初试状态应该是预先设置好的,所以要做状态1,故,初试top进来应该是1& U A" f3 g k5 |
{ //对每次状态分别试探4中方案
* O: Z+ _/ m* U! z) I for(m=1;m<5;m++)6 r" Q! L' F1 i
{: [- m, Y' P" |# t' o
//每次方案的实施是在上次结果状态上做的
5 U2 w5 n* u: {! C s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep;
% j8 P2 D$ g+ k/ n8 Y b s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf;, j# I- _2 P/ v4 J! r7 }3 A+ z
//用方案m移动,同时检查结果
& D3 v! m; d( O if(move(top,m)&&check(top))
( [$ C; S) Q# k, k. Q) z {
6 ]) E/ S1 m0 `3 t8 @ if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf )
/ s: T* U# T- W4 w% E( P/ } {& S) Q6 L+ y' u. U! `
//打印渡河步骤
+ i6 m; \1 F% C3 n display(top);
9 W+ {+ k5 n4 ]# Z- l //统计方案个数" S I3 A0 F- M, `
count++;
0 G! M( e/ Z3 i' x# J fprintf(fp,"count=%d----------------------------\n\n",count);' s a% ~% d( u- ?' h8 X
if(count>1000) exit(1);
8 ?( X- m# J+ t }! ?& F$ M! E% o- Z; C; M( Z
else
; E* U7 }/ [) K+ S( Z f1(top+1);
6 x' f1 a9 p, ^/ \ v$ r$ E }1 C/ j* j3 Q; ^2 d
}//for) Q K ]0 J: n8 k1 A
}//if(top>=0)! Q h( ~9 {+ h o: W) H
}//f1
3 ~( M$ E( Z" ? ( _* s5 Y" P& O
# p: s* V5 Z8 D+ n* B+ J
E; w6 D+ N# l# U. i' ivoid f2()1 a, I# O8 |5 M1 I( Y5 p5 u% ?
{2 q. a8 o. z) {2 F1 I
int top=0,i;
$ g5 ]+ X6 F4 S I0 A- m! E! B //开始时都在起始岸
: r9 N! ?7 v& }# X7 z! c$ w& F s[top].man=s[top].sheep=s[top].wolf=s[top].cabbage=0;
0 X3 c3 s5 @) w' e7 |9 k //未开始渡河( _0 E9 a' v6 G9 t! @. P r$ W
s[top].m=4;
, a; x; q: K1 q1 l while(top>=0)$ y& v9 V8 @+ f2 H0 `5 z
{
" @# U. ^; b7 y+ ^7 E8 c if(check(top))
4 d7 n* G# v& _) K4 D {
" l. _9 O6 F+ z( c if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf )4 `( E) i6 s0 w, B
{! b0 f! z$ i, D
//打印渡河步骤. ~2 P' B+ [- }
display(top);% V w4 E6 `! K T3 k* \# H
//统计方案个数0 d }, a: ~5 _$ [$ U1 G* y3 g
count++; " y, D K- W u' M8 v' _" b
fprintf(fp,"count=%d----------------------------\n\n",count);
$ j3 j' s, P3 R$ e" d- U- d& `3 l if(count>1000) exit(1);
2 T1 J: O2 g$ ^- L& d* S //回溯, ]: ~7 s l$ t2 Y% B
while(top>=0&&s[top].m>=4) ' z, `/ a. ]+ _6 l1 q% _' x
top--;
- m5 y- e5 {: S. A8 ? if(top>=0)
6 z: E( T9 Z6 m9 m# k {
/ l/ J/ Q: ~( `; Y( Y. a //在上次状态基础上准备做move# L7 a \( F {, B
s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep;
. i% ]" p2 Y; O# r" m s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf;
& N2 ^; Y% z. A2 a1 N8 K8 p i=1;! P9 g5 o1 s: j$ Q2 w$ Y
while(s[top].m+i<5&&!move(top,s[top].m+i))
8 L+ H; D5 P" x( T7 L6 a; Z( k- ?# L i++; ~% w1 y) _( _% X- ^- Q+ f
}
& [: p' X: h, R }
' {. q z" k$ S" P else# D1 g+ I3 {( K# u# |
{
/ G5 Q$ Y; b% H# y' A* V: D5 a top++;
; E3 y/ Q* h/ B' ?) M% H //在上次状态基础上准备做move$ P. {/ J/ C; E. r: t" V7 o' v
s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep;
' b, I8 k: n+ L$ K2 ?$ [# E3 h s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf;
$ M3 b3 T' K) e i=1;
6 P, V3 y& q% C, P M while(i<5&&!move(top,i))
6 ~# w$ A3 w+ G# L8 L3 W i++;! R' U& r2 u7 d) ~
}
% y0 I) |2 w' u% Y+ W* c }
C* W, W8 V: `: U) C else$ ^4 h) {7 r- c
{
& a c# e8 |4 [, ?0 ~ //回溯7 l! e& z2 @1 N* x- a
while(top>=0&&s[top].m>=4)
* ?) \& \! W/ k9 z6 w# U top--;: s7 E6 C. r% T4 [- E. i7 b
if(top>=0)- V/ X5 Y6 m! O" d/ \! J
{7 M' T P5 d( J: J5 a- i, Z7 p
//在上次状态基础上准备做move r% v! R3 o& T; U
s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep;, r* v& N9 F4 V, i6 q
s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf;
$ c4 ?( o# ~- H0 H. ~, T. l i=1;
0 z2 L0 b' Q$ d$ L) B1 t3 O while(!move(top,s[top].m+i))
! ^" g% |4 A5 Q( G i++;
/ H6 z/ ^$ T$ @/ t# k. _ }
8 P. J: b: X- n* g. R" q- u }
, D& f4 J/ j* L" I" j" o }//while
7 p* c9 m% a4 i8 r}//f21 L( e& x9 N5 d% q
//---------------------------------' j' C# W2 w' J; P
|