渡河问题
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?
3 M% H' X/ b4 f, l: j( {
程序代码：
//以下程序在Win98＋vc6.0运行通过
#include <stdio.h>" ?6 ?/ f M$ ?4 M- P
#include <stdlib.h>2 W- H7 \7 _$ n( L' x3 `" a
#define MAX 50# h" S' z! C) h. m, b7 w
struct state
{8 f0 A/ t( x" \8 w( q4 U( a. ]
int man,sheep,wolf,cabbage;//0:在起始岸；1：在目的岸: m2 q$ i2 E' }! L, C$ x
int m;//所采取的过河方法，(1--4)
}s[MAX];* x4 H4 @4 ?/ k: y$ n: j' q- K
int count=0;& Q# B8 N6 Z+ [
FILE *fp=fopen("c:\\2.txt","w+");
void main()
{
void f1(int ),f2();//f1试探递归6 J( P' q0 Z$ A4 z0 R+ k8 B
s[0].man=s[0].sheep=s[0].wolf=s[0].cabbage=0;
s[0].m=4;. p$ I4 }) Z* b: x* P' Q) z
s[1].man=s[1].sheep=s[1].wolf=s[1].cabbage=0;( b" Y, H/ v k8 X! F& {" D
f1(1);
//f2();
fclose(fp);$ ?% N. Y8 J- ~3 T; g
printf("\n");
}( `6 s. w% n }! }$ ~
//用m值决定的方法渡河，成功返回1,否则返回0
int move(int top,int m)
{
switch(m)/ B+ p; n7 e' Y4 p5 ~% Z0 Z9 P, v
{$ V# E! `9 Q5 u( |+ r* `! R
//人带羊过河
case 1:
//判断人羊是否在同岸
if(s[top].man!=s[top].sheep)
return 0;
s[top].sheep=s[top].man=(s[top].man==1)?0:1;- J: H+ F" F+ ^, S+ x
s[top].m=m;//存储过河方法0 t' A# K5 s" S" U
break;% U2 W5 H0 g( Z1 N. w' N
case 2:
if(s[top].man!=s[top].wolf)' F5 a$ K* o0 [% O
return 0;# A! R* H1 z/ R" `
s[top].wolf=s[top].man=(s[top].man==1)?0:1;
s[top].m=m;//存储过河方法4 _+ ^5 u1 K9 K3 t0 @: H
break;& K/ M2 C. P5 b8 b0 ]# ^
case 3:( ? Z$ w( Q& o& j0 i4 F8 q% [: H
if(s[top].man!=s[top].cabbage)
return 0;+ z S7 L3 z: ?% @' Z5 N
s[top].cabbage=s[top].man=(s[top].man==1)?0:1;0 Q, e, c# i* r0 H P2 A
s[top].m=m;//存储过河方法5 _, i5 @. t8 N, ~( R u$ y/ z( v
break;
//人单独过河, v% B {& J1 Y( V9 z
case 4:: ]) P" _4 I+ [0 b# t+ R* O% t* `7 Q* n# O
s[top].man=(s[top].man==1)?0:1;
s[top].m=m;//存储过河方法
break;: z- N& `* _ y
}//switch
return 1;
}//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);
for(i=1;i<=top;i++) W e y$ n2 X+ d, I- p: |
{
switch(s.m)
{
case 1:
if(s.man==1&&s[i-1].man==0)
fprintf(fp,"人带羊从起始岸过河到目的岸\n");' W1 O' x# Z. F+ C9 e0 T1 ~. i$ [
else; X1 K& G( M+ u0 {& `
fprintf(fp,"人带羊从目的岸过河到起始岸\n");0 s- S# j) @' Q/ F
break;- F- p& m1 h, M
case 2:
if(s.man==1&&s[i-1].man==0)
fprintf(fp,"人带狼从起始岸过河到目的岸\n");9 A" ?* d* ~7 k
else- [% a2 @! U& Y f4 {+ m
fprintf(fp,"人带狼从目的岸过河到起始岸\n");, o4 S$ `( u/ t% l
break;6 s' L5 y2 Y, }3 U, b
case 3:
if(s.man==1&&s[i-1].man==0)4 h( W8 b7 }) J7 `" H5 O
fprintf(fp,"人带菜从起始岸过河到目的岸\n");
else+ G' y$ q% w% z
fprintf(fp,"人带菜从目的岸过河到起始岸\n");
break;
case 4:
if(s.man==1&&s[i-1].man==0)
fprintf(fp,"人单独从起始岸过河到目的岸\n");9 x9 p) y/ i; k
else. A$ u9 Z. m5 j
fprintf(fp,"人单独从目的岸过河到起始岸\n");9 p: P" u1 c8 H. V
break;
}//switch
fprintf(fp,"state%d: man: %d, sheep: %d,wolf: %d,cabbage: %d\n",i,s.man,s.sheep,s.wolf,s.cabbage);
" t* z3 c9 V4 {8 O0 s
}//for
fprintf(fp,"All ferried successfully!\n");
}//display
//检查两岸合法性已经有无状态与历史重复性" _2 e$ K0 Q. r$ |7 O% f8 m
int check(int top)
{
int i;
//检查两岸合法性* v3 S1 X+ K! x( |( y
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;: Q3 B9 [: ]$ H: W! ~4 I
//检查历史重复性1 M3 z3 T6 ?: x% v
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;% ]' S- _8 v- _' u1 q
//ok
return 1;+ M: H, J) t2 i: A$ ^7 _" g P
}& N, F/ o- O2 X; J* I6 \
void f1(int top)
{) T, D- G0 X9 `; A8 A/ {
int m;' x8 M1 Z J3 s8 r( h
if(top>0)//0状态(初试状态应该是预先设置好的，所以要做状态1，故，初试top进来应该是1
{ //对每次状态分别试探4中方案
for(m=1;m<5;m++), [+ P2 z7 W3 M2 F+ p! m
{
//每次方案的实施是在上次结果状态上做的 Y. e* [% R1 V7 Q9 @: u* C
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))
{) i0 T5 i9 R6 V i6 u. o& W
if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf )
{3 F$ G/ F" y' `2 i
//打印渡河步骤
display(top);) T8 n2 k5 s, U
//统计方案个数( O( o; I/ x5 o& Z
count++; \9 t) S7 L p! A$ |: E! c* A8 T5 V R
fprintf(fp,"count=%d----------------------------\n\n",count);
if(count>1000) exit(1);
}- w5 ~; \. f- h& B
else
f1(top+1);
}# t" N! I% p0 I% P" J4 e
}//for/ i- p6 \* r( X1 k
}//if(top>=0)
}//f1
- V9 N" q5 {, p) u- x5 R
void f2() { int top=0,i;8 K) q8 c9 l8 z //开始时都在起始岸/ `% n" }( s7 F+ f& X% j$ w) A s[top].man=s[top].sheep=s[top].wolf=s[top].cabbage=0;. M2 O2 T* [2 m% K# D2 T //未开始渡河 s[top].m=4;' m7 e6 I6 ~2 x' G N while(top>=0)- e" V+ R; z/ v/ }2 @8 j {6 {7 z# Z$ j: w/ v ~8 {0 B2 ~ if(check(top)) {. f- v7 H1 ]+ m9 W4 i+ B/ m. ] if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf )5 c5 M H8 P: K+ [3 L {. k& d, A6 a7 E% V //打印渡河步骤 display(top); //统计方案个数. o" ~5 ]4 Z0 }8 \" H count++; 3 V6 k' f0 Y \5 f4 m2 |9 t6 H6 T6 w fprintf(fp,"count=%d----------------------------\n\n",count); if(count>1000) exit(1);9 U/ X9 G2 J. r //回溯$ ?$ {. f# o& X1 B9 y, n while(top>=0&&s[top].m>=4) top--; if(top>=0) {/ o7 p* s4 u$ J; D: Q! N //在上次状态基础上准备做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; z: j% l5 v; Y while(s[top].m+i<5&&!move(top,s[top].m+i))7 c! `: c# q* Z. I% A3 w$ | i++; }
}7 a3 Z e) Y8 @" k else) H' e8 u9 ^# B# I9 I7 F {- w7 q2 H4 F# l top++; //在上次状态基础上准备做move s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep;( n9 j, w# \( m0 } s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf;/ \" w3 _6 \% p. O3 e9 N( @ i=1;2 m& h( U* N- c, H while(i<5&&!move(top,i)) i++; }
3 a: P. X9 z% _9 Y A' U3 v}3 r, H G2 e& @) @) u" O else( m5 m. q7 p! v { //回溯: J) p9 P8 H2 D6 n+ f. J2 p5 G while(top>=0&&s[top].m>=4) ' q: K" |3 m% C! K( E. ~ top--;. a$ U) X) b" Z0 ~ if(top>=0)" e c3 r+ I% z5 R. e# M" a: p { //在上次状态基础上准备做move2 d/ ~6 o) e# B7 s9 u. t: W s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep;% I9 V3 m. g- q. p. C+ j2 T# o" F# v s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf;, k! L4 G0 Q; H4 @. e2 y: Y! _+ } i=1; ! `4 |! {. u+ g8 H* g0 y/ S+ } while(!move(top,s[top].m+i)) i++;# m& h5 p7 p {- c& ~$ g }: d2 ?% c6 o) i } }//while }//f24 u1 K' L, u8 A8 s //---------------------------------% r4 Z; l5 o: N: j. y; }& a
| 欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) | Powered by Discuz! X2.5 |