渡河问题

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?

! ^7 @( m% x6 o" | W, u

程序代码：

0 l9 {2 n0 c" n, _7 f' ^% z4 ?' ?

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

/ Y4 s! i, L5 h$ y: j9 t( H

#include <stdio.h> 9 c% ?0 f+ K* \8 ?) S#include <stdlib.h> 4 F$ I: ]9 J7 y#define MAX 50 struct state { # ^; n4 [& |% K4 l# M int man,sheep,wolf,cabbage;//0:在起始岸；1：在目的岸 + ]3 U: t2 |( i* h/ p+ [4 e( b int m;//所采取的过河方法，(1--4) }s[MAX]; ; V5 i; g2 ~9 F# n9 r1 [1 Vint count=0; FILE *fp=fopen("c:\\2.txt","w+");

3 [3 `9 \5 T& F5 ~" E" n, G- Y- {! f

void main() 3 `- a3 J0 i7 X; _{ void f1(int ),f2();//f1试探递归 s[0].man=s[0].sheep=s[0].wolf=s[0].cabbage=0; # y& z* }2 w$ b/ w5 P# z s[0].m=4; s[1].man=s[1].sheep=s[1].wolf=s[1].cabbage=0; f1(1); //f2(); fclose(fp); printf("\n");

& [7 T$ w- ~% j! j; E+ ]

} //用m值决定的方法渡河，成功返回1,否则返回0 int move(int top,int m) { 3 k _; D9 v8 D, N# H- \ i y switch(m) " r! R6 r' k- t { //人带羊过河 case 1: , S, a1 M5 f1 F8 b //判断人羊是否在同岸 if(s[top].man!=s[top].sheep) 1 S1 h% A4 `9 `8 A( T/ n" } return 0; s[top].sheep=s[top].man=(s[top].man==1)?0:1; s[top].m=m;//存储过河方法 break; case 2: if(s[top].man!=s[top].wolf) ! c; e( Y% f" A9 t4 y: w return 0; ! f9 m) Y( b8 f$ k' [4 V s[top].wolf=s[top].man=(s[top].man==1)?0:1; s[top].m=m;//存储过河方法 2 j, v$ D/ r9 O7 {! n: d% | break; $ Z" H- |# g# j% R! Y: Q5 l case 3: if(s[top].man!=s[top].cabbage) 4 R0 W0 P# O& ` ]. ]* h return 0; s[top].cabbage=s[top].man=(s[top].man==1)?0:1; s[top].m=m;//存储过河方法 break; //人单独过河 . W: `. b. H* h/ m" a) D case 4: $ b5 k/ I3 I, [9 E! H) ?5 O s[top].man=(s[top].man==1)?0:1; s[top].m=m;//存储过河方法 - T9 ^, r$ `* I2 [4 d break; 3 c7 L% @0 @4 L. N$ B) o; t9 S }//switch " u* ]3 u# w3 L) X/ e return 1; 8 D/ Y4 d( L3 ^7 e}//move //打印过河步骤 void display(int top) { * s. O/ A* C0 s0 I 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); 6 @( X7 W: S1 c; z8 W" e2 }. Z for(i=1;i<=top;i++) 0 }8 }% ~$ @8 R, O' o. d ^ { ) N4 a; ^+ u0 k5 q switch(s.m) & ` K; G, F$ T" B. K3 Y { case 1: 4 q$ w1 B% x8 ^2 }+ A/ u, ~ if(s.man==1&&s[i-1].man==0) 9 v/ U2 u+ ?3 S- I1 p* r6 o5 [& x fprintf(fp,"人带羊从起始岸过河到目的岸\n"); V' f3 V. O' K else fprintf(fp,"人带羊从目的岸过河到起始岸\n"); / g: q, o( x. r4 J! \& @ break; ! y" g5 {9 u6 f/ P case 2: 3 B% M0 R$ Q9 ]7 k) ^3 e5 g if(s.man==1&&s[i-1].man==0) fprintf(fp,"人带狼从起始岸过河到目的岸\n"); else fprintf(fp,"人带狼从目的岸过河到起始岸\n"); break; ; q- Y& f a Z. j case 3: if(s.man==1&&s[i-1].man==0) fprintf(fp,"人带菜从起始岸过河到目的岸\n"); * Z7 L9 @; h% b2 j- q% o& | else . I2 y% P2 v2 Z2 t( Q; C$ g fprintf(fp,"人带菜从目的岸过河到起始岸\n"); break; case 4: $ P+ p. W' A: ?* n3 s if(s.man==1&&s[i-1].man==0) 7 n: x$ O$ U& ]. |- |! `1 b1 A) Y fprintf(fp,"人单独从起始岸过河到目的岸\n"); & ]$ P" U+ k! U, q3 u else R" a3 q. `3 e5 U+ [' M fprintf(fp,"人单独从目的岸过河到起始岸\n"); & G- C! ]6 P4 ^) Z2 ~) M$ _4 h; W% s break; }//switch 1 p' N) d" Y: D: N- p5 I fprintf(fp,"state%d: man: %d, sheep: %d,wolf: %d,cabbage: %d\n",i,s.man,s.sheep,s.wolf,s.cabbage); ) n0 N! o6 S- i' f+ x- O. i* i$ N+ J }//for fprintf(fp,"All ferried successfully!\n"); }//display

( t4 \3 Y/ F3 N6 g

//检查两岸合法性已经有无状态与历史重复性 int check(int top) 9 W1 e8 }2 f7 f. ^( a( w{ % k' l* h8 R; K' A int i; & n0 V& [5 s1 \//检查两岸合法性 ; T4 _5 p7 z4 o" R. F' M( g1 [ 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)) ! L" C2 O* Z, A; g x return 0; //检查历史重复性 9 J, q* ^$ W# ]5 G 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) * q! I# C! P: B) S( q4 o/ z return 0; //ok 6 s9 E% f3 q6 L+ p" C return 1; } % r1 L# w/ `; i: B. U2 p7 wvoid f1(int top) / }* g/ w: [6 p6 r/ ^{ int m; 2 g( e* u+ o4 h, l2 H5 v0 g if(top>0)//0状态(初试状态应该是预先设置好的，所以要做状态1，故，初试top进来应该是1 { //对每次状态分别试探4中方案 for(m=1;m<5;m++) 0 b0 L5 [8 a Z6 N9 \$ F+ g { % e1 b7 `! h: k* j) z o/ a //每次方案的实施是在上次结果状态上做的 ' z4 K: d f+ D2 p s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; 1 {3 D- Y5 E6 ?& s8 l7 j9 x s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf; ) g' {6 q% l3 S" o/ t! ?. a //用方案m移动，同时检查结果 if(move(top,m)&&check(top)) { if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf ) { . ?$ N% L! j) ?1 z+ q! y# A/ @, B //打印渡河步骤 - m- T$ d5 u- a1 J display(top); //统计方案个数 count++; / A( K' k+ ]. |! W% J fprintf(fp,"count=%d----------------------------\n\n",count); # c1 y# }# J" z% {9 r- T" F) \ if(count>1000) exit(1); } else f1(top+1); } - o+ N- @9 U, D/ c+ B' [ }//for & J7 W* C" f$ I1 f# i$ ^+ x }//if(top>=0) ' v" O6 ?3 N1 r& }# ^$ u}//f1

+ g* Q$ N! @% S# ?( \6 v

void f2() 2 v+ n) U9 @% y& P{ int top=0,i; 2 f6 i8 O5 \* l" j0 c; p8 V //开始时都在起始岸 s[top].man=s[top].sheep=s[top].wolf=s[top].cabbage=0; //未开始渡河 & B e; q1 t0 E& O5 [, l6 t s[top].m=4; while(top>=0) { if(check(top)) { if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf ) { * j6 B' {4 Y5 L. } //打印渡河步骤 display(top); //统计方案个数 8 g' n9 N% A+ } count++; fprintf(fp,"count=%d----------------------------\n\n",count); / m+ g8 y- ~- ~8 Y/ Y# ~3 m+ ?% E H; Z if(count>1000) exit(1); //回溯 f9 R% @ R+ N while(top>=0&&s[top].m>=4) top--; if(top>=0) { $ c* w. Q, E( }- T //在上次状态基础上准备做move s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; ! n0 o" k- k$ ^ s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf; i=1; ' G4 l' [# a# k! T while(s[top].m+i<5&&!move(top,s[top].m+i)) i++; }

0 A' S2 M9 |6 J, d) l

} & O- l: H4 B) @ else : @7 f2 O( k8 D$ g { top++; //在上次状态基础上准备做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; 5 i V2 w, E$ H/ z while(i<5&&!move(top,i)) - K" ]1 Y7 ^8 t9 @: m0 ^ i++; }

) G% z) Y* s1 F& z) _5 ?% v: j

} ) @/ S( {8 x, j# i" U9 r% U else 5 }8 D1 ^0 I) x- L& j { //回溯 while(top>=0&&s[top].m>=4) / O4 ?2 t8 A/ Z% z2 I top--; C, Z" R5 j! I9 {7 u: g if(top>=0) $ g8 A$ |1 z! A3 r+ l9 y% b { 4 Y: I1 X/ A! t: _5 D: X1 g2 c9 X //在上次状态基础上准备做move 2 X2 f* H8 D8 o. j; s! k/ \ s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; 8 j. g9 j# M8 \' n5 } d s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf; " y& q) ^1 [+ {! C- K. F i=1; ' O- [" C' N# E0 ~& e, `; y' | while(!move(top,s[top].m+i)) i++; ) \4 R4 U! {& u8 H7 P! g } 7 C, d: c" A4 L$ i# t# I3 {1 m } / K) v r8 l1 d6 n j: t5 w, `, n }//while 7 \! `) a8 J. S% e' L4 j2 n}//f2 / o" G3 z G% {. x' i- [//---------------------------------

sally

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

huashi3483

呵呵，好搭档

lynn324

是用c编的吗?

mnpfc

呵呵，看过了