渡河问题

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?

- j, F7 c/ e$ n

程序代码：

. u4 J2 y) K( ?+ Z0 Z- \

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

! V9 v! h7 F& @' N

#include <stdio.h> #include <stdlib.h> 0 f7 c% Y& z2 y( D% c* S9 b3 T#define MAX 50 struct state { int man,sheep,wolf,cabbage;//0:在起始岸；1：在目的岸 5 Z% v" c8 l+ `- y* K int m;//所采取的过河方法，(1--4) }s[MAX]; 0 l" I/ x. |1 H6 [/ Tint count=0; FILE *fp=fopen("c:\\2.txt","w+");

# o8 U( V# L1 Y- d" a3 H

void main() { ! U! [6 Q4 @$ \8 q( ] void f1(int ),f2();//f1试探递归 s[0].man=s[0].sheep=s[0].wolf=s[0].cabbage=0; 3 c' d) W; s' ^, G- X( u: i- p s[0].m=4; * j# F/ t$ B% D4 u s[1].man=s[1].sheep=s[1].wolf=s[1].cabbage=0; f1(1); 6 ^" N# b# G9 ^3 B; x% K N4 m8 P //f2(); fclose(fp); printf("\n");

& b$ M8 x( Y% _ C+ \- r5 s

} //用m值决定的方法渡河，成功返回1,否则返回0 int move(int top,int m) / m1 _4 A/ p. n: V+ O( j2 _{ : H8 v8 r& ]) A+ _' s$ @ { switch(m) 6 \2 T) A+ V% e) Q$ ~( J! ]4 k { % ` S1 B$ i& i; E) B9 a //人带羊过河 case 1: //判断人羊是否在同岸 9 M; N% j; n9 X$ p- G% V if(s[top].man!=s[top].sheep) return 0; ; L2 ~2 t/ o S% G; I s[top].sheep=s[top].man=(s[top].man==1)?0:1; s[top].m=m;//存储过河方法 . X, T; q6 q( X% _: i0 M) \0 i# H break; % h, o# W7 @* P; W9 E# R* t( A case 2: if(s[top].man!=s[top].wolf) return 0; 7 U6 y, ~' U: |0 k4 g3 V s[top].wolf=s[top].man=(s[top].man==1)?0:1; s[top].m=m;//存储过河方法 break; # l3 j+ C7 _2 N) q; ] case 3: ) \% r, I5 ^7 }6 `. e if(s[top].man!=s[top].cabbage) ' L6 m% N% Q9 O) Z( T: h return 0; s[top].cabbage=s[top].man=(s[top].man==1)?0:1; 9 b7 K0 K) T0 m s[top].m=m;//存储过河方法 break; //人单独过河 ( o( ~" a6 N% p3 C2 t case 4: s[top].man=(s[top].man==1)?0:1; 9 i$ q8 r2 Z# @1 j s[top].m=m;//存储过河方法 " D7 k* N% c( C1 K. [/ H- y. C% c break; ' A3 P( n; K8 X% N% t' z6 I& C }//switch 2 r9 R" u; \5 t6 n8 J* @9 O return 1; & C! z) d5 S* A# K5 k4 k, [% K}//move + ?6 \0 W) h+ U//打印过河步骤 void display(int top) - k4 _1 Q8 Y* K5 Y/ h. Q2 b6 z{ 3 Z2 U( W! {# u6 N- E 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); * w" d2 V; |& o8 J8 N" z for(i=1;i<=top;i++) { , M5 O# K% M# P/ g' k' y switch(s.m) { - m3 u4 F2 b. m/ G% g2 F+ n4 [( e case 1: 8 A2 p1 Y% p3 H6 g: c1 J0 _! R% l if(s.man==1&&s[i-1].man==0) : w( T- s& j( b( z; G, b& w) o5 ~# u fprintf(fp,"人带羊从起始岸过河到目的岸\n"); else 8 l7 x) W% [' j- m- p, B fprintf(fp,"人带羊从目的岸过河到起始岸\n"); break; ) k' t- O- H* Z- ?6 M case 2: * ^. R/ W, G3 B; v8 I% X if(s.man==1&&s[i-1].man==0) / J/ Y2 A6 ^, R0 I6 h9 G1 X) }, S' [ fprintf(fp,"人带狼从起始岸过河到目的岸\n"); else & h4 q( ]# H- t) ~# J% `, a fprintf(fp,"人带狼从目的岸过河到起始岸\n"); break; case 3: if(s.man==1&&s[i-1].man==0) fprintf(fp,"人带菜从起始岸过河到目的岸\n"); else 5 f# M$ l" B, G5 t: f) J6 K$ C fprintf(fp,"人带菜从目的岸过河到起始岸\n"); break; 1 k1 l* Z" W* \4 | case 4: if(s.man==1&&s[i-1].man==0) fprintf(fp,"人单独从起始岸过河到目的岸\n"); & x0 [" i2 E& @ else fprintf(fp,"人单独从目的岸过河到起始岸\n"); 8 i: [3 T# r6 m8 l break; }//switch 3 O4 W9 {7 _/ o2 t. T fprintf(fp,"state%d: man: %d, sheep: %d,wolf: %d,cabbage: %d\n",i,s.man,s.sheep,s.wolf,s.cabbage); . @: T0 ~6 i6 C# n4 Y }//for 1 p, D; F& ~7 _/ Y0 }2 Ufprintf(fp,"All ferried successfully!\n"); }//display

7 V9 n' c/ R% v7 `! `) F, x

//检查两岸合法性已经有无状态与历史重复性 int check(int top) t0 y- \& i( u, W7 c& Q, [% d2 x{ int i; a, X7 s. B# Z1 c//检查两岸合法性 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)) return 0; //检查历史重复性 for(i=0;i<top;i++) 7 l2 s9 H" L6 K7 g; h if(s.man==s[top].man&&s.sheep==s[top].sheep&&s.cabbage==s[top].cabbage&&s.wolf==s[top].wolf) & G5 c" Q1 D3 _/ s3 } return 0; 2 R1 d( z0 M3 K" B1 q, G4 A# ^* m' c& O0 P //ok & [ t3 w6 v3 w/ F e# n$ |5 U* w return 1; $ B; j9 F2 m9 {) X/ \} 3 i8 D$ `9 Z3 ?5 mvoid f1(int top) { int m; 0 s& q$ g( K- @( w if(top>0)//0状态(初试状态应该是预先设置好的，所以要做状态1，故，初试top进来应该是1 { //对每次状态分别试探4中方案 for(m=1;m<5;m++) { //每次方案的实施是在上次结果状态上做的 + q& n$ W ?2 X2 S0 K( s' 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; - e% w, l, ^1 I+ @& b //用方案m移动，同时检查结果 if(move(top,m)&&check(top)) { if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf ) % @! s0 r' v" u7 {- m { 0 h+ [( E2 x2 |; b4 g' ` //打印渡河步骤 ! O* S- C' G Y& E6 q4 A- n display(top); * p2 r! a9 _( J3 F+ I4 o s //统计方案个数 count++; / Q4 C( Q1 `2 S/ [ fprintf(fp,"count=%d----------------------------\n\n",count); if(count>1000) exit(1); . {( Y( ?1 {% E- m, W& U7 ] } g- H, \! E; G else f1(top+1); } }//for }//if(top>=0) ( P1 S. ]. T( C}//f1

, ]8 t, Q3 J- n

void f2() { int top=0,i; //开始时都在起始岸 # U+ N! l: c2 r0 J s[top].man=s[top].sheep=s[top].wolf=s[top].cabbage=0; s4 S0 w _* Z. w* X7 |% u% ] //未开始渡河 - _& ~; C' H0 H. e5 e s[top].m=4; while(top>=0) { if(check(top)) { - C: |/ ]& ?5 t( {4 X+ D if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf ) 2 }! Z8 d+ @6 K+ g: e" a { //打印渡河步骤 display(top); //统计方案个数 3 O3 w/ V3 |6 K1 |6 y# Y count++; 1 v' O7 ]" U# j4 R; X' t fprintf(fp,"count=%d----------------------------\n\n",count); " y# S, O9 W k$ Z7 J if(count>1000) exit(1); & Y- u4 Q* a% d) Q: p1 T //回溯 2 p+ k1 _0 }: B! d" D, t while(top>=0&&s[top].m>=4) top--; if(top>=0) { 7 O/ W. C. \2 y //在上次状态基础上准备做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 ?/ g, L9 w: @2 d8 L' | i=1; while(s[top].m+i<5&&!move(top,s[top].m+i)) i++; }

8 z, `5 @# {+ z8 Y. E

} else ( ]* a$ }$ A( [* R' O6 Q$ | { 2 `+ j8 S# ^6 \4 Y. _3 \; | 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; ) ~0 I- |' B. {5 T* x0 ^/ J. G: w while(i<5&&!move(top,i)) c6 `, d5 J- ^, c i++; }

} else { //回溯 while(top>=0&&s[top].m>=4) top--; ) y( |& b* V8 h' E. s1 M if(top>=0) { //在上次状态基础上准备做move 8 O! g1 F6 F( O8 J* | s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; 9 m. Y5 P# d1 U s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf; 9 ?6 _" G2 Y7 E. n: g i=1; 5 F6 ]1 M. a R/ n* R while(!move(top,s[top].m+i)) ! P- G: f) Y# P5 K4 d i++; } " s7 ^; r* }! G: y- S } 6 l' ^6 s4 l# D8 p5 g, i. N }//while }//f2 / E/ i3 p* g* W//---------------------------------

sally

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

huashi3483

呵呵，好搭档

lynn324

是用c编的吗?

mnpfc

呵呵，看过了