渡河问题

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?

程序代码：

+ h5 G. V: X* c% y# H9 n

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

8 f* [! w1 z( q

#include <stdio.h> #include <stdlib.h> 1 @6 [" V+ @% q# L4 d R7 |#define MAX 50 ! o f. G4 V6 B) c* Q" w9 }struct state / }4 C4 m; W6 t# u1 d* w' U. N) S{ ' p# q* l9 J% S+ I1 o8 j/ l" v int man,sheep,wolf,cabbage;//0:在起始岸；1：在目的岸 int m;//所采取的过河方法，(1--4) }s[MAX]; int count=0; FILE *fp=fopen("c:\\2.txt","w+");

9 P+ p0 I( p% s' A

void main() # h$ R9 J3 p1 v' F1 F{ & e' [" m$ K% V( [, C$ ^ void f1(int ),f2();//f1试探递归 % D. G8 L {6 z! V s[0].man=s[0].sheep=s[0].wolf=s[0].cabbage=0; 0 v+ z$ D. L5 y% J" s+ C/ ^' S s[0].m=4; : P/ t% d- J* w# g1 h s[1].man=s[1].sheep=s[1].wolf=s[1].cabbage=0; f1(1); //f2(); 4 u; Q% W* {! a* W fclose(fp); , m# D! X: K- i( q) q/ K" J- R printf("\n");

' h& h" J+ t1 O2 \( Z" V

} //用m值决定的方法渡河，成功返回1,否则返回0 * A' \- }1 Z( h0 A2 I) Xint move(int top,int m) { switch(m) { //人带羊过河 $ J$ ^" j* A* P# H+ R% H case 1: //判断人羊是否在同岸 if(s[top].man!=s[top].sheep) return 0; + m1 D# @3 P( E1 y) F s[top].sheep=s[top].man=(s[top].man==1)?0:1; 2 G/ ?- [8 z9 D4 F( v( M+ U1 W% d s[top].m=m;//存储过河方法 break; case 2: if(s[top].man!=s[top].wolf) # k* E6 J3 J0 z- t1 @6 B0 _ return 0; s[top].wolf=s[top].man=(s[top].man==1)?0:1; 5 p/ \( B1 v9 f( R9 J s[top].m=m;//存储过河方法 ! M7 h, }$ e" s break; ( T/ {7 r0 B, b) A; e* K case 3: if(s[top].man!=s[top].cabbage) return 0; - h& k1 v3 u z1 c) V" G s[top].cabbage=s[top].man=(s[top].man==1)?0:1; N1 z1 Y$ F5 ~& ? s[top].m=m;//存储过河方法 $ k' @2 \* [( r# x break; //人单独过河 / H: N& V/ ~/ R# `) O case 4: s[top].man=(s[top].man==1)?0:1; 0 R9 `; \# j! Q! F) a s[top].m=m;//存储过河方法 break; ) v" N) r' Z+ z. Q) z) F }//switch return 1; }//move / k: x3 ]8 M8 o9 N8 u//打印过河步骤 " v) i) {1 P) A P: G) b' Ovoid display(int top) + y. u" r# u8 n P{ int i=0; 4 [$ X: g. W# g% N fprintf(fp,"state%d: man: %d, sheep: %d,wolf: %d,cabbage: %d\n",i,s.man,s.sheep,s.wolf,s.cabbage); 2 p% T4 q' Y. b for(i=1;i<=top;i++) { switch(s.m) X6 a6 \2 i2 ?/ s6 [4 G6 ?; m' c; F { 6 J+ a( p7 {: j- G! o: o case 1: if(s.man==1&&s[i-1].man==0) fprintf(fp,"人带羊从起始岸过河到目的岸\n"); : J. Q% } A8 A3 D, {! G% C else fprintf(fp,"人带羊从目的岸过河到起始岸\n"); break; " ?: D. ~8 Z6 f2 h. U+ f8 q1 V* y$ _ case 2: % l2 [9 U. \, p. L7 v if(s.man==1&&s[i-1].man==0) fprintf(fp,"人带狼从起始岸过河到目的岸\n"); else / _7 J5 T: m* c5 o; P) V9 l fprintf(fp,"人带狼从目的岸过河到起始岸\n"); break; ; J+ K3 P0 [0 ^3 d& ~! G2 N case 3: ; X! Z1 \' k) v: X d) r( Y- P$ s if(s.man==1&&s[i-1].man==0) " F& @. L9 X# {$ s fprintf(fp,"人带菜从起始岸过河到目的岸\n"); else - A* ~* X3 q+ D fprintf(fp,"人带菜从目的岸过河到起始岸\n"); break; case 4: + U0 g! u1 B n& X( e if(s.man==1&&s[i-1].man==0) 8 ^- f$ x% I" X9 b# `/ D. ~% [ fprintf(fp,"人单独从起始岸过河到目的岸\n"); else 9 I* D' ~8 C' F M. H; J; @! u fprintf(fp,"人单独从目的岸过河到起始岸\n"); break; }//switch + f# c" L$ k* N% e+ v1 d 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"); }//display

//检查两岸合法性已经有无状态与历史重复性 ; g+ J7 s! z" a3 k- o! y' v3 S; rint check(int top) { ( B0 r* u( `+ G* T+ I; y* E int i; + R+ e4 {1 {5 U; w& P! q* b//检查两岸合法性 0 ]( c+ V1 W7 ]& }3 E0 {$ }! w if((s[top].sheep!=s[top].man&&s[top].cabbage!=s[top].man)|| (s[top].wolf!=s[top].man&&s[top].sheep!=s[top].man)) return 0; 0 ?; v' j1 d* C' g7 v% Z //检查历史重复性 - I2 ^/ m( j x" s) M5 h7 ` 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) return 0; 3 J; w3 d( W c q //ok 6 M8 n/ W" z5 v! Q7 H% u return 1; } void f1(int top) { # A- X; I9 k* c# w int m; if(top>0)//0状态(初试状态应该是预先设置好的，所以要做状态1，故，初试top进来应该是1 { //对每次状态分别试探4中方案 0 u* h1 x9 C* k: f2 P for(m=1;m<5;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; //用方案m移动，同时检查结果 2 {9 [ W; ]0 l4 E3 X$ J if(move(top,m)&&check(top)) { * x& \+ S, x1 x. w7 k if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf ) - p& ^/ R# _1 s* V+ ^7 h { 9 v! k* I* N4 V+ G //打印渡河步骤 ' X3 J) k l9 |/ r6 W+ p5 M% `3 O5 q' ~" W display(top); //统计方案个数 count++; 5 O/ U$ z* B' B6 u4 } fprintf(fp,"count=%d----------------------------\n\n",count); n; Z( }- N9 j1 I5 J, L if(count>1000) exit(1); 4 y6 |; u: t* L4 u# q% k: g; c } else ( H3 F/ [# a" f9 p f1(top+1); 5 i& P4 q- i. z+ P, R } }//for }//if(top>=0) }//f1

5 J \' p l7 ~8 j* p3 f

6 y6 {6 {6 s/ H' v+ O/ F

void f2() 6 I. y |# O* d% s# I6 O/ P{ 0 A. M5 U @' u int top=0,i; ) G( z% V/ i J( M. X //开始时都在起始岸 5 h. N. l# y* m7 U7 {0 T s[top].man=s[top].sheep=s[top].wolf=s[top].cabbage=0; 6 S2 T6 D8 j r0 t% u //未开始渡河 s[top].m=4; 9 c7 ?1 M% R7 g) _ while(top>=0) { if(check(top)) " \6 S2 B) G6 @; X& S+ d8 @) B) M- A { if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf ) * C- P W( L& ?0 Z, ~" j { //打印渡河步骤 display(top); : p. c$ A& L$ [( }1 P7 ^ //统计方案个数 1 K4 N6 k" L' C( ~* b; ~; I, n4 ? count++; : `2 H& x5 X; }. E: t fprintf(fp,"count=%d----------------------------\n\n",count); if(count>1000) exit(1); //回溯 while(top>=0&&s[top].m>=4) top--; if(top>=0) : H' y! d6 ~$ f# M { //在上次状态基础上准备做move 6 s1 y; l( g) D2 X* G+ r! F6 K 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; 0 F* f8 ?& ~: Q+ ?7 f0 A$ m* l i=1; : c% k9 O6 s* q1 {/ k while(s[top].m+i<5&&!move(top,s[top].m+i)) . a3 ~' w- }* n5 w6 v: W7 E i++; }

} else 7 k! p: F) S$ l5 G { top++; //在上次状态基础上准备做move 7 p* U$ N* R/ [5 z s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; 7 p5 Q( c9 k( h: O* I) @ I! i s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf; + T+ F- R8 R* s0 d$ a; u i=1; while(i<5&&!move(top,i)) i++; }

} . d" s4 A( ?4 p/ h else { //回溯 7 ]2 i0 g A0 f4 d while(top>=0&&s[top].m>=4) top--; 7 _2 I- q7 _+ ^. u1 Z if(top>=0) { //在上次状态基础上准备做move ) B2 }% N5 Q m s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; # x9 g5 v3 U& d# L3 s s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf; i=1; while(!move(top,s[top].m+i)) : D9 t! J. y$ T8 R i++; } } : z; ?; p- w t% Y# c }//while ' {+ c$ l# w3 y- ~" e1 N- j q}//f2 3 |+ Z/ n- H6 }8 k//---------------------------------

sally

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

huashi3483

呵呵，好搭档

lynn324

是用c编的吗?

mnpfc

呵呵，看过了