渡河问题

sally

渡河问题

, \% v; s% V) n# ]5 F9 @5 E2 c- ^

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?

1 E* ~" p' g0 Y6 A$ t, T9 g9 Y

& V S1 S7 Q& X) T

程序代码：

! ?% c+ M" e- c' d- e

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

3 f. v# R3 e8 M. x T

#include <stdio.h> #include <stdlib.h> #define MAX 50 8 y+ h- q! J: Z$ R. {struct state { int man,sheep,wolf,cabbage;//0:在起始岸；1：在目的岸 int m;//所采取的过河方法，(1--4) ! G; ?8 r3 } I: s5 c* J# @6 X}s[MAX]; 0 H6 U4 A2 O) ?5 xint count=0; FILE *fp=fopen("c:\\2.txt","w+");

void main() % o0 {. @9 M$ P: n1 f& L! V{ void f1(int ),f2();//f1试探递归 ( j. \* A+ `' T. a$ b9 C0 ~% O s[0].man=s[0].sheep=s[0].wolf=s[0].cabbage=0; 4 f, O9 H. u4 [2 J9 P s[0].m=4; 5 q& E* y- o: e7 [) a s[1].man=s[1].sheep=s[1].wolf=s[1].cabbage=0; f1(1); //f2(); - {- l# L+ g2 B& G fclose(fp); : i1 l7 v, e* R9 n printf("\n");

} 8 q% Z! _4 |. |//用m值决定的方法渡河，成功返回1,否则返回0 int move(int top,int m) { % c$ L) @9 @) |. h3 u- ` switch(m) # S% ?7 L# e6 b5 J5 s { . e* H) \1 c0 v //人带羊过河 case 1: + L: N8 f |+ O. z# {. D' ~ //判断人羊是否在同岸 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;//存储过河方法 break; 6 f2 L; D$ H" x# k case 2: 9 }6 L. ~# B) C$ \6 u+ U if(s[top].man!=s[top].wolf) return 0; 4 r2 n& W! p) ` s[top].wolf=s[top].man=(s[top].man==1)?0:1; s[top].m=m;//存储过河方法 , z# T4 _9 K) s- p break; case 3: if(s[top].man!=s[top].cabbage) 4 S. q0 T" i4 ~ return 0; 2 M3 n" {1 v4 f) s& x ] s[top].cabbage=s[top].man=(s[top].man==1)?0:1; ) ]5 k, D5 g* Z( e4 _9 k s[top].m=m;//存储过河方法 / s7 M' H6 Q2 \3 R8 ] break; //人单独过河 % w# t' q2 h# W) A) e' G& \4 i, E% ]$ H& Z case 4: i0 A+ ]* P3 s. ^, w) i s[top].man=(s[top].man==1)?0:1; s[top].m=m;//存储过河方法 / [: h& F" C6 `) g4 \' J break; }//switch 7 ?( _; Y7 }" M0 J) h% x/ E return 1; }//move //打印过河步骤 * I; W; V! J/ R# Jvoid display(int top) { int i=0; / N: p. L9 A) ~' u. s! u% k/ g; [ fprintf(fp,"state%d: man: %d, sheep: %d,wolf: %d,cabbage: %d\n",i,s.man,s.sheep,s.wolf,s.cabbage); 0 Y; c+ |( m1 w! P5 o; o- j7 ? for(i=1;i<=top;i++) & ~8 F+ I8 u- h% v* l { switch(s.m) { case 1: ) `* q. h; d: l if(s.man==1&&s[i-1].man==0) fprintf(fp,"人带羊从起始岸过河到目的岸\n"); # Y y$ [) a- D: v0 s else fprintf(fp,"人带羊从目的岸过河到起始岸\n"); break; ! E& C; t J7 X: I6 U5 Q" A case 2: 3 k; N" @, T2 f2 ?9 E- t [ if(s.man==1&&s[i-1].man==0) 3 w( \. W+ f3 E fprintf(fp,"人带狼从起始岸过河到目的岸\n"); & H% h6 N0 u0 t! @& j# f/ I ^) w else fprintf(fp,"人带狼从目的岸过河到起始岸\n"); 8 \7 X$ b! A y" z7 C5 G9 j break; case 3: if(s.man==1&&s[i-1].man==0) 4 J# e& i, |" _# {2 S fprintf(fp,"人带菜从起始岸过河到目的岸\n"); else fprintf(fp,"人带菜从目的岸过河到起始岸\n"); break; # e+ O2 V, w* \ case 4: & ]2 d2 K# Y0 P9 m N. R if(s.man==1&&s[i-1].man==0) fprintf(fp,"人单独从起始岸过河到目的岸\n"); ) O: x4 i: D4 h3 | else fprintf(fp,"人单独从目的岸过河到起始岸\n"); * y* A" y8 B& [+ H; X. P' O break; }//switch : J0 ^2 P' T' I% b# y fprintf(fp,"state%d: man: %d, sheep: %d,wolf: %d,cabbage: %d\n",i,s.man,s.sheep,s.wolf,s.cabbage); 4 w' _! `2 o2 z- w9 T0 [ / t# ?; F5 h3 f i8 u) n! U }//for 1 ~ U7 l, W2 R+ e3 sfprintf(fp,"All ferried successfully!\n"); }//display

//检查两岸合法性已经有无状态与历史重复性 - F8 n/ G8 r' Tint check(int top) { int i; ' \9 t6 h. g2 x//检查两岸合法性 . z! N6 l* M- C* W) V$ c& N4 } if((s[top].sheep!=s[top].man&&s[top].cabbage!=s[top].man)|| 6 K0 E! v: o6 w0 W (s[top].wolf!=s[top].man&&s[top].sheep!=s[top].man)) return 0; ( I6 w! a: ^ L6 G& C7 I/ g //检查历史重复性 8 G9 g- n; o, g L* k 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) return 0; //ok return 1; } ( h8 x; O! E. g k. x Rvoid f1(int top) $ Y7 ~0 D6 w& B) L' w% a v{ , B: d9 C& _% s int m; , U; m$ w$ S5 }) m" e- [9 _& y if(top>0)//0状态(初试状态应该是预先设置好的，所以要做状态1，故，初试top进来应该是1 { //对每次状态分别试探4中方案 9 }8 R- R, p( t* ]5 @ Z7 e' x for(m=1;m<5;m++) { //每次方案的实施是在上次结果状态上做的 / `7 Z- P. ?6 z8 K+ G s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; ! Y: o6 L; _) C# [$ r s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf; % |! ~, I4 H: H8 v: z- d1 O, e& L //用方案m移动，同时检查结果 if(move(top,m)&&check(top)) { 0 [2 k; H; e! q1 C) C if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf ) : D$ Y0 F7 r4 O; G; E+ e { 1 M. Z, I9 u9 r$ e2 ?* t //打印渡河步骤 display(top); / c8 x1 ^& v8 i7 n* J" I //统计方案个数 count++; fprintf(fp,"count=%d----------------------------\n\n",count); if(count>1000) exit(1); } else # l0 D2 v! G; \2 L) J- N2 y( J$ v6 H f1(top+1); $ f( T) G8 c, E* y+ C8 Q2 v/ O0 K } - |( ^3 p' s+ J7 _6 t+ m6 f }//for & C+ z& r, r% V) x, }# G, H2 y! l }//if(top>=0) }//f1

" P; r* {. |6 m+ v+ r' f7 j

2 r4 C4 F2 k* [) C$ t+ \! e

void f2() { 0 m8 O4 {7 h% r* D6 O& j int top=0,i; //开始时都在起始岸 s[top].man=s[top].sheep=s[top].wolf=s[top].cabbage=0; * c# a% R9 V% _4 s) Y" a, d; [ //未开始渡河 & g: s/ e/ V7 g. m4 D6 t1 l% H s[top].m=4; while(top>=0) { if(check(top)) { if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf ) { //打印渡河步骤 display(top); //统计方案个数 count++; 7 N: Q* m; c4 H& }3 ^ fprintf(fp,"count=%d----------------------------\n\n",count); if(count>1000) exit(1); ( M: \# X# J# W/ i //回溯 , F6 t# `. l' @5 a) |% D' [9 | while(top>=0&&s[top].m>=4) top--; 1 `( d) N0 d+ f8 q7 M: ^ if(top>=0) { //在上次状态基础上准备做move s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; # o* x0 g/ `0 c! r# E+ [ s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf; i=1; while(s[top].m+i<5&&!move(top,s[top].m+i)) i++; , ^1 A) Z6 h# @$ f }

. ^0 W. _: o+ [: e

} - }* ~4 f' L2 ]( t6 S else 3 O1 G9 u9 x1 y1 u! e3 j! ] { top++; ' R% x* K) |( ]( x //在上次状态基础上准备做move s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; 6 W4 Q# x/ G$ B- S0 _' N s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf; ) q, n$ S5 i) x& @6 F. e' ~ i=1; while(i<5&&!move(top,i)) . W9 q! w0 O8 W2 r, F- B% x g- K i++; 4 `6 K( X! i5 i }

; A; p' E- J# a% `5 [& b: a. A

} else { //回溯 - f7 ~/ m3 T C$ u1 R/ z while(top>=0&&s[top].m>=4) top--; if(top>=0) 4 c# H6 K4 w- l* Z0 `# x6 } { //在上次状态基础上准备做move s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; ( ^) n$ ~2 W8 v0 P4 G1 f: h' f5 v/ W s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf; i=1; % c9 j9 d1 U" j' B+ C' v while(!move(top,s[top].m+i)) i++; " ~% x& {2 p1 i _ } } }//while }//f2 //---------------------------------

sally

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

huashi3483

呵呵，好搭档

lynn324

是用c编的吗?

mnpfc

呵呵，看过了