渡河问题

sally

渡河问题

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

程序代码：

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

#include <stdio.h> ; F& c' I) i+ e6 X% I# S0 f. a. z#include <stdlib.h> #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：在目的岸 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 v

void main() 0 N9 l7 G8 h2 Q. n% p{ void f1(int ),f2();//f1试探递归 s[0].man=s[0].sheep=s[0].wolf=s[0].cabbage=0; s[0].m=4; 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); printf("\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) { ( P* w5 K- h3 M3 ?3 @ switch(m) { //人带羊过河 - u* H3 f2 A1 x" d6 v8 {1 w case 1: //判断人羊是否在同岸 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; s[top].m=m;//存储过河方法 break; 4 l+ i" M; H& p( ?$ U4 {! R( V# n case 2: if(s[top].man!=s[top].wolf) 4 h: l: M* u. E% E3 ?' j return 0; s[top].wolf=s[top].man=(s[top].man==1)?0:1; s[top].m=m;//存储过河方法 break; 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; s[top].cabbage=s[top].man=(s[top].man==1)?0:1; s[top].m=m;//存储过河方法 break; //人单独过河 case 4: s[top].man=(s[top].man==1)?0:1; s[top].m=m;//存储过河方法 & K( M1 q1 S. a5 @; Z break; ! Y, g$ v7 c9 D. ~) s, }' e6 g$ ? }//switch return 1; }//move //打印过河步骤 void display(int top) ' R2 O, ^) u6 p) K5 O4 M% q: E( U( |{ 5 ~, p8 V2 C _ 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); : f- b/ T7 P1 f. { for(i=1;i<=top;i++) # o4 b7 D( V2 W: p { switch(s.m) { 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"); else 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) fprintf(fp,"人带狼从起始岸过河到目的岸\n"); else n9 W- f0 {' N7 J fprintf(fp,"人带狼从目的岸过河到起始岸\n"); 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"); else fprintf(fp,"人带菜从目的岸过河到起始岸\n"); break; case 4: % f, W1 m' \8 H: `& @; K if(s.man==1&&s[i-1].man==0) fprintf(fp,"人单独从起始岸过河到目的岸\n"); ; r- }; G7 K7 e% b) {: w) g, u% h else fprintf(fp,"人单独从目的岸过河到起始岸\n"); break; 2 T5 {8 ]0 t' @$ ~) z }//switch fprintf(fp,"state%d: man: %d, sheep: %d,wolf: %d,cabbage: %d\n",i,s.man,s.sheep,s.wolf,s.cabbage); }//for fprintf(fp,"All ferried successfully!\n"); 8 O; j9 e2 _) g6 F% ]3 g% t7 Z: z}//display

//检查两岸合法性已经有无状态与历史重复性 n; f2 Q; H$ n: Oint check(int top) { int i; //检查两岸合法性 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; //检查历史重复性 & K- f$ S8 g% p* N5 a for(i=0;i<top;i++) 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 //ok return 1; . h5 R! X1 _, ^$ S. M! i; @, ~} void f1(int top) { 6 z2 g* f9 x* B; x int m; P& p% X5 o* n: T3 R- z if(top>0)//0状态(初试状态应该是预先设置好的，所以要做状态1，故，初试top进来应该是1 { //对每次状态分别试探4中方案 * O: Z+ _/ m* U! z) I for(m=1;m<5;m++) { //每次方案的实施是在上次结果状态上做的 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; //用方案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/ } { //打印渡河步骤 + i6 m; \1 F% C3 n display(top); 9 W+ {+ k5 n4 ]# Z- l //统计方案个数 count++; 0 G! M( e/ Z3 i' x# J fprintf(fp,"count=%d----------------------------\n\n",count); if(count>1000) exit(1); 8 ?( X- m# J+ t } else ; E* U7 }/ [) K+ S( Z f1(top+1); 6 x' f1 a9 p, ^/ \ v$ r$ E } }//for }//if(top>=0) }//f1

3 ~( M$ E( Z" ?

E; w6 D+ N# l# U. i' ivoid f2() { 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 //未开始渡河 s[top].m=4; , a; x; q: K1 q1 l while(top>=0) { " @# 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 ) { //打印渡河步骤 display(top); //统计方案个数 count++; 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 //回溯 while(top>=0&&s[top].m>=4) top--; - m5 y- e5 {: S. A8 ? if(top>=0) 6 z: E( T9 Z6 m9 m# k { / l/ J/ Q: ~( `; Y( Y. a //在上次状态基础上准备做move 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; 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++; }

& [: p' X: h, R

} ' {. q z" k$ S" P else { / G5 Q$ Y; b% H# y' A* V: D5 a top++; ; E3 y/ Q* h/ B' ?) M% H //在上次状态基础上准备做move 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++; }

% y0 I) |2 w' u% Y+ W* c

} C* W, W8 V: `: U) C else { & a c# e8 |4 [, ?0 ~ //回溯 while(top>=0&&s[top].m>=4) * ?) \& \! W/ k9 z6 w# U top--; if(top>=0) { //在上次状态基础上准备做move 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; $ 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}//f2 //---------------------------------

sally

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

huashi3483

呵呵，好搭档

lynn324

是用c编的吗?

mnpfc

呵呵，看过了