渡河问题

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?

$ G8 s% z& _9 Y u1 \. K

程序代码：

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

#include <stdio.h> 5 `5 a5 x7 R$ ~ y& K& p2 f#include <stdlib.h> #define MAX 50 5 [( R+ b9 ~- w, S! T* o' H% Kstruct state / m: ~7 X4 p$ C! t7 A2 s9 u{ int man,sheep,wolf,cabbage;//0:在起始岸；1：在目的岸 int m;//所采取的过河方法，(1--4) 6 \0 \0 u( k6 n# A& ~}s[MAX]; & G! v1 j: W, @8 O6 xint count=0; FILE *fp=fopen("c:\\2.txt","w+");

void main() { void f1(int ),f2();//f1试探递归 s[0].man=s[0].sheep=s[0].wolf=s[0].cabbage=0; s[0].m=4; 3 v# r" h0 K0 \1 F s[1].man=s[1].sheep=s[1].wolf=s[1].cabbage=0; f1(1); //f2(); fclose(fp); ; T' h( p$ C& v8 O$ B7 F printf("\n");

' @" W. _" M3 F- L- i4 N0 [

} //用m值决定的方法渡河，成功返回1,否则返回0 int move(int top,int m) { 0 m) U, u+ I8 i switch(m) 6 R j; d, ]- m" o# w; r5 a# _7 K3 \ { 5 T. a* O! w6 } }/ v3 w //人带羊过河 case 1: % y$ x9 y% [6 Q //判断人羊是否在同岸 3 W4 a0 _: m y: M0 f! ` if(s[top].man!=s[top].sheep) return 0; 3 n+ L; H. Y0 z s[top].sheep=s[top].man=(s[top].man==1)?0:1; s[top].m=m;//存储过河方法 8 E. q# r8 B# o1 T: z break; + B: u) {" u+ n- Q' o$ n. s, I case 2: ; @ G- O; b+ c; C' N/ ] if(s[top].man!=s[top].wolf) ' F# C: ~; D5 D4 o9 [4 A+ T6 y) i return 0; s[top].wolf=s[top].man=(s[top].man==1)?0:1; A" F; M6 ?- I, i |' f2 c s[top].m=m;//存储过河方法 break; case 3: 1 s `. u( i; l4 a+ L1 C: z if(s[top].man!=s[top].cabbage) return 0; 0 O O! ?) d% `, `6 I% e1 o+ \7 | s[top].cabbage=s[top].man=(s[top].man==1)?0:1; 6 r, Z' ?% S! @) K1 i% N s[top].m=m;//存储过河方法 break; " d* _: o( K8 o) | //人单独过河 6 u; I/ A, E& n! G, i$ e9 B case 4: : h* r* Z- Z2 Y( m s[top].man=(s[top].man==1)?0:1; & ]) r! Y% H. F4 J s[top].m=m;//存储过河方法 break; }//switch / J, Y7 ~& U s% L, v0 G return 1; }//move //打印过河步骤 void display(int top) & M. l* o9 A7 J- T{ int i=0; 2 D6 J8 c& u9 x7 T fprintf(fp,"state%d: man: %d, sheep: %d,wolf: %d,cabbage: %d\n",i,s.man,s.sheep,s.wolf,s.cabbage); + o7 |. ?& k6 ]& Q8 ~ |8 ] for(i=1;i<=top;i++) + \- Y: v W& }5 c! l( L- I { switch(s.m) $ M/ V& a& n7 I' c3 } { : e: T8 N0 U% A4 g' G& r; g case 1: if(s.man==1&&s[i-1].man==0) : p+ d, E/ R3 K1 C6 W" I4 q fprintf(fp,"人带羊从起始岸过河到目的岸\n"); else fprintf(fp,"人带羊从目的岸过河到起始岸\n"); break; case 2: if(s.man==1&&s[i-1].man==0) fprintf(fp,"人带狼从起始岸过河到目的岸\n"); 5 h6 S5 ^% y- O# O- T2 Q else fprintf(fp,"人带狼从目的岸过河到起始岸\n"); break; case 3: if(s.man==1&&s[i-1].man==0) : |' ?1 s( q: H2 X! } fprintf(fp,"人带菜从起始岸过河到目的岸\n"); else + n W$ i: Y! J- A( |5 s fprintf(fp,"人带菜从目的岸过河到起始岸\n"); - }. |1 T5 I1 n% N& g3 h break; case 4: if(s.man==1&&s[i-1].man==0) # K6 B( _ E) `, Z! a fprintf(fp,"人单独从起始岸过河到目的岸\n"); ! @* C# @. Z# b7 c& g- u0 G# S else fprintf(fp,"人单独从目的岸过河到起始岸\n"); break; }//switch fprintf(fp,"state%d: man: %d, sheep: %d,wolf: %d,cabbage: %d\n",i,s.man,s.sheep,s.wolf,s.cabbage); ( ^. D: t( h4 ]7 T* V4 Y" q 9 E4 [& h) M7 w" ? }//for fprintf(fp,"All ferried successfully!\n"); - ?# \! x; w. m" w/ g6 w7 v}//display

//检查两岸合法性已经有无状态与历史重复性 int check(int top) { : f5 r U/ t }! m+ z: C$ S int i; //检查两岸合法性 & b l+ w4 g: M7 G2 y* b if((s[top].sheep!=s[top].man&&s[top].cabbage!=s[top].man)|| 7 A7 \/ n* j: C+ `& }* `" W6 I (s[top].wolf!=s[top].man&&s[top].sheep!=s[top].man)) return 0; + T0 G$ |/ S' `0 u4 B //检查历史重复性 for(i=0;i<top;i++) $ t7 A; z5 J' O E( p, u1 s$ \ if(s.man==s[top].man&&s.sheep==s[top].sheep&&s.cabbage==s[top].cabbage&&s.wolf==s[top].wolf) : t4 q5 K: U" s6 }# N0 t: m/ @ return 0; //ok 3 X) ~- Q9 i" E5 Z! k: }$ G return 1; - J' `$ Q1 I' {# x* s} void f1(int top) { int m; ! q1 K/ ]& Q( V# f2 z$ H if(top>0)//0状态(初试状态应该是预先设置好的，所以要做状态1，故，初试top进来应该是1 { //对每次状态分别试探4中方案 ( V" [, W3 o! k1 q# N5 d for(m=1;m<5;m++) { * a8 a' G& ~0 |; r A) ` //每次方案的实施是在上次结果状态上做的 3 g+ d/ I0 K _* H k s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; 6 g. e; W9 Q' O s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf; % u' E4 t) b) C //用方案m移动，同时检查结果 if(move(top,m)&&check(top)) { if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf ) 6 P9 w" f% f5 V' b$ ~9 B { //打印渡河步骤 display(top); //统计方案个数 count++; fprintf(fp,"count=%d----------------------------\n\n",count); if(count>1000) exit(1); } else f1(top+1); ' h/ E% e7 A" u1 ^ } }//for ) h; h) D3 x1 R2 w }//if(top>=0) $ Z# c- d8 c( @0 \}//f1

. W# n. K4 V: @+ t

' H8 A+ L, G3 N6 m, C$ B3 t+ U5 t

# s' ]9 @0 O s: Nvoid f2() { int top=0,i; //开始时都在起始岸 # W4 Z$ e; a; P; i3 z s[top].man=s[top].sheep=s[top].wolf=s[top].cabbage=0; //未开始渡河 , I6 s% W; h b* k) s5 \ s[top].m=4; ; ]8 I) C7 w, t0 v, Q, o while(top>=0) { if(check(top)) { ( @9 A9 `2 U- G* M. w2 W if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf ) 1 \8 c" G( E( h( T( k) p5 |: v { //打印渡河步骤 1 R" \% m, U0 t4 G9 e* F# r' T display(top); $ x# O# }/ J, _) n/ N8 y3 P, z# p //统计方案个数 * Y( `, N# W& H count++; 1 [! V0 S1 m; A6 Y fprintf(fp,"count=%d----------------------------\n\n",count); if(count>1000) exit(1); ( _9 R m& X4 |8 k6 F2 e8 @ //回溯 while(top>=0&&s[top].m>=4) top--; if(top>=0) { //在上次状态基础上准备做move . F$ `, N- R6 u9 q, B s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; # b- [! n: i: l5 o2 @ s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf; i=1; * n1 q/ g& q% l# F while(s[top].m+i<5&&!move(top,s[top].m+i)) i++; 0 M3 t! k" V; O' b7 H- | }

} 8 T; t* z: j) s) I' A else & v7 {3 G" M3 q" {, W { top++; 1 m) x' b8 P# a //在上次状态基础上准备做move ) G+ u2 P0 ~, d$ r 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; : D; w$ }4 Y1 O% y i=1; 9 ~ B. d! f& A. m% T while(i<5&&!move(top,i)) i++; }

R. s8 ^$ F- O, `0 Z, i& s1 z5 s

} 1 Q! S- n; @( K5 [6 Z1 U else { //回溯 9 N8 J* A: l/ T$ ` G) m7 x while(top>=0&&s[top].m>=4) 1 c8 [3 q7 u* N top--; if(top>=0) { u1 l1 v2 W/ ] //在上次状态基础上准备做move - _! H0 P1 a0 S s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; 4 h- @# Y3 ]% p s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf; i=1; while(!move(top,s[top].m+i)) i++; } } % n0 o$ E# F2 K& a3 X3 i$ V( F }//while }//f2 //--------------------------------- ! _6 E* O; v- M- `- ~

sally

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

huashi3483

呵呵，好搭档

lynn324

是用c编的吗?

mnpfc

呵呵，看过了