渡河问题

sally

渡河问题

. E* Y W- E6 m! L* e

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?

6 V4 m' T0 c4 F" X

# `( x$ \9 e2 G3 s2 D

程序代码：

7 I R3 X. i" }, D& M

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

#include <stdio.h> # y) s- D& o8 A4 u8 A( s. L8 y0 d9 A#include <stdlib.h> #define MAX 50 struct state : ~4 ]# j v$ T4 [4 S2 o. ~( |{ int man,sheep,wolf,cabbage;//0:在起始岸；1：在目的岸 int m;//所采取的过河方法，(1--4) }s[MAX]; int count=0; FILE *fp=fopen("c:\\2.txt","w+");

- G) D; p" @. g1 I7 M' d8 n T

void main() : I# @7 z& S8 O{ 9 X: X' i- Y9 |4 q) {. ~1 f4 G void f1(int ),f2();//f1试探递归 s[0].man=s[0].sheep=s[0].wolf=s[0].cabbage=0; 4 P {2 u" J$ A; M, \ s[0].m=4; ( o1 J' t3 ` ^; J) Q s[1].man=s[1].sheep=s[1].wolf=s[1].cabbage=0; f1(1); //f2(); fclose(fp); printf("\n");

} //用m值决定的方法渡河，成功返回1,否则返回0 int move(int top,int m) { switch(m) { ( t5 C) j) C, t% f T //人带羊过河 case 1: 0 b' U/ ^5 O* [0 Q1 A //判断人羊是否在同岸 if(s[top].man!=s[top].sheep) 6 X6 B# Z$ ~' Y( L& Q {3 e return 0; s[top].sheep=s[top].man=(s[top].man==1)?0:1; - N, O7 c+ W& n. i% T s[top].m=m;//存储过河方法 break; 3 q, y' O3 M. \. [ case 2: if(s[top].man!=s[top].wolf) return 0; s[top].wolf=s[top].man=(s[top].man==1)?0:1; s[top].m=m;//存储过河方法 break; case 3: if(s[top].man!=s[top].cabbage) return 0; , ~$ o- e, m8 ~5 ]. g( n s[top].cabbage=s[top].man=(s[top].man==1)?0:1; s[top].m=m;//存储过河方法 break; & U- ]7 |& {+ x //人单独过河 / ` S: H' i2 @$ b, z. } case 4: 6 X+ w( {* A4 n8 {' W s[top].man=(s[top].man==1)?0:1; ( [/ ~6 Z0 r7 x |# b3 H s[top].m=m;//存储过河方法 break; }//switch return 1; ; i; a: T8 ~5 {8 F4 T. D* b/ d}//move //打印过河步骤 void 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); 8 s6 P1 v3 m% R" n, r y- H for(i=1;i<=top;i++) 3 D1 m2 `8 H* z9 M) j# t { switch(s.m) { ! x; L6 D( U! q case 1: + J/ T4 e3 {' l5 L" q' {( B- x if(s.man==1&&s[i-1].man==0) ; m, m6 \& z$ o* q2 D fprintf(fp,"人带羊从起始岸过河到目的岸\n"); 7 D2 [6 u& q" p7 M/ N1 U! r else fprintf(fp,"人带羊从目的岸过河到起始岸\n"); 8 y$ j. I' L0 J, s5 I5 A$ q. a break; case 2: 7 p2 w: {- z+ _& n E1 U if(s.man==1&&s[i-1].man==0) fprintf(fp,"人带狼从起始岸过河到目的岸\n"); - Z8 C0 T; S! j' C$ h4 i else fprintf(fp,"人带狼从目的岸过河到起始岸\n"); 6 a' P* D% ] a- `) @: w7 s break; case 3: . n6 G; T7 A1 \ if(s.man==1&&s[i-1].man==0) fprintf(fp,"人带菜从起始岸过河到目的岸\n"); + d% C- K7 Q7 ~, l else fprintf(fp,"人带菜从目的岸过河到起始岸\n"); break; case 4: if(s.man==1&&s[i-1].man==0) fprintf(fp,"人单独从起始岸过河到目的岸\n"); else 1 L! G% P* `9 O5 |7 M. H fprintf(fp,"人单独从目的岸过河到起始岸\n"); $ C1 ]! |+ ~. T- |0 T5 ?. R break; ! v% G9 w$ b8 P8 r# _! p' P }//switch fprintf(fp,"state%d: man: %d, sheep: %d,wolf: %d,cabbage: %d\n",i,s.man,s.sheep,s.wolf,s.cabbage); }//for 4 M5 z1 }1 s! ofprintf(fp,"All ferried successfully!\n"); }//display

5 N9 _6 p! n3 _4 n5 t2 z6 {1 t! P# F

//检查两岸合法性已经有无状态与历史重复性 . q& p1 c/ ?. n; l) t) n& K; qint check(int top) { $ ~3 [, e1 \* ]' s. q5 s int i; //检查两岸合法性 if((s[top].sheep!=s[top].man&&s[top].cabbage!=s[top].man)|| 5 V4 \$ m& c+ K$ ^: G0 ^# I3 P3 h (s[top].wolf!=s[top].man&&s[top].sheep!=s[top].man)) return 0; //检查历史重复性 6 Z/ f/ g) a: A2 z for(i=0;i<top;i++) ( D) ~7 d+ e+ `- w% P if(s.man==s[top].man&&s.sheep==s[top].sheep&&s.cabbage==s[top].cabbage&&s.wolf==s[top].wolf) return 0; D: W% b7 [+ ~0 H9 ]9 S0 ]1 ] //ok return 1; 5 j5 _5 t% p* P( _4 S} 2 ]) Y# x0 P4 ]' kvoid f1(int top) ! _" N6 q4 d# C: K1 `2 ~{ int m; $ [, ~# g; t' W9 Z- [ if(top>0)//0状态(初试状态应该是预先设置好的，所以要做状态1，故，初试top进来应该是1 { //对每次状态分别试探4中方案 for(m=1;m<5;m++) 2 g! x5 c9 T# x0 Q$ ^8 d2 a { //每次方案的实施是在上次结果状态上做的 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; //用方案m移动，同时检查结果 if(move(top,m)&&check(top)) { / j8 U- L, g1 } if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf ) 2 a: c* \8 G( D+ H% M' W { ; N+ I9 I" h: [+ d! p //打印渡河步骤 ( u5 T# k' i9 q+ C6 W, U, I display(top); //统计方案个数 W) @0 C- v9 c3 ~3 P count++; fprintf(fp,"count=%d----------------------------\n\n",count); " D4 F C) q1 c0 l1 R+ W2 k# _4 s- x ` if(count>1000) exit(1); } else 5 A& o4 x. I: N$ D! ]$ ?# r f1(top+1); , J' ?4 H! f# r) h# E! H3 u } }//for & Q, Q! Z3 l, h* j+ Y1 C& V" ~ }//if(top>=0) }//f1

+ ~7 `0 t; u1 Y4 y+ e9 q

8 A$ y2 _' b; f0 W! A

3 i! H3 s. n4 {. S! |, v

+ [! S' }$ D) ?void f2() 6 f$ {+ r+ e: O# }7 j7 d# p{ int top=0,i; //开始时都在起始岸 s[top].man=s[top].sheep=s[top].wolf=s[top].cabbage=0; //未开始渡河 $ `, i0 r6 v7 c$ s" P8 L5 g" O/ p% ` s[top].m=4; while(top>=0) 7 |4 | {. {- j5 R6 T { if(check(top)) { * Y9 P! U1 K! L6 n% V" f" w$ o+ S if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf ) { + ?; q- u5 B2 \ //打印渡河步骤 display(top); //统计方案个数 count++; " }* R: t* {+ A& H0 ^' z5 c fprintf(fp,"count=%d----------------------------\n\n",count); 8 ~0 A1 Q( H: \( q$ b if(count>1000) exit(1); " F7 z6 o/ ?# F! b //回溯 while(top>=0&&s[top].m>=4) top--; if(top>=0) A2 {4 a, {# Y+ g { //在上次状态基础上准备做move s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; ! K* j* I) ~: L3 i; S5 |3 j s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf; i=1; 4 c! ~- k' @6 E+ q3 G while(s[top].m+i<5&&!move(top,s[top].m+i)) i++; - M' b) L6 K# f) X7 J }

} else { top++; //在上次状态基础上准备做move : ?% c, }. A* w5 t s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; 1 T/ P1 w3 Q9 [' R# w, G s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf; 7 @3 w* N7 t) Z& }9 T i=1; while(i<5&&!move(top,i)) i++; }

} else { //回溯 * E: j" ?$ W! i% g while(top>=0&&s[top].m>=4) + ]6 s* s% i3 f5 s" L. e& R top--; 4 F( B( o$ O# t( w7 f. \+ r' L+ Y if(top>=0) { , f1 X: j$ I. K //在上次状态基础上准备做move ) W, x' _3 M* `# V Z& I- X s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; , P1 G% U: R, n, |0 i3 D s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf; i=1; 2 m* O2 C" s0 b9 e8 y while(!move(top,s[top].m+i)) i++; } } : z9 D7 a# `) A+ v- T" E' R9 g( M& B- z }//while }//f2 2 F8 P4 k! s4 T& Z' a: x//--------------------------------- 9 a2 D2 U7 _" G3 j0 b# h

sally

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

huashi3483

呵呵，好搭档

lynn324

是用c编的吗?

mnpfc

呵呵，看过了