渡河问题

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?

, [' N4 `2 m2 Q

程序代码：

, ]2 `4 M7 o3 m: n) m

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

#include <stdio.h> 3 {& R5 w) m' P#include <stdlib.h> #define MAX 50 struct state { int man,sheep,wolf,cabbage;//0:在起始岸；1：在目的岸 ! }$ J) g9 v' l7 m s! Y, ? int m;//所采取的过河方法，(1--4) }s[MAX]; " G) W' \' K, ~' m* U# [- ?( oint count=0; * j8 t5 k0 S$ K+ v" |4 i. o: wFILE *fp=fopen("c:\\2.txt","w+");

void main() { 3 b( B* u W' |2 G* B, {0 D void f1(int ),f2();//f1试探递归 s[0].man=s[0].sheep=s[0].wolf=s[0].cabbage=0; ! B- j# p( G9 e$ \ s[0].m=4; s[1].man=s[1].sheep=s[1].wolf=s[1].cabbage=0; * k# Z8 V$ [& l" Q, V z4 T0 Z3 a f1(1); 7 ^2 ^# V C l. F/ O) W1 }6 |8 u //f2(); fclose(fp); 0 z% K' L- B8 Q F2 H$ ` n; j; g% ~% X printf("\n");

} //用m值决定的方法渡河，成功返回1,否则返回0 . i* z% H( j& G1 C- Vint move(int top,int m) 6 C @2 V+ D2 W{ switch(m) { //人带羊过河 case 1: //判断人羊是否在同岸 - u, O1 Q( i1 }+ D- g" n& J if(s[top].man!=s[top].sheep) return 0; s[top].sheep=s[top].man=(s[top].man==1)?0:1; ' W. N& E7 @3 v6 [9 F* X s[top].m=m;//存储过河方法 3 n7 I! E# e3 i1 n. J break; % T: e& H" r9 z/ w1 C case 2: & J" U! B6 m2 l" M+ Z a if(s[top].man!=s[top].wolf) : r3 _2 U$ P, G5 @ \. H) X1 X: s return 0; s[top].wolf=s[top].man=(s[top].man==1)?0:1; s[top].m=m;//存储过河方法 " t( K8 V& ]1 x break; case 3: if(s[top].man!=s[top].cabbage) return 0; 3 b1 F% V+ i4 V& S7 q" d4 I' E 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;//存储过河方法 % {1 @$ D6 U# u, ? break; " i, O3 u5 @5 w* J$ x' f }//switch $ N/ f J6 Q& J; [ }3 s, k( T/ w return 1; }//move //打印过河步骤 , k8 J3 r1 [- _( Y4 qvoid display(int top) { # z) Y( v* Z* n' X int i=0; 0 @4 q7 M a+ y/ H fprintf(fp,"state%d: man: %d, sheep: %d,wolf: %d,cabbage: %d\n",i,s.man,s.sheep,s.wolf,s.cabbage); for(i=1;i<=top;i++) { switch(s.m) { case 1: if(s.man==1&&s[i-1].man==0) fprintf(fp,"人带羊从起始岸过河到目的岸\n"); else 5 i% x; q6 @5 R# i fprintf(fp,"人带羊从目的岸过河到起始岸\n"); break; ' E8 c% J- |9 n6 Q+ j2 A7 ^; S case 2: if(s.man==1&&s[i-1].man==0) fprintf(fp,"人带狼从起始岸过河到目的岸\n"); " Y5 d, g% \" t$ S else fprintf(fp,"人带狼从目的岸过河到起始岸\n"); * ^' |+ B5 |7 E break; case 3: if(s.man==1&&s[i-1].man==0) ! [; a- z' k6 i0 H% T fprintf(fp,"人带菜从起始岸过河到目的岸\n"); else fprintf(fp,"人带菜从目的岸过河到起始岸\n"); / B+ e* _7 y( w$ S M7 Y) t# d break; case 4: if(s.man==1&&s[i-1].man==0) + L" P& f. Q: f% | fprintf(fp,"人单独从起始岸过河到目的岸\n"); else ; F, O8 U- a1 X0 N7 K0 w2 ]+ O fprintf(fp,"人单独从目的岸过河到起始岸\n"); / w! e" X& ~6 j0 O! e5 L break; 4 F d' g, @( E, [5 F6 ?6 C }//switch fprintf(fp,"state%d: man: %d, sheep: %d,wolf: %d,cabbage: %d\n",i,s.man,s.sheep,s.wolf,s.cabbage); + O+ _: @% n! t- Q }//for 1 m( c8 j" X( ]2 @, v# E. kfprintf(fp,"All ferried successfully!\n"); }//display

1 d9 J9 j5 S, \$ E0 {. I# n

//检查两岸合法性已经有无状态与历史重复性 : j8 c% o9 I' m7 P) t$ m. e/ Wint check(int top) 8 X' g! o! l& J/ {+ o( H* c{ ' ~7 K3 ~! a2 @# o" a) _4 V int i; //检查两岸合法性 2 o* O; J4 c4 o' t; ?7 Z; { if((s[top].sheep!=s[top].man&&s[top].cabbage!=s[top].man)|| ( @% O; ?) _/ r8 l! S (s[top].wolf!=s[top].man&&s[top].sheep!=s[top].man)) return 0; //检查历史重复性 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) 0 L: o; C9 F" g+ \% k1 B return 0; //ok return 1; } void f1(int top) { int m; : q( A, G! T9 k/ x$ z! V! Q! u: { if(top>0)//0状态(初试状态应该是预先设置好的，所以要做状态1，故，初试top进来应该是1 { //对每次状态分别试探4中方案 for(m=1;m<5;m++) 9 ^7 `% V5 P( w: n9 |8 B( E { //每次方案的实施是在上次结果状态上做的 # _# o6 ~ e# l( |" S& J9 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; . C+ l, w. z' R //用方案m移动，同时检查结果 - G* w+ N4 l0 W6 P) r' ? if(move(top,m)&&check(top)) . L }/ |; L2 X, I+ p6 B2 c) p { if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf ) ) [9 {- `4 f! A4 V# [8 L { //打印渡河步骤 display(top); $ \. o! j9 ]8 S9 \2 K% o5 s //统计方案个数 . S+ r2 G/ D. K; ~+ i5 P count++; # }) [7 o- v; F# |6 ?; n- j fprintf(fp,"count=%d----------------------------\n\n",count); 3 I* t x6 w: f R if(count>1000) exit(1); / q9 q: n" z1 W! b% R) m } else $ @- t6 Y6 G5 S9 Q: R0 L" ] f1(top+1); ( t+ w8 a7 h' O+ {: z } }//for 7 M) Z: W- i5 o* d. k6 |$ V0 c& I }//if(top>=0) }//f1

/ H" I& a# H1 M2 T9 J

3 D' ^- N. m! G" ~0 S+ P r2 `

void f2() ' v$ F2 J8 ~# j/ Z! D/ J{ 2 b* d# E* k* P. ~8 K int top=0,i; //开始时都在起始岸 s[top].man=s[top].sheep=s[top].wolf=s[top].cabbage=0; //未开始渡河 * g9 A3 m) R% V6 m6 ~ s[top].m=4; 3 z9 D$ v4 M6 T( E while(top>=0) { 7 a5 r( J) x7 V1 n. w$ B if(check(top)) { if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf ) { " h8 l" s9 v$ |: V! h7 r/ w //打印渡河步骤 display(top); % H6 X" j% O6 N9 ]- i. } //统计方案个数 8 V' w( Y [& `/ T* ` count++; fprintf(fp,"count=%d----------------------------\n\n",count); if(count>1000) exit(1); 7 w' U% y2 n! ` //回溯 while(top>=0&&s[top].m>=4) top--; & H$ N! d/ d2 S/ w6 N if(top>=0) { 8 E) e. H/ o6 w0 }8 c5 y# p" b //在上次状态基础上准备做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; : V* v" n+ I, i i=1; : s2 z1 T7 @9 M) U2 T& k0 j while(s[top].m+i<5&&!move(top,s[top].m+i)) i++; " O! n) _% C8 c8 n0 I# K! i5 b: x }

} else { " }1 ~3 ^4 W3 J7 N top++; 9 N; U& Q- y4 F //在上次状态基础上准备做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; i=1; while(i<5&&!move(top,i)) / T8 n1 Z5 f* {* M) a, l$ q i++; }

} else { 5 G4 R2 ]: e: J& q' J& e0 H //回溯 while(top>=0&&s[top].m>=4) ! F" j1 m6 L7 o5 m- Q- U; r2 d top--; if(top>=0) { //在上次状态基础上准备做move 7 n3 b0 u. F% n8 X1 i- ] s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; 3 q8 s8 B* a5 L2 b9 ?9 f8 A s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf; i=1; " x/ t6 w* m6 W+ m: E. q while(!move(top,s[top].m+i)) i++; } } }//while . p; M$ K% ^! l4 h}//f2 //---------------------------------

sally

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

huashi3483

呵呵，好搭档

lynn324

是用c编的吗?

mnpfc

呵呵，看过了