渡河问题

sally

渡河问题

* b0 g+ Z& A9 S5 w I+ ^5 U' i

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?

0 v+ n5 z/ \. O5 h# C: |6 H( n

程序代码：

$ {% R* }& M0 N

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

) ^3 L6 O: ~' G, H

#include <stdio.h> #include <stdlib.h> #define MAX 50 0 i# W# v5 u0 c, J2 \& U6 Astruct state , ~7 Y2 I2 B0 p$ A- z{ & y; U; p8 b2 ` int man,sheep,wolf,cabbage;//0:在起始岸；1：在目的岸 ; j5 g/ Y' U2 w2 W: Q' Z int m;//所采取的过河方法，(1--4) ' n9 T: N$ |* ?}s[MAX]; int count=0; s- c4 T" G3 z" G3 `6 t0 iFILE *fp=fopen("c:\\2.txt","w+");

) ]. M& W1 O" |% u9 \2 `% {

void main() Q f L% w+ L; h; l& C: q{ 0 e* i/ L2 O6 c) F$ y void f1(int ),f2();//f1试探递归 s[0].man=s[0].sheep=s[0].wolf=s[0].cabbage=0; , K, [# ~ v" h8 {$ l s[0].m=4; 9 H7 A0 V7 E5 g* J5 W s[1].man=s[1].sheep=s[1].wolf=s[1].cabbage=0; . i* ?: Z% k% ]0 k" C f1(1); 4 F# s% l: _7 I+ Y5 z/ J //f2(); fclose(fp); 0 V5 z# t+ r& Q8 S8 T% {& n printf("\n");

} //用m值决定的方法渡河，成功返回1,否则返回0 * s) p: k2 r% ]2 P3 W2 H3 c$ cint move(int top,int m) { - l8 K: q- Z% ]. a5 c0 V switch(m) { / J: b( D& F% e. b. }9 J0 o //人带羊过河 * R# s: w1 C: P7 s; i/ c2 @* B case 1: 4 I( v8 `! [. @+ e1 w% v6 v+ [ //判断人羊是否在同岸 if(s[top].man!=s[top].sheep) return 0; s[top].sheep=s[top].man=(s[top].man==1)?0:1; s[top].m=m;//存储过河方法 . k3 o; x# E9 e% |4 t, Q break; case 2: if(s[top].man!=s[top].wolf) - h4 S! w) z' R8 L2 _" X, H" m return 0; " E D% l0 }- E- m- f1 k. G5 ^4 G s[top].wolf=s[top].man=(s[top].man==1)?0:1; s[top].m=m;//存储过河方法 2 A- @% F) ? u' m break; case 3: ; h. ?9 P2 k! [& y if(s[top].man!=s[top].cabbage) return 0; s[top].cabbage=s[top].man=(s[top].man==1)?0:1; ; C: Q1 J6 y( c5 S( R# w+ u5 k s[top].m=m;//存储过河方法 % C- X* G! Y/ u( q break; * g9 m7 H( y( m2 Z9 W9 {1 W //人单独过河 8 v4 P. C' _' s case 4: 1 |+ v9 W9 j0 Z% d. F7 U s[top].man=(s[top].man==1)?0:1; s[top].m=m;//存储过河方法 break; " m+ G6 d0 B, I: x& N }//switch return 1; }//move ! _+ P: Z4 `7 D, E, D//打印过河步骤 5 H ]2 X/ M) `- J3 x: }* Kvoid display(int top) " |9 |$ G: n' V1 x{ % T; l3 x: t( F1 K int i=0; & q" Q) K( C, 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++) " S) q& E' A4 z& i, v9 h+ A) U { * l6 d/ A* J$ s switch(s.m) { case 1: if(s.man==1&&s[i-1].man==0) fprintf(fp,"人带羊从起始岸过河到目的岸\n"); else ; K: c" X/ Q$ p0 R- A fprintf(fp,"人带羊从目的岸过河到起始岸\n"); break; 7 @! A8 s) G* ~; D+ w9 l$ J. w. T; s+ W case 2: 5 s. l# H' N! e( h+ s/ s o. ^3 V: u if(s.man==1&&s[i-1].man==0) fprintf(fp,"人带狼从起始岸过河到目的岸\n"); 2 F0 x6 D% Y) @1 j. ^5 H; B, i6 w else fprintf(fp,"人带狼从目的岸过河到起始岸\n"); " M( s3 v9 |5 l# p5 Y% u6 n c break; case 3: if(s.man==1&&s[i-1].man==0) fprintf(fp,"人带菜从起始岸过河到目的岸\n"); & v, a9 u; z3 v6 u3 T else 7 x! w% P' Y$ F0 ]4 U" s fprintf(fp,"人带菜从目的岸过河到起始岸\n"); break; case 4: if(s.man==1&&s[i-1].man==0) " f1 N- e# @2 J. h2 A6 q! Y fprintf(fp,"人单独从起始岸过河到目的岸\n"); % {: o9 X& P& j3 K$ w" A M4 l else fprintf(fp,"人单独从目的岸过河到起始岸\n"); break; }//switch 0 k( V$ p( }: K% }7 A/ X fprintf(fp,"state%d: man: %d, sheep: %d,wolf: %d,cabbage: %d\n",i,s.man,s.sheep,s.wolf,s.cabbage); 5 f0 _: |8 l, A& z& @! T9 ]; f& X }//for . r& B: x3 I& {4 ^6 J7 M0 A9 |fprintf(fp,"All ferried successfully!\n"); N. y, i% `/ D3 n' J5 }}//display

//检查两岸合法性已经有无状态与历史重复性 int check(int top) { 2 P# }. W. i; N# k: p+ |+ J! I int i; //检查两岸合法性 if((s[top].sheep!=s[top].man&&s[top].cabbage!=s[top].man)|| ' U& ^6 q$ y3 W (s[top].wolf!=s[top].man&&s[top].sheep!=s[top].man)) return 0; //检查历史重复性 / j# t6 l7 v7 ?1 u5 W for(i=0;i<top;i++) : d, l0 y; Z) [- e2 M if(s.man==s[top].man&&s.sheep==s[top].sheep&&s.cabbage==s[top].cabbage&&s.wolf==s[top].wolf) : h1 q6 Q6 H- t return 0; ! S& p" u7 v8 U- D //ok return 1; 6 a; C9 F# g3 [/ u y: \" c+ u3 I} O- P% w5 x& n1 Xvoid f1(int top) ' S/ ?5 Q. Z* D3 A+ j2 b{ 2 ~, W- ?: |4 v int m; 0 ^) b# u5 V6 m, j: Z: K0 ? if(top>0)//0状态(初试状态应该是预先设置好的，所以要做状态1，故，初试top进来应该是1 { //对每次状态分别试探4中方案 for(m=1;m<5;m++) { //每次方案的实施是在上次结果状态上做的 s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; 9 ?8 Z) H9 h+ x' c- l/ x s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf; y, w8 V* H( Z$ y //用方案m移动，同时检查结果 , u' | n6 k1 d" M- O, g) A* @ if(move(top,m)&&check(top)) { if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf ) { //打印渡河步骤 display(top); //统计方案个数 count++; fprintf(fp,"count=%d----------------------------\n\n",count); ' T: i) M; X. w" l" b, x if(count>1000) exit(1); 2 J7 M" H% E4 L+ ]0 S } 8 _) e9 x* h+ @) f& U5 A+ {+ Y else 6 e* A' w8 c. {+ ^ f1(top+1); } }//for , z! y7 z n: u7 Q3 v5 w9 ^ }//if(top>=0) 8 q+ n P6 q6 k6 ^1 H% U5 A}//f1

' R4 H! X+ B. g

4 l7 E- Y+ U6 T9 U$ c

+ d1 E' s: A, @, x

& u0 n1 X. s$ q% Y+ Ovoid f2() . x7 N' O E9 x* i2 ?# b- e- ^{ int top=0,i; 2 F$ u, W2 P9 r7 F //开始时都在起始岸 s[top].man=s[top].sheep=s[top].wolf=s[top].cabbage=0; 5 h' `/ Y$ f( Z //未开始渡河 s[top].m=4; 2 E- w8 `" T5 K2 i* k while(top>=0) { # R. {5 Z3 o( |0 X* L4 \ if(check(top)) ' P5 ?0 P$ u: d: U8 v$ E3 i { if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf ) 2 w+ q: c8 |+ |; [- s { //打印渡河步骤 * ^6 [( e" m @5 w display(top); //统计方案个数 count++; fprintf(fp,"count=%d----------------------------\n\n",count); if(count>1000) exit(1); //回溯 while(top>=0&&s[top].m>=4) " w5 v; Q+ e4 a* ~# F! J" V top--; if(top>=0) ( x0 ~3 U0 c3 j! 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; 2 r, v' b: l% C3 t; s9 Y& q' f i=1; 2 E1 x$ ]3 W3 A r' Z while(s[top].m+i<5&&!move(top,s[top].m+i)) 9 D# Z {5 m. _) W0 @) c i++; }

} ' J2 a8 h" E2 {1 h9 A else 9 Y! S# T7 J( N. t9 b { # M# t+ l" ^8 k$ @% M& m% J top++; " v6 U# h/ q$ A, G( u0 S //在上次状态基础上准备做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; 4 M# n3 ]3 K. U& J while(i<5&&!move(top,i)) ' }6 ^ b' ?/ s" R+ A2 w9 p+ g i++; 8 Q2 Y# G9 q" }7 U }

! t7 w1 `; f. j8 s

} 6 @) }7 H" _7 o8 C9 O+ A, R else 2 a6 J u' [/ G* o- {4 { { : v6 \$ P+ Z1 a1 w0 | //回溯 while(top>=0&&s[top].m>=4) top--; if(top>=0) 1 q' Z; `2 U9 i! K6 { s { //在上次状态基础上准备做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(!move(top,s[top].m+i)) i++; , d/ ^; R$ K. l+ u' Y& T( D: N } } $ u q$ C K: J7 |2 j/ a }//while }//f2 , O/ E4 K/ C- M//---------------------------------

sally

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

huashi3483

呵呵，好搭档

lynn324

是用c编的吗?

mnpfc

呵呵，看过了