|
渡河问题
0 F! e$ ]9 z6 B; [2 D& X# p$ l" V: R 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?
B% P, ~8 p9 @% C* ?
1 T) t- w8 W( E: n程序代码：
3 T( q7 S4 C2 ?1 O) |
//以下程序在Win98＋vc6.0运行通过
* N. X+ J, X; K7 W, {#include <stdio.h>
! M9 ]8 h+ J' R" |9 T2 P#include <stdlib.h>* O) u9 R. o# b& ~% b) ?
#define MAX 50# \- t' G8 @' b
struct state0 {- l; e8 H9 M+ c+ I& E% X0 w1 P
{3 ]5 P) ~" K- t# K- y# C1 B
int man,sheep,wolf,cabbage;//0:在起始岸；1：在目的岸# R1 f8 U3 e% |0 e: k- Z7 }
int m;//所采取的过河方法，(1--4)
6 v- f" o) Z C+ h}s[MAX];
) x1 F4 C+ J: Z) q6 \" Oint count=0;. o6 F, ], _: @; p! D( x8 i
FILE *fp=fopen("c:\\2.txt","w+");
; y; B; \- F, P1 | {void main()
, j- T' x7 M3 e6 }/ H{& W* R! k: c! {' X* p
void f1(int ),f2();//f1试探递归6 b( c6 Q9 i5 q* j
s[0].man=s[0].sheep=s[0].wolf=s[0].cabbage=0;
; N0 z$ ?. E9 F! A- W3 k7 U: I/ V s[0].m=4;
- C& i- K' e) ?# Y1 r+ d s[1].man=s[1].sheep=s[1].wolf=s[1].cabbage=0;
6 T1 ~# i# Y# R8 m8 B0 A3 U) c+ O f1(1);3 p; @) \9 u) G# x
//f2();
; w9 m, C7 L! r5 A* Q, Z; i fclose(fp);/ u3 X& C m7 J
printf("\n");
0 Y* A' G" n9 d
}" |3 X7 o6 Z1 B: J( [/ Q! C
//用m值决定的方法渡河，成功返回1,否则返回0
# N7 y3 u% A3 F( b% a* Aint move(int top,int m)
4 L, \& n9 T+ s' |' n+ d v{
0 G( B5 x( M* ]9 x7 V% D4 @' ^ switch(m)6 J7 B5 @! a3 |3 C6 [" N8 f
{( M1 d8 S: c+ X& a' s
//人带羊过河
1 A3 j5 K: |% y* c( g7 Q case 1:
* p r: |7 k, U3 w! s: j/ Q //判断人羊是否在同岸6 M7 P. z. e) ]) A+ _4 q+ B# h* o
if(s[top].man!=s[top].sheep)
' V# ^9 e6 o9 C7 m' Q return 0;2 D! @7 d n7 b6 _4 P* J
s[top].sheep=s[top].man=(s[top].man==1)?0:1;
' O7 X- z6 j* j7 T s[top].m=m;//存储过河方法
- w) F# l' F+ v! s- W7 i! x break;
& A" R% H7 I7 ~" f* l4 X+ _9 W" o case 2:- M2 T$ H( b5 {. g2 {4 U4 v6 B( ?
if(s[top].man!=s[top].wolf)8 N& Y8 f7 R. L1 Z" {2 I1 q
return 0;/ P) s6 A) B) O; g8 e* [
s[top].wolf=s[top].man=(s[top].man==1)?0:1;
4 H- w- X+ p; m+ C( \ s[top].m=m;//存储过河方法9 F) R2 a* X- S& K
break;
0 a2 i9 [9 w, R/ H$ d9 m case 3:
" y. g: J! a7 f if(s[top].man!=s[top].cabbage)* c, T/ e! Q& d6 ~% d
return 0;4 D" A% v/ G! C- i2 e% n
s[top].cabbage=s[top].man=(s[top].man==1)?0:1;% o& H3 Q2 U1 J' V
s[top].m=m;//存储过河方法
, W* o F3 d% J) S' K break;
6 O6 D- g6 L* H; S; Z4 K //人单独过河- a& l0 K; I# D+ g% e+ j- K5 Z
case 4:
% u& K- A5 ?! r1 f9 } s[top].man=(s[top].man==1)?0:1;( D( D' a5 }1 ] y0 f5 m: L, ?! R
s[top].m=m;//存储过河方法- {/ ~' e% N5 P2 X' j! O( i7 @
break;
. Z2 I5 O( X. s( P! O9 x* N( P }//switch& L+ k9 d4 n l# a9 d
return 1;
/ |( E# a+ ~+ f* `}//move2 t/ I+ z+ d* s5 Q
//打印过河步骤
: N! e9 J# t1 ~: |& M8 z0 ^void display(int top)1 M) _5 D+ K! @2 ]! L: d
{, @4 h8 ]' r: c0 M. J/ M& ^" u
int i=0;
* c1 q Z- n2 G6 G9 \& [ fprintf(fp,"state%d: man: %d, sheep: %d,wolf: %d,cabbage: %d\n",i,s.man,s.sheep,s.wolf,s.cabbage);( ]+ K2 c0 t _% w0 J
for(i=1;i<=top;i++)
/ }7 [# O! Z6 G# j+ \ {
/ }- x6 K! g9 l0 F# R/ H9 f switch(s.m); k# f, u( S! i6 Z! M" z
{
5 }6 V3 m9 m/ t/ X) @3 q$ c. { case 1:( X4 y0 R, r% Q- g% R
if(s.man==1&&s[i-1].man==0)0 L4 v# ^6 i& B# ^! Z( ]
fprintf(fp,"人带羊从起始岸过河到目的岸\n");# p& b: s4 B& _
else
' Y% P2 K- O% a! a% Q4 x fprintf(fp,"人带羊从目的岸过河到起始岸\n");! ` W4 @# h# b% h$ C0 k
break;
; J7 t4 P; ~ L9 E case 2:0 q4 E: j. y2 r
if(s.man==1&&s[i-1].man==0)4 ?* u) q; i0 F( {
fprintf(fp,"人带狼从起始岸过河到目的岸\n");; ^# {6 g! B" I$ ?+ Z
else8 K+ o$ ^" ^" r4 Y( N: p M
fprintf(fp,"人带狼从目的岸过河到起始岸\n");
3 d9 b5 a! S) C- S. \) ^ W! W2 r break;
; r! c1 G1 B) o& h$ @- T2 i case 3:
* S$ s. h, _1 ] if(s.man==1&&s[i-1].man==0)" n, u, [% D8 w7 y$ ^
fprintf(fp,"人带菜从起始岸过河到目的岸\n");
5 d) P& J9 N j else' w; C( `, I5 g3 o% H
fprintf(fp,"人带菜从目的岸过河到起始岸\n");2 o4 Q2 n% |9 p& C% U# _/ ?) z7 Q
break;- ?' U- w& C; W
case 4:3 R( k4 x* g! @- S$ i+ \1 U
if(s.man==1&&s[i-1].man==0)
+ I; a' a/ @. B/ E! s fprintf(fp,"人单独从起始岸过河到目的岸\n");1 c% \0 j6 X$ U A/ J- Z- G: h
else
2 @/ W" p( F1 r. c" t+ H fprintf(fp,"人单独从目的岸过河到起始岸\n");
# h& Y, Q* z" a* L8 L4 w8 L" a break;
3 d+ A& \1 x5 p" H/ c }//switch
- h) I* J6 g2 \/ _ C4 h fprintf(fp,"state%d: man: %d, sheep: %d,wolf: %d,cabbage: %d\n",i,s.man,s.sheep,s.wolf,s.cabbage);4 T# b0 [, s, g" h4 g6 L( V+ n* H
9 W' y/ s2 h+ ?. y% _8 E5 a }//for
9 ?) S! c. o4 K' n4 {3 kfprintf(fp,"All ferried successfully!\n");
3 |; e) D- N3 x" c3 e}//display
* ]/ B# s9 x& I) p+ y
//检查两岸合法性已经有无状态与历史重复性; Y5 b$ K8 l( c' `- {+ v) v
int check(int top)$ J) ?3 R' E$ k) M
{
" `( f* K) |: M0 r int i;! P: U- d- N, r1 P
//检查两岸合法性 b1 S+ X. P, T% }4 c) s
if((s[top].sheep!=s[top].man&&s[top].cabbage!=s[top].man)||; C1 ~% J: |& N3 O" V& P
(s[top].wolf!=s[top].man&&s[top].sheep!=s[top].man))
$ [$ ?0 D' y: ^6 t return 0;2 ^4 P* N2 N/ _5 N7 w
//检查历史重复性
$ i2 T9 u/ S; z r. o8 j for(i=0;i<top;i++)
1 K5 u! N" D) F8 G# Y: s if(s.man==s[top].man&&s.sheep==s[top].sheep&&s.cabbage==s[top].cabbage&&s.wolf==s[top].wolf)
. Z$ F* Y/ j( D2 a, ^7 u% N( ~0 K6 f return 0;
( @$ K7 _( x' i" e/ ~8 F //ok
7 Y# F$ {6 l! w& C1 s return 1;
; M. J# f9 H" H}, Y0 `' _3 n/ |, B2 I8 f
void f1(int top)
% Z6 r# d" a- T* L{
4 g& C" u2 I& ]( @6 \ int m;) c, e. H+ p# }9 H7 G0 \3 [
if(top>0)//0状态(初试状态应该是预先设置好的，所以要做状态1，故，初试top进来应该是1
) C5 F+ z% O3 F: [! A r6 |* P { //对每次状态分别试探4中方案; y8 M# m8 F6 ^3 G( q
for(m=1;m<5;m++)) X9 P) Z) A$ v, Q, i. j( L
{
$ J" i" a e8 h! A/ B! C3 @ //每次方案的实施是在上次结果状态上做的. ^6 ]+ W7 M' p7 x2 n- \; @
s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep;9 `$ @/ U) \4 w7 {
s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf;
( _: p" H* v8 b( l. m" L3 n4 Q: N //用方案m移动，同时检查结果' m0 g! k& o% u3 O" M
if(move(top,m)&&check(top))6 K8 ^+ {8 y) U! t; F
{
0 c/ K1 s P5 I4 E if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf )
# K3 ~1 l* Z( V5 @# [6 Y3 Y, Q9 \* l {
/ y+ T/ u$ N0 r9 [% [' j/ z w0 K: W //打印渡河步骤* v4 M+ O. @- @) t
display(top);
7 i; E( @9 b/ ~ //统计方案个数/ B. A1 p; d& J5 I3 e4 U5 |
count++; ) Y" ^1 t/ E1 E0 S
fprintf(fp,"count=%d----------------------------\n\n",count);8 J3 Q- f i1 V3 L. M& F
if(count>1000) exit(1);
; Q' ]+ o3 Q7 S) O: R5 w }
/ {2 X& [0 q) D else, A) x# q% c3 U, v- W! Q
f1(top+1);
- X2 h5 ^1 f6 a2 X k) O }
0 N9 k- @" H8 L, F" O }//for( `; N8 c( g. y( t9 a: ?
}//if(top>=0)
4 p5 n6 _8 E( k# `}//f1
B. c3 |: r2 F4 W. N, p
) D; F7 ?% `- f& }8 W
' t! s s& f4 |# p$ X" i4 t
1 ?9 q1 H, j1 ~% A
void f2()' Z; M9 ]) z3 u! m! b- c- N8 P
{+ F( X2 t) I% h# `/ ^+ i2 ^
int top=0,i;" T- w5 ]* Y* C; C, x; ]2 ^$ i w4 }) x
//开始时都在起始岸
! m' [- Z) |; s5 c; j- D6 u' [ s[top].man=s[top].sheep=s[top].wolf=s[top].cabbage=0;! G2 O: C6 h/ G" F
//未开始渡河1 L1 I% z! p- |4 h: r w4 O& w# W
s[top].m=4; Z- l. n0 ^+ L. q5 |
while(top>=0)9 G7 o/ A7 Y% L) ?
{" r3 i) H. b( [5 O6 w/ u3 X6 |
if(check(top)), D' o) H% y$ @; |' T
{8 A. o; X$ N5 ^6 {- [8 W5 w$ D
if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf ) r5 o3 s% \2 q# H9 B
{
7 U0 W5 r8 U# t //打印渡河步骤7 c% e7 C# x6 ?6 U
display(top);. W; B& F% {# ]
//统计方案个数 a/ V$ z# M$ G& b3 Z- s6 `
count++;
- a1 J$ ?) [( i( u fprintf(fp,"count=%d----------------------------\n\n",count);" e- A# N) U( a* n
if(count>1000) exit(1);$ }2 E. ^) x' i x( N6 X6 G3 b
//回溯
; m" n2 n' ~. a# j0 z" O while(top>=0&&s[top].m>=4) ! ^' l" Z: Y# D F
top--;
4 N9 _# k% F5 [ n! J4 L* W9 i7 Z if(top>=0)1 S% V m3 f& J) S4 u$ _
{# |: b. V$ [6 A. j) y3 w: Q
//在上次状态基础上准备做move
+ ~; ?* |& D' m g; p% Z( I4 v s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep;* S9 A* x+ e7 w3 H
s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf;; ^' P" e3 Y3 J
i=1;) u( |. T- N8 t& u
while(s[top].m+i<5&&!move(top,s[top].m+i))
, m1 e. @# j$ B/ J i++;) ^# }9 B+ z) u6 ?7 U' L6 ~# Z0 n
} 6 y# d+ m' N, N( l4 D9 D4 D
}9 t. ]+ s" x* F) k, X0 d' [" v" \
else
6 O3 s- _, h6 a/ z! h7 C7 V {* n$ C0 P* V$ N" q
top++;
4 H. r0 Y- m7 c' `3 I- j //在上次状态基础上准备做move
0 d' k% ^# g" B! D. F$ W. j+ g s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep;
) J0 n) }& ~' G+ h: a s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf;0 M5 W: X% w% a" y
i=1;
& n# C/ Y+ R6 |" o6 q+ ]( j9 r- |! l: k while(i<5&&!move(top,i))6 d$ G; f$ `+ `; S4 J+ |0 t( k
i++;
( k8 Q1 `. g6 H } ! k1 x; q( k9 o" u8 o' _# t
}
2 J3 V0 l9 t8 c; n else
) J9 C1 x* n# I* s' Z% w3 t B8 D8 i {
* `, w$ j1 v9 J# {5 n1 @ //回溯3 s& C% w! \' t4 J
while(top>=0&&s[top].m>=4)
6 U2 V4 [. I; b! ?5 D top--;
1 f ]( _0 ?1 `0 O if(top>=0)
& Y% c# O) V3 ]7 p- n {0 c3 ~; N* p9 v, f
//在上次状态基础上准备做move% e2 v5 E& G% a& ]
s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep;
, H; k# c4 [) p+ \2 N s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf;
9 H; E8 ]+ D' g$ P( z* G( P i=1;
) ?3 G; C& d% q3 e! C while(!move(top,s[top].m+i))2 X; y$ a t8 u5 x
i++;
& l# y% t* t% j) L }
! r+ E) V9 O: F }
2 G: u1 A2 v" U }//while$ D2 L8 \; h5 X% m9 D
}//f2' |( c# ?0 r" @6 }: L9 R1 H5 T
//---------------------------------" h) _9 a% H4 M& |# n1 O* d
|
IP卡
狗仔卡
发表于 2004-6-5 11:57
转播
淘帖
分享
收藏
支持
反对
微信
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
抢沙发
显身卡
