|
渡河问题
) [+ K' s& P. ] 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?
8 _; p! M N7 i( U- q+ ~8 ^
5 X, w6 |- ^, z: k( {7 k程序代码：
7 Y) B% e$ T2 J0 k
//以下程序在Win98＋vc6.0运行通过
& h( C6 b4 T! y R- a6 S#include <stdio.h>- p/ R. N4 v+ U3 Q2 D
#include <stdlib.h>) ^. b$ M! K, O- D( N) q- U+ }
#define MAX 507 z. h2 q2 [/ Y
struct state
$ Q4 }+ F& M' S# V! ?2 A4 O* N{
# I. R% a: N$ Y) M int man,sheep,wolf,cabbage;//0:在起始岸；1：在目的岸
* ^* O9 ]& O4 X int m;//所采取的过河方法，(1--4)
5 i. b8 j& Z) L3 O}s[MAX];9 k9 K8 L; h/ q' X- i% {0 r0 K
int count=0;
`5 m6 k5 w. L8 B% Q* q+ HFILE *fp=fopen("c:\\2.txt","w+");
* m8 ^) Z( V7 d& B+ nvoid main()
Q* B8 F4 n8 N3 M o% N6 x{
$ C; M$ v" ?! K4 E! j void f1(int ),f2();//f1试探递归
, T/ d w ~" l+ q7 U2 K& F* a% ^ s[0].man=s[0].sheep=s[0].wolf=s[0].cabbage=0;
; R6 t' I9 |$ R- _" B s[0].m=4;
, A+ E" s9 |" K0 I" g1 H8 v" _ s[1].man=s[1].sheep=s[1].wolf=s[1].cabbage=0;0 T( ^ R# M, d) a ~
f1(1);6 Q3 A% e. U, H5 P1 k1 p7 Z
//f2();
% l/ ?9 F1 v( W6 {/ E' f* ]0 h" y1 f fclose(fp);
1 p3 g9 z- g) [ printf("\n");
1 p& k6 U$ `8 A! q}0 I: A* @2 u- H% b" r# {
//用m值决定的方法渡河，成功返回1,否则返回08 P5 u; n" ~' u" K- z4 ^3 u4 p
int move(int top,int m)& A+ b! `$ V; s' c$ A! T3 h
{
+ F1 v7 N' _6 f) l+ } switch(m)& b8 o; t' ^* S3 {1 _2 [
{" F. [* T+ F9 W \+ i
//人带羊过河2 y: O$ T4 `* \" X! a4 p
case 1: ) }/ l! T& {0 K! T) N
//判断人羊是否在同岸9 I3 |$ |) J6 X; L5 q1 Q
if(s[top].man!=s[top].sheep)
9 h" g: C" m# }0 w return 0;
7 ]+ P& c; z3 e+ _ s[top].sheep=s[top].man=(s[top].man==1)?0:1;
# s% o, ]" S0 [9 m) d4 ` s[top].m=m;//存储过河方法
& ]' \- h6 U1 @7 v, r# q+ w( | break;1 ]$ Q5 j, l) @# M7 M: ~+ Y
case 2:
/ E) |+ C: v4 h8 @ if(s[top].man!=s[top].wolf)+ J& W8 e. I1 R2 i- m9 j; R/ S
return 0;6 u4 L8 j- a0 q! h; K$ {
s[top].wolf=s[top].man=(s[top].man==1)?0:1;
- l% X9 P! h8 J6 T5 L9 s s[top].m=m;//存储过河方法 Q; W% D7 y6 y2 ], H; j3 y
break;
" y0 H$ E! B! R1 W5 n5 N! S% W case 3:
" X+ z$ x2 ]$ {" y/ Y0 o- ^ if(s[top].man!=s[top].cabbage)8 F& l- d" S2 S
return 0;7 P7 ?5 b! D( k4 C
s[top].cabbage=s[top].man=(s[top].man==1)?0:1;
3 h% n# o( a$ F, d9 D1 l3 Z s[top].m=m;//存储过河方法0 ^( n2 J% P( q* h$ J
break;
- k6 d+ A6 Y% } G" [* W0 [' {% ?8 X //人单独过河9 O- E# T. a4 K* z W
case 4:5 a7 G! p1 d" D
s[top].man=(s[top].man==1)?0:1;
& C M% m( d# a% D0 l2 q2 V _ s[top].m=m;//存储过河方法$ B; u$ n( n. T3 _
break;8 m: U# {. a5 k- K6 S
}//switch
% D# g3 }$ G& a4 W return 1;
& A R/ m. _2 c9 e8 t' L& s8 i}//move
) |5 R) H( e! [4 x. E1 K//打印过河步骤# F, A ^' t5 I# S$ Y: Z9 \! U
void display(int top)
9 f! c* m D5 f9 N. V p; s @0 U{
" B" C/ n( V( f* _3 i int i=0;
* I. P2 @6 o2 _; V3 j fprintf(fp,"state%d: man: %d, sheep: %d,wolf: %d,cabbage: %d\n",i,s.man,s.sheep,s.wolf,s.cabbage);4 q! n" K" b; C9 f- {
for(i=1;i<=top;i++), e% D9 X2 Q U" f
{8 ~4 U3 S1 t5 ~6 n* z+ {
switch(s.m)/ f- \1 d' Q* N% [
{5 ]4 t- B8 `- ~! _3 H# X4 A7 U
case 1:1 r# \% r9 v- S
if(s.man==1&&s[i-1].man==0)3 A8 V. _0 M3 ], m* q/ g
fprintf(fp,"人带羊从起始岸过河到目的岸\n");# f; n* F, f9 h4 q! E" P
else6 P! m& Z7 b# g M: K) l! x" q
fprintf(fp,"人带羊从目的岸过河到起始岸\n");9 y3 i/ ~' ?! ^; B8 }' n
break;: U+ T0 ~" X" D1 S2 s3 d
case 2:
" n2 r& i/ ]& H if(s.man==1&&s[i-1].man==0)5 p0 K) v* _ b( R4 N5 x9 n: o6 `1 H
fprintf(fp,"人带狼从起始岸过河到目的岸\n");1 Y: l/ W7 k5 C! P
else
) J; k5 I+ v$ O+ Z fprintf(fp,"人带狼从目的岸过河到起始岸\n");8 M0 a v& K6 G& C
break;5 n' |8 [# y k& t+ ^1 k
case 3: p% B$ d% Z$ D. ^8 T/ z
if(s.man==1&&s[i-1].man==0)7 ?. w3 b: d2 m( J8 |) f8 L. F5 ~
fprintf(fp,"人带菜从起始岸过河到目的岸\n");/ X" E h1 k: B4 z; j8 H- w3 _8 K6 p
else N1 `# ^0 n2 m
fprintf(fp,"人带菜从目的岸过河到起始岸\n");
* d8 K/ B! [- G' J break;2 O7 @( c' X$ a
case 4:7 D e) V; A* t
if(s.man==1&&s[i-1].man==0)8 G6 N5 c" c$ q! S
fprintf(fp,"人单独从起始岸过河到目的岸\n");5 a1 C: D6 x3 y6 q, C+ w3 [; j8 Q
else% C8 ]' n) V' l! ~. C1 ]2 x
fprintf(fp,"人单独从目的岸过河到起始岸\n");+ q( _# y6 \" {7 q$ S
break;7 P3 I7 R: Z9 L+ l
}//switch* s2 a* e1 I+ H% R3 r7 e
fprintf(fp,"state%d: man: %d, sheep: %d,wolf: %d,cabbage: %d\n",i,s.man,s.sheep,s.wolf,s.cabbage);* p( v) |0 a! B8 {
T. W/ W7 C% I, g, j" \* ~7 n }//for* E7 X+ B# A/ h/ Z7 p3 }' H* C0 Y
fprintf(fp,"All ferried successfully!\n");
6 }. b) t& H y8 p& w( L}//display
5 p* c/ t6 }" \: [6 a; N
//检查两岸合法性已经有无状态与历史重复性
4 }' z$ i: w% ], S/ n5 Pint check(int top)" L+ h+ H: [7 T1 b2 o9 C
{
5 g/ y: I4 C' J, o/ {7 d9 g int i;* H( f1 @9 d: c5 v H
//检查两岸合法性
' Z$ }: G+ y1 K. v/ m! \) ~ if((s[top].sheep!=s[top].man&&s[top].cabbage!=s[top].man)||
" y% }$ a+ Q- |+ r+ M( ]8 ~* i (s[top].wolf!=s[top].man&&s[top].sheep!=s[top].man))
! B d) [6 P+ I* Z" w: c6 a3 |, @ return 0;7 g4 R. C" {8 o
//检查历史重复性* P5 J8 A4 q! ^' `2 q6 n+ K3 a
for(i=0;i<top;i++)
& c) n# K9 i* T O if(s.man==s[top].man&&s.sheep==s[top].sheep&&s.cabbage==s[top].cabbage&&s.wolf==s[top].wolf)' ?* o* d( r# c) I) J8 |. |
return 0;
3 N, x6 f" R6 A5 `3 ?7 z/ K+ w# I //ok
0 N: [ J& L5 y return 1;& W. \* D3 D: s+ G" {% l0 L5 j
}
, j8 i5 w4 s# R( U, pvoid f1(int top)
% ^' P9 `( U* ^# ?. K7 D J{# I( _; k* d* r" g+ k
int m;: \* ?' d% X2 g
if(top>0)//0状态(初试状态应该是预先设置好的，所以要做状态1，故，初试top进来应该是1
5 e, W/ m* V3 J+ p; G$ y0 Q { //对每次状态分别试探4中方案
2 G# U# z3 X! M& }; y: y6 p! j; a; D for(m=1;m<5;m++)
: o5 y. B2 H7 K2 Q/ _4 B9 o {: t) c: ^* s0 z" p+ ^8 }1 D o% K
//每次方案的实施是在上次结果状态上做的, k- I' |9 ]5 {
s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep;
3 {0 a+ x' {" C! {- T- v- {/ l s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf;
: M; C Z0 @- A6 j: I% i2 L //用方案m移动，同时检查结果+ G0 H* B2 L ?3 L* |; v2 X: \
if(move(top,m)&&check(top))
9 s9 g3 l& u, p8 z7 ~ {: e. ]) Q& Z& J4 `
if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf )" n% q B0 L5 L! D% {* {0 P9 k
{
9 h# a# ~$ b1 F# V7 j9 S //打印渡河步骤
* o4 Z6 f$ d5 \4 C display(top);
* ]0 h- A6 x6 n0 s7 p! G //统计方案个数
' P' i& ^/ j+ Y4 Y count++; 4 U: G3 b* b* _' t3 J" U
fprintf(fp,"count=%d----------------------------\n\n",count);
) @1 t8 K% J% C1 ?& O$ U4 g2 ]; \, r if(count>1000) exit(1);
+ h, p2 z0 T: w }
0 C# w9 W, [* L5 z) Y" I* ]* d else
9 y6 A; Z A7 f7 u! L, }2 z f1(top+1);' P1 g' f, k+ r* B) c' w1 w
}7 ]7 W% F0 {4 D. c6 j
}//for/ g! R; R P: H, I' m
}//if(top>=0)
; t$ W7 e( L+ ? a}//f1
& K. I, W( D. p% X* d ( h( a" T5 Y2 Y# v- U9 m# o
' x1 _3 N+ a+ V% z; ]3 J8 P6 i / C J0 C1 X, K
void f2(). f) [8 t: B7 G9 Q+ ~: i
{2 A# z! { U" @# V1 c
int top=0,i;
- y/ B3 ?+ B7 o( ? //开始时都在起始岸
2 N3 C! V$ F7 v6 { C s[top].man=s[top].sheep=s[top].wolf=s[top].cabbage=0;
0 j1 y, p8 n3 \$ X- k3 O4 O+ c //未开始渡河
- }* ^3 [. U+ P6 B& u2 [ s[top].m=4;4 ]2 n& w7 G* n' B$ a1 C$ I
while(top>=0)
+ F2 d) H7 R1 ?8 `! ?; @% v- p8 { {
2 r: s* S, O& P& t7 s8 s if(check(top))/ r! Z1 E. A' ~9 r) {/ [3 n" H: E# {
{7 B8 q1 d& [6 ]: P: V/ X, M
if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf )
% ]: r8 @1 Z, v/ Z {
+ q& t) b! N- M1 [ //打印渡河步骤& ?, r6 p4 Y' G5 O1 T/ U7 d1 a
display(top);- V. y- y8 k3 M3 M4 P# `+ x
//统计方案个数0 ~: L- H* x. x
count++; ! R& _% |6 B8 u$ W W
fprintf(fp,"count=%d----------------------------\n\n",count);' v/ J6 O! p3 p; y; Y$ M" U2 b( `9 p1 `: i
if(count>1000) exit(1);) S7 }: p" G/ N
//回溯/ T( L& {* d! a
while(top>=0&&s[top].m>=4)
" e0 j+ \9 B5 @* H) d9 t9 U top--;5 z1 {+ m* q1 K/ a# R- h+ @
if(top>=0) i5 J! X, S) d3 u
{
- ~/ u* E% G8 B# }& X! M //在上次状态基础上准备做move
. f, B4 H; Z$ z- R5 C' |2 b s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep;
* w4 s! O$ s) C2 j s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf;% R' D6 ]5 O3 [0 D! i; x
i=1;
1 B0 |! o$ W- c- [* e2 k' C while(s[top].m+i<5&&!move(top,s[top].m+i))% y+ _/ {' ^, i' F t) L2 |1 K
i++;
0 p, L" J& h" G } # u1 `$ Z" H: ?" ?! x
}0 u7 Z( d# O, ?7 Y& C
else m0 q* |5 h- s* W6 ~
{! g. K0 c D. i5 |* v/ u
top++;
- d9 C8 T# r0 J; d //在上次状态基础上准备做move
3 L y+ W1 W. d6 u3 t s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep;
9 x: j8 P, q* e' f s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf;
! S% E2 R- U; }/ i" a i=1;
6 b5 z& g. i; p, j" I while(i<5&&!move(top,i))/ d# w' h8 l1 ?- B, f6 e8 m
i++;
6 o" |- |7 c$ n5 Z" h: M+ g1 z } 8 o/ h5 D& c: @
}
" k3 j( S; i1 X, G H4 D8 D else
% I/ a+ ?7 { \) @9 q- R T5 }# ^0 h4 l {
' N: j8 C& L0 e+ c: z; h7 x+ q //回溯6 m6 J- h* o8 R; F9 a! V! U0 r
while(top>=0&&s[top].m>=4) / w3 e) a% N- O# B: V4 X
top--;5 N* {/ B" I" N& q
if(top>=0)
" E8 M! U* a; d8 m! V {
4 b( ^2 R" h+ C, D0 o4 H$ n. B //在上次状态基础上准备做move$ B( t8 H6 ~) L+ r2 i
s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep;
, |1 S; i2 E2 b o s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf;
) Z3 O6 O7 a; q' |6 Z" M, ? i=1; ! q* \" ?9 }, s! M# W8 B+ r$ s
while(!move(top,s[top].m+i))
/ ]+ c) a3 e, ?7 d1 n i++;
% M w5 G& E0 L+ v, { }
! Y4 H. U" ]) b6 c }" s1 V+ k x9 R5 r& W5 \
}//while
6 R }1 H: ^# L$ L, R}//f2
0 `. S! U# t( m5 m# A4 W& d//---------------------------------
1 C T ?+ y }# D3 v1 S( { |
IP卡
狗仔卡
发表于 2004-6-5 11:57
转播
淘帖
分享
收藏
支持
反对
微信
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
抢沙发
显身卡
