渡河问题

sally

渡河问题

$ X! f3 c5 P8 r N' q' @

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?

) Y0 J5 J, F& m$ O* W

程序代码：

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

#include <stdio.h> #include <stdlib.h> #define MAX 50 struct state $ _1 K- T% v, q: b$ I{ int man,sheep,wolf,cabbage;//0:在起始岸；1：在目的岸 ) I. ]9 y& j5 v- Q X; d f& R int m;//所采取的过河方法，(1--4) }s[MAX]; int count=0; FILE *fp=fopen("c:\\2.txt","w+");

8 N; o% w5 S' R) z& Q

void main() { : p. P( s6 o& V3 u0 [! x void f1(int ),f2();//f1试探递归 s[0].man=s[0].sheep=s[0].wolf=s[0].cabbage=0; ) H5 g1 M' _$ c1 r: b s[0].m=4; s[1].man=s[1].sheep=s[1].wolf=s[1].cabbage=0; " q H/ [' p7 Q% M f1(1); //f2(); : u2 w7 k% v& v/ l fclose(fp); 2 a4 ^1 g; S, E- b2 _& B printf("\n");

! ^- ?) z" X& u" n

} , C1 X# p3 X0 L% |//用m值决定的方法渡河，成功返回1,否则返回0 $ x6 ~5 c$ r4 k ?+ Pint move(int top,int m) { switch(m) ; [+ U6 t* S1 X' j; Z0 Y { . d4 {" t9 ^ `0 }& c- H //人带羊过河 case 1: //判断人羊是否在同岸 - f! T; F1 r3 C. D9 [ if(s[top].man!=s[top].sheep) . O3 z/ `( h! Q( U0 q6 E8 N* U1 \9 u return 0; s[top].sheep=s[top].man=(s[top].man==1)?0:1; s[top].m=m;//存储过河方法 ! i6 m* E' T* Z9 ^+ j: M break; case 2: : n0 V# N( Z5 w if(s[top].man!=s[top].wolf) ) P5 y. O7 \0 U# I0 ?3 ? return 0; $ R9 K8 X# A7 [$ \' l$ D8 g8 `* A! A s[top].wolf=s[top].man=(s[top].man==1)?0:1; 1 {9 J9 }% c4 e9 ?' ^2 ^# Y s[top].m=m;//存储过河方法 % v2 B% s9 \! ~2 ?5 s) \ break; 4 T. j6 j# R5 }" x case 3: if(s[top].man!=s[top].cabbage) return 0; s[top].cabbage=s[top].man=(s[top].man==1)?0:1; s[top].m=m;//存储过河方法 ; E4 T; ~- k9 J1 K7 x0 _2 w break; //人单独过河 / Y2 b/ W7 N7 `, V case 4: s[top].man=(s[top].man==1)?0:1; s[top].m=m;//存储过河方法 break; ' }+ |3 W4 S" A3 [# r }//switch return 1; }//move //打印过河步骤 % \3 _8 i7 x) G/ Bvoid display(int top) 6 U3 |+ h7 n( |/ g1 v0 x{ 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); , X/ t& L# _- {) M for(i=1;i<=top;i++) { 2 v% \3 _6 _; x; _& c( A4 C& o switch(s.m) 9 R3 w# ^5 a, P# Y w { case 1: if(s.man==1&&s[i-1].man==0) fprintf(fp,"人带羊从起始岸过河到目的岸\n"); ( P, R/ `& A: }% _. V: V else 3 Q C5 m3 |+ H5 I. D f fprintf(fp,"人带羊从目的岸过河到起始岸\n"); break; . c0 ~$ W& a) w: M case 2: if(s.man==1&&s[i-1].man==0) fprintf(fp,"人带狼从起始岸过河到目的岸\n"); / h( ?2 z- z5 t& X9 g/ F1 \* G6 n else & [) T; T' F/ _/ _2 T5 J. ?$ \3 J fprintf(fp,"人带狼从目的岸过河到起始岸\n"); 5 A5 g! g5 a2 {4 l7 D& m2 Z- [, h break; 5 W, p2 h. B( w; G6 Y+ z/ j case 3: if(s.man==1&&s[i-1].man==0) u7 H3 s' ?& v9 w- p fprintf(fp,"人带菜从起始岸过河到目的岸\n"); 6 h( L. o) @0 V5 i. q. h else fprintf(fp,"人带菜从目的岸过河到起始岸\n"); & c% y Z# a) W: u' U' M6 n break; case 4: " \7 R' U1 O y$ ^0 ^( u6 A if(s.man==1&&s[i-1].man==0) # h7 L! }& z, t# z3 m6 B/ b fprintf(fp,"人单独从起始岸过河到目的岸\n"); 0 v$ t; H. J" E else fprintf(fp,"人单独从目的岸过河到起始岸\n"); break; }//switch ) ]7 {: U, y- A! W. x7 u& S fprintf(fp,"state%d: man: %d, sheep: %d,wolf: %d,cabbage: %d\n",i,s.man,s.sheep,s.wolf,s.cabbage); / u( j) Z& T) s6 | }//for fprintf(fp,"All ferried successfully!\n"); }//display

( U; d6 j; R" c1 o9 c

//检查两岸合法性已经有无状态与历史重复性 int check(int top) O$ I% x3 A0 p. S% E' J+ Q% p- Y{ 4 M% x' Y( h' {( y9 p: X int i; //检查两岸合法性 , H# G7 V! s) T# v6 G if((s[top].sheep!=s[top].man&&s[top].cabbage!=s[top].man)|| % r2 T5 Q/ f+ E (s[top].wolf!=s[top].man&&s[top].sheep!=s[top].man)) return 0; //检查历史重复性 for(i=0;i<top;i++) 2 ]9 S# k' Q% E7 m if(s.man==s[top].man&&s.sheep==s[top].sheep&&s.cabbage==s[top].cabbage&&s.wolf==s[top].wolf) ) A( R; O" D- z! [+ @8 u return 0; / a9 E3 {; g; f$ K. M; q9 n //ok return 1; : G( D, |/ J: Z4 {( O& }1 w: Z} 6 }$ x+ l, I/ T: U' ]void f1(int top) ( x; f1 t. y* U0 M9 f3 [{ int m; * n8 u5 H( R* z; |( ]. G if(top>0)//0状态(初试状态应该是预先设置好的，所以要做状态1，故，初试top进来应该是1 { //对每次状态分别试探4中方案 for(m=1;m<5;m++) ! Q5 L3 b; q) ^% o+ Z: ^ { //每次方案的实施是在上次结果状态上做的 ' ~; v3 Z5 ]. V4 x! Y s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; $ k. @2 {- t2 Z6 Z# S5 e5 X s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf; //用方案m移动，同时检查结果 6 R+ e9 a/ |' D: O2 B/ i if(move(top,m)&&check(top)) ) _; I% _/ I+ r' A { / w+ x9 y- J% C) Q7 h: q if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf ) ) F% t0 l4 {' C5 [: ^ { //打印渡河步骤 display(top); b7 @. r& y. X& T( @ //统计方案个数 count++; fprintf(fp,"count=%d----------------------------\n\n",count); 8 T W1 J8 S: h9 @" q7 w if(count>1000) exit(1); } else ( W$ a; c$ ]" g2 I6 [4 t f1(top+1); $ @$ n7 b8 U7 i% Z4 W/ _) r6 G2 _6 w } 2 N- O; a- t, c7 B# \ }//for ; w" R& Y% I$ R' E) B: L }//if(top>=0) }//f1

& U0 c2 v2 M. U$ n' L

' w. |/ _+ x8 ?# y

void f2() 9 W$ ~% e! E, y{ int top=0,i; + `5 z1 O* m/ V+ C8 S, Q //开始时都在起始岸 + ]/ Y0 |& W! O4 I$ ` s[top].man=s[top].sheep=s[top].wolf=s[top].cabbage=0; //未开始渡河 s[top].m=4; while(top>=0) . x% d% g3 g, ], E0 O" ?( R { if(check(top)) { if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf ) 0 H) I# E/ T% T! w1 ?+ _ { ( }9 d3 m6 O4 m //打印渡河步骤 display(top); //统计方案个数 count++; 5 K5 l% z! k: |# P k fprintf(fp,"count=%d----------------------------\n\n",count); 2 @$ w' {" r: J/ P* G if(count>1000) exit(1); 9 J& P- R$ X& v( W7 m/ b) u //回溯 while(top>=0&&s[top].m>=4) / E' t1 ^% d' Y, Q" m* a2 y top--; if(top>=0) { + C0 R6 x$ j+ Q7 i4 c //在上次状态基础上准备做move s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; & G% U' g; e' H s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf; , P1 b- F w$ r" e* e% V' m i=1; ; j3 j( X& I" F" c4 Q; P. \ while(s[top].m+i<5&&!move(top,s[top].m+i)) : u7 b! a8 S% U8 G. w i++; }

} 2 t% [* P7 s% K8 y else { top++; //在上次状态基础上准备做move & Q; Q. \' u4 g8 Z6 [' g) M 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; i=1; while(i<5&&!move(top,i)) ( N0 K, }7 W; F2 `4 W& x. ? i++; }

} . [8 o& n2 ^0 t* ` else { //回溯 while(top>=0&&s[top].m>=4) 0 s' P3 i$ _4 r3 k, y- e1 } top--; if(top>=0) 2 U9 Y! _, H( f { //在上次状态基础上准备做move c- m$ X7 L" Q. O 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; 8 |: m |, @/ `* Q4 f i=1; while(!move(top,s[top].m+i)) 5 L# e# C! y- Y* @9 t: M i++; } } }//while , u" y/ Q# w; y) P& ]! e/ q( m}//f2 //---------------------------------

sally

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

huashi3483

呵呵，好搭档

lynn324

是用c编的吗?

mnpfc

呵呵，看过了