渡河问题

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?

- s$ s- {" Z1 H/ C8 M7 j

程序代码：

/ M. _ {1 u/ ]: E2 h

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

#include <stdio.h> #include <stdlib.h> 0 D, e% k7 x, o5 w#define MAX 50 @9 ?1 P( r" F7 p+ Fstruct state 3 h6 S' t" D. O& B0 k) U$ a{ int man,sheep,wolf,cabbage;//0:在起始岸；1：在目的岸 int m;//所采取的过河方法，(1--4) }s[MAX]; int count=0; FILE *fp=fopen("c:\\2.txt","w+");

void main() & L; ]! a0 N; A7 J' H0 w4 Z6 }$ t{ ( V, v) { D/ @ 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; + j4 l' }2 m2 x* Z, @ f1(1); + J( W D7 m' j) b1 E7 q //f2(); ( A) [" D/ i; {1 k! s1 [5 J fclose(fp); printf("\n");

% M9 d% H( H" M3 @, {2 s6 M

} 8 S8 Y" l { H8 V//用m值决定的方法渡河，成功返回1,否则返回0 int move(int top,int m) 7 z- r( q4 U+ x3 D& [. y{ switch(m) 6 a, B! k2 q2 ~ z- U$ |* J { / @! r4 h* w- ?# _# O! R //人带羊过河 case 1: //判断人羊是否在同岸 # L4 t! Q/ |. C2 V3 r if(s[top].man!=s[top].sheep) & x: J- E0 y0 q' W3 w3 { return 0; , q. Q+ I1 k7 w5 v; P s[top].sheep=s[top].man=(s[top].man==1)?0:1; s[top].m=m;//存储过河方法 9 W1 _$ w0 T. Z' }: G7 S2 Z5 l break; % c, x4 ]3 D: x1 c: J6 X case 2: if(s[top].man!=s[top].wolf) # F( B2 J' ^6 p* | return 0; s[top].wolf=s[top].man=(s[top].man==1)?0:1; s[top].m=m;//存储过河方法 + ]6 F B# H) |& o; x break; 2 L% R, L# ~4 L- f# c case 3: , Z! s" j2 X' i/ { if(s[top].man!=s[top].cabbage) return 0; s[top].cabbage=s[top].man=(s[top].man==1)?0:1; ( _5 c7 l7 j* T; r8 P, {# @& e, b s[top].m=m;//存储过河方法 break; //人单独过河 : w! B% q' | l6 V# `) \# z7 Z# v case 4: 5 m5 K" z; ]2 d& g- b$ x s[top].man=(s[top].man==1)?0:1; s[top].m=m;//存储过河方法 break; ) q6 E5 S2 T- F- Y2 L$ w: [ }//switch , O" A3 s; |7 R6 a" k return 1; }//move //打印过河步骤 + l- R. D: ^% I8 U: d% hvoid display(int top) { 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); 3 K" m6 f; ?4 z7 ]& f for(i=1;i<=top;i++) { switch(s.m) { 0 a! | f6 U# Q+ E v case 1: 6 r. u- K" u" o! X# M. j) J. q if(s.man==1&&s[i-1].man==0) & m- E4 ^( A5 o fprintf(fp,"人带羊从起始岸过河到目的岸\n"); else fprintf(fp,"人带羊从目的岸过河到起始岸\n"); , p O: l* c5 m' U9 A% q break; * |$ ~# ^. i$ F) p case 2: if(s.man==1&&s[i-1].man==0) 1 X; }+ s* V9 E" a0 b3 w% S fprintf(fp,"人带狼从起始岸过河到目的岸\n"); else fprintf(fp,"人带狼从目的岸过河到起始岸\n"); % N2 x& N; x# _2 j6 d1 n( L4 o2 X8 K break; case 3: if(s.man==1&&s[i-1].man==0) fprintf(fp,"人带菜从起始岸过河到目的岸\n"); ! b& z3 J+ q% m. D else 6 V& ~: b' r6 Y7 K# n) [; W! B% R fprintf(fp,"人带菜从目的岸过河到起始岸\n"); break; case 4: : P4 Z! W% x) z8 L if(s.man==1&&s[i-1].man==0) fprintf(fp,"人单独从起始岸过河到目的岸\n"); else fprintf(fp,"人单独从目的岸过河到起始岸\n"); 2 t$ h5 l* e: }7 b# W break; }//switch % U3 ~- v% b7 g9 a6 K- w: x fprintf(fp,"state%d: man: %d, sheep: %d,wolf: %d,cabbage: %d\n",i,s.man,s.sheep,s.wolf,s.cabbage); 5 c8 a1 c4 T- f3 r% I B }//for $ Z0 N' d) b$ u3 q) Lfprintf(fp,"All ferried successfully!\n"); ; \: l( N! [5 Q. k}//display

//检查两岸合法性已经有无状态与历史重复性 int check(int top) { int i; 7 I3 _: B# T+ M5 ^//检查两岸合法性 4 v: |" f+ u. c# d( N if((s[top].sheep!=s[top].man&&s[top].cabbage!=s[top].man)|| - n8 S. j$ o; w; Q (s[top].wolf!=s[top].man&&s[top].sheep!=s[top].man)) " E4 e) z% }" J! x! ~ return 0; //检查历史重复性 & @* z q) ]' M3 L: u/ p$ q0 E for(i=0;i<top;i++) # q( Z t6 p9 ^9 y if(s.man==s[top].man&&s.sheep==s[top].sheep&&s.cabbage==s[top].cabbage&&s.wolf==s[top].wolf) return 0; //ok ( b; O- X+ b) ]2 {0 K return 1; } 3 R8 d0 T. a* R- U7 @void f1(int top) w( K% \/ c& T/ v0 \: O, Z{ 5 j: ?* e0 c3 H. ^ int m; if(top>0)//0状态(初试状态应该是预先设置好的，所以要做状态1，故，初试top进来应该是1 { //对每次状态分别试探4中方案 $ V2 Z$ Y( ]' A1 R; [- E for(m=1;m<5;m++) { $ Y, o9 i! e8 r1 s" v //每次方案的实施是在上次结果状态上做的 ; W# `+ l) v5 t; H& Y# x8 h 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; : l. U1 E* s# b ^6 w _( \5 K //用方案m移动，同时检查结果 if(move(top,m)&&check(top)) { + o$ V% I$ U' | a* T- f% E" H if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf ) { //打印渡河步骤 6 A) _* ]7 X$ Y# n display(top); ( Z8 Y9 Q, E6 g" @1 l# \9 V. H, I //统计方案个数 count++; ' B+ u% \( J7 C' j( Z fprintf(fp,"count=%d----------------------------\n\n",count); if(count>1000) exit(1); ) S* A2 W3 B; O/ g) w } else # l) }5 v9 J w$ V f1(top+1); } }//for - s2 }+ ~" `( Y6 Y( o) v. u }//if(top>=0) }//f1

* j0 [& h! Y/ Y3 ?$ ?

( e; i+ q$ A. h; Y2 D

' O* N, ?# Z9 V% x/ \9 svoid f2() 7 ?. N6 r5 k; T0 f, ~3 I6 y{ int top=0,i; //开始时都在起始岸 s[top].man=s[top].sheep=s[top].wolf=s[top].cabbage=0; //未开始渡河 s[top].m=4; . y( P# f7 I k* H; \ while(top>=0) 8 O; C) N" T" ?: l$ c8 E1 } { if(check(top)) { 1 o! R h% m; B: x if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf ) / T% i/ r. ^# I: g { ) P Z3 E: V% J& ]0 h: Q0 I/ ^2 [ h //打印渡河步骤 " e* e/ q9 T) j0 F0 | display(top); //统计方案个数 count++; fprintf(fp,"count=%d----------------------------\n\n",count); if(count>1000) exit(1); ' \( \' |: q; p+ |. S. \: o //回溯 3 f$ n8 r* }1 i0 J while(top>=0&&s[top].m>=4) 2 `6 [: m" l4 _' l3 c% } top--; if(top>=0) & e3 M, ?( q1 a0 A% O/ r2 n { 7 [' k" }- X9 b //在上次状态基础上准备做move 1 ^7 m1 `) x* i2 o% b2 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; % y: E( M/ A+ L( P7 [ i=1; 5 ]$ I. n& C/ \! s while(s[top].m+i<5&&!move(top,s[top].m+i)) i++; }

; j* g" \5 O4 |( ?8 Q2 J

} * S7 ^) s/ U4 Z5 |6 \9 E+ I else { top++; $ `2 n9 d% ^, Z0 E8 h+ ~7 P* Q //在上次状态基础上准备做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; 3 f2 o% `4 H: ?/ a i=1; while(i<5&&!move(top,i)) i++; }

} % v; M6 X! p7 _; p+ G8 L/ r: K V else * c0 S5 K) b& G, q { //回溯 ; y ?* [) R: x while(top>=0&&s[top].m>=4) ' L+ Q8 Y4 I K9 Q top--; if(top>=0) 5 c8 @; c6 T6 U1 f E { //在上次状态基础上准备做move * n* P* _( i5 w5 u 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; 3 [. }- J7 Y8 I. ~. N' ^3 U i=1; while(!move(top,s[top].m+i)) 9 D/ b: Y4 S n/ e7 P i++; } } ! I0 Y+ y5 Y4 ~/ V9 C. {2 v; ? }//while % ]; K! Q2 N# t( U8 c}//f2 //---------------------------------

sally

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

huashi3483

呵呵，好搭档

lynn324

是用c编的吗?

mnpfc

呵呵，看过了