渡河问题

sally

渡河问题

4 P. |* l9 |- a A/ U* Z0 y- S

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?

& ~. G& L6 U) o4 F( b

程序代码：

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

" @8 A2 _( l! T3 U$ m

#include <stdio.h> % `# y7 K& Z& V9 X. o#include <stdlib.h> ) J' i5 h9 r. R- M7 N#define MAX 50 struct state { int man,sheep,wolf,cabbage;//0:在起始岸；1：在目的岸 X5 ~ O a/ R int m;//所采取的过河方法，(1--4) }s[MAX]; 5 T3 K; U0 F9 I; ~int count=0; FILE *fp=fopen("c:\\2.txt","w+");

void main() 8 x0 T; f- J/ [5 g- j( Y7 p1 n{ void f1(int ),f2();//f1试探递归 0 v5 g+ \' M0 k. Z s[0].man=s[0].sheep=s[0].wolf=s[0].cabbage=0; C7 j+ d, }" ~: ~0 S; k. r s[0].m=4; / g& v8 _ c) Q& Q; H; S& V- Y- x s[1].man=s[1].sheep=s[1].wolf=s[1].cabbage=0; 7 j$ k4 p) \% h% G( B% r! _) w9 e! {; v f1(1); 5 I/ F8 r" N# T: M //f2(); 6 a8 S% t! Z8 {/ ] fclose(fp); printf("\n");

} 5 p: z& G* @1 t//用m值决定的方法渡河，成功返回1,否则返回0 ; y% y$ S/ L8 T: \int move(int top,int m) ! o ]) ^# \. V" f6 Y% }; ?{ ; B5 L0 ^0 v" `& |- ^ switch(m) 8 T3 ^0 P; _. }* ?3 K" m) v { //人带羊过河 case 1: //判断人羊是否在同岸 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;//存储过河方法 7 N, J* V* t- q3 [& P! I break; case 2: - K. G8 v) n8 ~/ I; ]* l if(s[top].man!=s[top].wolf) return 0; 7 S4 U6 x9 i( c; F, t5 h9 q9 K7 a# R s[top].wolf=s[top].man=(s[top].man==1)?0:1; ( l3 D* J. v* T& J+ t6 i s[top].m=m;//存储过河方法 # D: L: m. c3 I break; case 3: if(s[top].man!=s[top].cabbage) return 0; 6 H% J( `$ W, O: q8 l s[top].cabbage=s[top].man=(s[top].man==1)?0:1; s[top].m=m;//存储过河方法 break; % ^, r$ X0 N& s# R; E' E //人单独过河 case 4: . [6 b# G4 E) g3 p$ B4 G7 B f s[top].man=(s[top].man==1)?0:1; 6 M- x9 e" y! b s[top].m=m;//存储过河方法 break; }//switch return 1; 4 ]6 Q+ t: [: \, p( F0 b}//move //打印过河步骤 . u0 s6 [$ \ Evoid 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); " J: K) h8 L; e4 g for(i=1;i<=top;i++) { switch(s.m) ; _, a" f6 a% x: n' _/ A { ( }) G$ |) C- r3 f W6 b case 1: if(s.man==1&&s[i-1].man==0) fprintf(fp,"人带羊从起始岸过河到目的岸\n"); 8 K/ i+ Q/ y' R else 4 V5 j8 {& U# g$ k5 C/ U# o" h fprintf(fp,"人带羊从目的岸过河到起始岸\n"); $ `; j# r' h" j4 ], p break; case 2: if(s.man==1&&s[i-1].man==0) fprintf(fp,"人带狼从起始岸过河到目的岸\n"); 0 ~2 M: q' l! { else fprintf(fp,"人带狼从目的岸过河到起始岸\n"); ) O9 P& H9 _' [$ f( j9 A- _ break; % x. @, j$ Y' M' o0 u* {; M; O( G( n, h case 3: if(s.man==1&&s[i-1].man==0) fprintf(fp,"人带菜从起始岸过河到目的岸\n"); else fprintf(fp,"人带菜从目的岸过河到起始岸\n"); 7 S. v* G; c j8 ]& \8 b break; case 4: ! E2 W, K1 Q8 J3 a4 n% z X: n, } if(s.man==1&&s[i-1].man==0) fprintf(fp,"人单独从起始岸过河到目的岸\n"); : A. a% Q4 f9 Q6 v& {: g else fprintf(fp,"人单独从目的岸过河到起始岸\n"); 4 P a: @: f: [& |5 f& N break; - b4 l* r" q" [! Q4 V; J1 K }//switch 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

//检查两岸合法性已经有无状态与历史重复性 int check(int top) { int i; 0 E$ A! N; J9 A. [9 y* ^! n//检查两岸合法性 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)) 5 W/ y1 C- d8 p2 Y8 m return 0; X( Y4 m5 S7 p1 n1 T& j //检查历史重复性 2 }7 v& A8 D, \. v0 P: A* j4 @4 B3 W 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) - T$ U* u& w W2 |; G5 t! @% A( @ return 0; //ok return 1; 6 M! i; y9 K- n! `3 s0 H* o} 7 Z" K. E" z4 b4 Hvoid f1(int top) 6 s4 h2 l% W7 t8 k6 }% J{ ! g1 C: L# u( u. j int m; if(top>0)//0状态(初试状态应该是预先设置好的，所以要做状态1，故，初试top进来应该是1 { //对每次状态分别试探4中方案 2 h i' C9 H- O( { V 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; 4 s M! J8 y. c$ ` //用方案m移动，同时检查结果 if(move(top,m)&&check(top)) / E d! Q5 V) k9 a; O, c { if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf ) ; D; j4 c: _% t6 ]7 d! b6 j8 }/ o { //打印渡河步骤 display(top); , L2 P9 D1 `# ^; q: K //统计方案个数 8 M3 W# W& V4 b: P count++; fprintf(fp,"count=%d----------------------------\n\n",count); 8 C& V* c) R9 R' n, @3 P0 ? if(count>1000) exit(1); # P- ]; s% S# s } 6 `% e6 M) f9 \5 i else 1 e m* F; G) b& _3 ? f1(top+1); / z4 ?) q5 M- l5 _% B } , i4 Q' G/ ~! [ }//for $ L, P- Z$ M& j& D: @2 Z" u }//if(top>=0) $ g9 n2 a, p: a+ l9 ?% o4 {7 }6 O}//f1

1 B7 L9 v) y0 U( G

8 @/ e: ^$ h, S2 d& \" z

9 |/ v# D; e1 B6 R' @# |void f2() ! b8 q" X# d3 g. m( x{ # V$ U* g' I* h/ H int top=0,i; //开始时都在起始岸 % a0 @$ J9 p+ n; ?8 { s[top].man=s[top].sheep=s[top].wolf=s[top].cabbage=0; ( Y+ r- D" V, v4 V; ~8 V //未开始渡河 s[top].m=4; / X% f0 f8 Y$ @: S) H1 w while(top>=0) { if(check(top)) , L& \. M# G, W# V1 V; x% T( \ { {1 s1 g" a. a; Z# v4 Q* C- a& f) g if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf ) 2 W1 [7 ]1 B0 s+ F5 c# f { 1 ^$ r& O6 V* ] //打印渡河步骤 0 U! l8 M ]" l. C display(top); //统计方案个数 % l/ q: v% D% w7 D8 Z count++; " M0 |. A8 t* p j. w- z fprintf(fp,"count=%d----------------------------\n\n",count); if(count>1000) exit(1); ) [; a% ^9 ] V# P9 h. l# a$ \ //回溯 & Q* R# ^- Y/ M while(top>=0&&s[top].m>=4) ( U& k% c$ y" ~& _! ~( N8 D9 o" } top--; 4 g! Z& I( ~' j1 N- l1 t if(top>=0) 3 ^. a4 C( I4 b { //在上次状态基础上准备做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; 5 i u( F% L7 C& _. w i=1; ; B& i+ o. V" A1 ?3 L% k while(s[top].m+i<5&&!move(top,s[top].m+i)) 0 {9 z, ], m2 r* m! a4 H9 |6 M* w i++; ' ^: e! ]7 q9 q6 |0 b( v. l3 N }

9 p5 w% S" N$ \, Y5 f1 D

} else 0 R1 a Q/ D' x, K: R/ M { 6 G) Q0 c5 w- f5 L6 T3 J. M top++; //在上次状态基础上准备做move 0 i# \& |9 b5 n# b3 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; 2 W5 v0 h2 k/ [, Q2 l( H5 i) u while(i<5&&!move(top,i)) - Y5 m' | e( @# u$ Q" `4 n i++; + f0 n7 n9 J6 D, d' F# A }

- B9 [# Y! n$ h; \* ~6 P I+ l

} 2 Q- q0 m8 W! {' O else { //回溯 while(top>=0&&s[top].m>=4) . [- |$ L0 U P) A( \) A/ L top--; # B# Q, e1 c, G0 N4 c if(top>=0) 4 J6 \& Y7 {7 R: Y+ ]2 [. `: f9 X& ^ { //在上次状态基础上准备做move s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; ; |% [+ F/ ^$ n3 ?" X3 O; k; E& y s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf; i=1; 7 V c8 b" E( ^4 g/ i9 C. V" w while(!move(top,s[top].m+i)) i++; } } }//while * j h' |2 B0 ~4 [" ? F+ @}//f2 . I0 Q7 t: {% g6 b+ N( k( u//---------------------------------

sally

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

huashi3483

呵呵，好搭档

lynn324

是用c编的吗?

mnpfc

呵呵，看过了