渡河问题

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?

; Q" K4 U$ f' o8 y

程序代码：

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

#include <stdio.h> #include <stdlib.h> & e1 c, @# T$ a- F/ Y$ y#define MAX 50 2 ^$ F+ G, a9 f2 T* {struct state { int man,sheep,wolf,cabbage;//0:在起始岸；1：在目的岸 int m;//所采取的过河方法，(1--4) 1 a: z/ l3 _/ u5 R% l}s[MAX]; 6 r+ y# `2 s5 L! l& [int count=0; 2 g; s- a p6 EFILE *fp=fopen("c:\\2.txt","w+");

void main() { void f1(int ),f2();//f1试探递归 ' T9 N; |& j& E- o$ t s[0].man=s[0].sheep=s[0].wolf=s[0].cabbage=0; 1 D% i& m) s9 x2 h% T8 Q s[0].m=4; 6 y$ B! B% T7 f: e s[1].man=s[1].sheep=s[1].wolf=s[1].cabbage=0; f1(1); //f2(); ) e" G5 I& x' x" [ fclose(fp); printf("\n");

} % y- Y( s- @! E' e//用m值决定的方法渡河，成功返回1,否则返回0 int move(int top,int m) { switch(m) 5 l$ A7 e' b5 I4 i { //人带羊过河 case 1: //判断人羊是否在同岸 if(s[top].man!=s[top].sheep) return 0; s[top].sheep=s[top].man=(s[top].man==1)?0:1; 7 G5 D) r1 T+ `! L1 E s[top].m=m;//存储过河方法 + F$ f* L- t& z* n4 d P8 m6 T break; 8 t/ Y& A7 z) F* o case 2: if(s[top].man!=s[top].wolf) - r/ x( M' a, A return 0; 7 ]4 U8 {6 V6 y8 n2 s s[top].wolf=s[top].man=(s[top].man==1)?0:1; s[top].m=m;//存储过河方法 : | A. e- _6 y) p break; # L. [& `+ t5 c8 [& U- _0 Y case 3: & h! U. \& |& Q* @* W, z2 T0 { if(s[top].man!=s[top].cabbage) return 0; s[top].cabbage=s[top].man=(s[top].man==1)?0:1; / g; `: `( z( Z5 r' g s[top].m=m;//存储过河方法 break; # `0 |$ V# U- E% n! k //人单独过河 6 G, Y& N, Q* P/ Z& ]# U2 C" r case 4: s[top].man=(s[top].man==1)?0:1; L4 O/ Y" k$ [* W9 B9 D; p s[top].m=m;//存储过河方法 break; }//switch return 1; }//move ! |4 | Z3 F3 K$ s% ^- l7 A' F//打印过河步骤 ' a1 }! ?' p5 l( s" l! ]void display(int top) { 4 o* C8 K- m U8 Q3 i int i=0; ! }5 |( P( I" p5 t7 K! ~ fprintf(fp,"state%d: man: %d, sheep: %d,wolf: %d,cabbage: %d\n",i,s.man,s.sheep,s.wolf,s.cabbage); 1 \' s8 Q" y! ]) Z" S* ]( Z* F for(i=1;i<=top;i++) 2 m/ T3 }1 B. V* N5 }5 m) P { : S# j/ c. g) M) J switch(s.m) @* W0 E! Y/ z4 Z! J) F7 J/ j { ! Q; }( W5 P8 p, @' d case 1: if(s.man==1&&s[i-1].man==0) fprintf(fp,"人带羊从起始岸过河到目的岸\n"); ! s4 `5 O) A! D" i% a else - j ]1 r8 _. _! ] fprintf(fp,"人带羊从目的岸过河到起始岸\n"); break; " {1 P: `: l$ x* f case 2: if(s.man==1&&s[i-1].man==0) fprintf(fp,"人带狼从起始岸过河到目的岸\n"); ( h& B0 _, |8 m; ~" x8 o5 Z( j2 w else 5 Q t( y6 S& o5 f s fprintf(fp,"人带狼从目的岸过河到起始岸\n"); ! G/ [$ @0 `1 S0 v; U5 A! y break; , q4 Y, d! y' v$ }8 n Z, _' r case 3: if(s.man==1&&s[i-1].man==0) # e( G: ?: _4 s* T fprintf(fp,"人带菜从起始岸过河到目的岸\n"); ! G9 `1 A- A4 |: k5 R+ b, z else fprintf(fp,"人带菜从目的岸过河到起始岸\n"); ! z L) ^# X. V. ?7 } break; case 4: if(s.man==1&&s[i-1].man==0) 5 j) a U0 Q3 A" f fprintf(fp,"人单独从起始岸过河到目的岸\n"); else fprintf(fp,"人单独从目的岸过河到起始岸\n"); - c ^! x$ V7 c) v/ s/ W( c% l- h% T5 { break; y# q; f% a. s; l" u" }* n }//switch fprintf(fp,"state%d: man: %d, sheep: %d,wolf: %d,cabbage: %d\n",i,s.man,s.sheep,s.wolf,s.cabbage); . a8 F& W9 m$ p# }# i/ m+ o }//for 3 I0 |& n2 c& O, Jfprintf(fp,"All ferried successfully!\n"); }//display

8 E3 L; g$ S4 m% |/ |- s

//检查两岸合法性已经有无状态与历史重复性 $ ^( @ {4 K% M; P. n' yint check(int top) { int i; //检查两岸合法性 if((s[top].sheep!=s[top].man&&s[top].cabbage!=s[top].man)|| - A+ h# q1 `8 ? (s[top].wolf!=s[top].man&&s[top].sheep!=s[top].man)) return 0; 7 V# I) d" w, `8 w/ e& m //检查历史重复性 Y3 R4 d% i L5 N6 f0 | 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; //ok " c$ v% d! N/ _4 z y, X9 Y return 1; , W9 _$ l- S1 `, f# x, M1 O} void f1(int top) { int m; $ i% }# g* f2 \9 P if(top>0)//0状态(初试状态应该是预先设置好的，所以要做状态1，故，初试top进来应该是1 % F& c [% N: \- ]" M { //对每次状态分别试探4中方案 : O8 B; e3 b- C6 H8 G K; d4 I for(m=1;m<5;m++) { . M7 M. ]2 B4 r9 \0 B% J8 o //每次方案的实施是在上次结果状态上做的 9 u5 Q$ F3 f/ @ s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; : ~: g4 G* ]* F9 q% \3 Y s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf; //用方案m移动，同时检查结果 6 V7 x) ^/ k1 L% ]0 S* n, _ if(move(top,m)&&check(top)) 7 l; h& W: K4 N4 ?( ^+ b9 w. z { , b4 x. A( E7 k+ }# Y if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf ) { //打印渡河步骤 display(top); ( ~% U4 r8 y5 R5 Q( p7 v+ N2 ^ //统计方案个数 ' X( n+ E/ N' ~, `3 d8 l count++; fprintf(fp,"count=%d----------------------------\n\n",count); % L) }, L( {5 @# @" k if(count>1000) exit(1); } else 2 k; N; ~- C! V9 v5 g f1(top+1); } 8 {. ?+ g7 f& q9 O# C }//for }//if(top>=0) }//f1

$ x9 C( g% p9 l( k7 c% ~

void f2() 4 u) `( r$ J9 A- o, t4 x{ 6 s: S* }5 c2 x6 \* c6 u$ C8 _ int top=0,i; 7 J9 L8 ~9 N# S1 v/ x9 ~# W$ G //开始时都在起始岸 s[top].man=s[top].sheep=s[top].wolf=s[top].cabbage=0; //未开始渡河 % W$ I- z2 L* z$ P s[top].m=4; ) }1 ]: }$ ]* ^8 J( { while(top>=0) { if(check(top)) 9 d* y% T: P1 z# P Y { 0 }3 `$ e% ?) u/ ]% J7 p: x' Z if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf ) { ( N% ^- O& ]2 K+ _ //打印渡河步骤 w9 ^. u& B1 O6 b display(top); 8 ^- m: p% P, C9 v6 _ //统计方案个数 0 o- k1 {& _) w1 K& q% ?) t count++; : D9 w3 b5 }4 }' R* ~ fprintf(fp,"count=%d----------------------------\n\n",count); $ _6 ` G8 k7 ^2 @0 |' |1 g7 R if(count>1000) exit(1); //回溯 * }, T) m2 H( [ while(top>=0&&s[top].m>=4) top--; 5 n! L: _9 i5 q2 J if(top>=0) { 6 \( G% s- I/ }3 } //在上次状态基础上准备做move 5 w1 \) J9 n+ H( {) M. P 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; . r2 i& q4 d/ ^ i=1; while(s[top].m+i<5&&!move(top,s[top].m+i)) i++; }

} else & T. B+ q' `& [) d4 d; F { 5 R" ^' M+ F/ K# n+ G$ o6 P4 J: q top++; ! E% s, B) w% C! K/ k3 G- g //在上次状态基础上准备做move ! e8 Z, M9 \+ ?3 ?! i/ B( T. B# x 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; , F# x: l( u, c; ]* M' u4 h while(i<5&&!move(top,i)) i++; & B6 J5 k8 u0 w$ f9 h }

} . f( F; Q& j9 R" Q else . `/ R5 ~# A5 L# \0 z { //回溯 while(top>=0&&s[top].m>=4) top--; if(top>=0) { ' @: b( g# Y. r$ Y/ b //在上次状态基础上准备做move 7 G: ^, n' L/ {* [( s 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; / `5 L. y$ ^! M5 _( v! z0 b while(!move(top,s[top].m+i)) i++; 1 L* R, `5 l7 S) N1 D } } ; u! ^& M& ?1 |, S* Z0 X }//while }//f2 3 X3 o/ [% ]9 A: q//---------------------------------

mnpfc

呵呵，看过了

lynn324

是用c编的吗?

huashi3483

呵呵，好搭档

sally

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