渡河问题
- U; s8 u n$ e9 b$ X: T4 z6 aA 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 e8 K% Y' y$ Y+ V; D6 \6 `7 H
程序代码：
//以下程序在Win98＋vc6.0运行通过
#include <stdio.h>. U( C* {" o g" k: o4 q( F
#include <stdlib.h>
#define MAX 50
struct state
{& G, B3 w! A6 F
int man,sheep,wolf,cabbage;//0:在起始岸；1：在目的岸1 U0 P+ I& Q8 f8 t! e
int m;//所采取的过河方法，(1--4)% @7 G7 p2 b j+ W
}s[MAX];0 p# |7 h1 J. t) P9 N
int count=0;
FILE *fp=fopen("c:\\2.txt","w+");
void main()
{
void f1(int ),f2();//f1试探递归4 E* [% R+ E' U1 I# |; D
s[0].man=s[0].sheep=s[0].wolf=s[0].cabbage=0;) d$ F$ S9 V/ Y0 U S
s[0].m=4;
s[1].man=s[1].sheep=s[1].wolf=s[1].cabbage=0;
f1(1);
//f2();+ r9 }! i7 X8 I# \
fclose(fp);, C2 [# }8 [6 k" F" j2 a& o6 f
printf("\n");
}
//用m值决定的方法渡河，成功返回1,否则返回0
int move(int top,int m)+ i& z, Z0 d4 a0 h5 [2 T2 K, }
{
switch(m). k' h) h6 f7 p9 M
{$ H6 ^4 G9 Q, x9 y! _8 C7 Z
//人带羊过河3 U/ _8 H# b% d+ [
case 1:
//判断人羊是否在同岸
if(s[top].man!=s[top].sheep) ( F; h4 \# |) q
return 0;, i- T P3 O; E
s[top].sheep=s[top].man=(s[top].man==1)?0:1;$ C- H4 L, H' L7 ]" Z5 S
s[top].m=m;//存储过河方法0 S$ ^" b6 X$ ^+ _- g& l$ q
break;' ?( { @* a: S
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;
s[top].cabbage=s[top].man=(s[top].man==1)?0:1;* J' i5 B& Z3 D) i# _9 j$ g7 _
s[top].m=m;//存储过河方法
break;) i8 E. i# \1 M: {
//人单独过河
case 4:
s[top].man=(s[top].man==1)?0:1;
s[top].m=m;//存储过河方法: K) f& k3 C( x* O6 t. _. N, `, @
break;' ^+ T. `( L# A* S
}//switch7 W! F" w8 m0 M! Y4 H9 O+ P/ t
return 1;
}//move
//打印过河步骤
void display(int top); B6 N/ R* D9 ]- X6 ]% O
{' j: y% U7 Y3 O0 y6 O8 z6 m( j
int i=0;% b, A. Q; g3 D ^" y
fprintf(fp,"state%d: man: %d, sheep: %d,wolf: %d,cabbage: %d\n",i,s.man,s.sheep,s.wolf,s.cabbage);5 s$ v4 g/ h3 t+ ~ w) Q
for(i=1;i<=top;i++)
{0 A, x7 ~3 ?5 z& ]
switch(s.m)
{
case 1:. h$ [$ {2 B1 N2 @, }! M; D9 Q+ _; Y
if(s.man==1&&s[i-1].man==0)
fprintf(fp,"人带羊从起始岸过河到目的岸\n");' n$ j+ d& K( h% q( }* L* U
else4 l9 g. L% f, v4 s- }% H
fprintf(fp,"人带羊从目的岸过河到起始岸\n");& v M0 F- z9 N* u
break;) F/ D- d+ }9 @; G7 U. B& H
case 2:6 s1 T/ ~1 o$ a! J) K; `" O) n' F' [
if(s.man==1&&s[i-1].man==0)
fprintf(fp,"人带狼从起始岸过河到目的岸\n");5 `" d2 W7 \# B. K
else
fprintf(fp,"人带狼从目的岸过河到起始岸\n");: n3 Z. _0 _* X+ e
break;
case 3:6 m2 x- a$ L# ~/ w
if(s.man==1&&s[i-1].man==0)7 M: m: u$ S- v
fprintf(fp,"人带菜从起始岸过河到目的岸\n");
else0 X3 [* q* D, @; W$ e+ }
fprintf(fp,"人带菜从目的岸过河到起始岸\n");
break;
case 4:3 f: O+ E. Q2 G5 a& d4 |
if(s.man==1&&s[i-1].man==0)* p F# o G6 Q9 r) \3 i$ R' ]. v
fprintf(fp,"人单独从起始岸过河到目的岸\n");
else
fprintf(fp,"人单独从目的岸过河到起始岸\n");5 G' V+ V, y$ O0 T+ 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);6 E7 w! n+ i- z. ]0 J
}//for. z8 M2 P; r$ j" ^7 X
fprintf(fp,"All ferried successfully!\n");$ w8 D7 a2 D8 R, N# H; i7 {
}//display
//检查两岸合法性已经有无状态与历史重复性
int check(int top)
{4 \- `& q/ j( O& ]7 H8 f' {4 I
int i;
//检查两岸合法性
if((s[top].sheep!=s[top].man&&s[top].cabbage!=s[top].man)||% y" I5 ^) H" A7 n1 L9 w- H
(s[top].wolf!=s[top].man&&s[top].sheep!=s[top].man))
return 0;: |7 W% c' ?/ _2 g5 r" E
//检查历史重复性1 c l8 {. s1 \, J
for(i=0;i<top;i++). E& j5 ^9 ~) _ _) r
if(s.man==s[top].man&&s.sheep==s[top].sheep&&s.cabbage==s[top].cabbage&&s.wolf==s[top].wolf)
return 0;
//ok1 ]2 A( }2 ?4 _7 N3 k' D C6 w
return 1;" A) l& ^. c1 Y3 Y [ T
}, A# L* C% ], v( E% ~" Q
void f1(int top)1 M; g8 o1 ?- e' F/ ^+ e2 i
{
int m;
if(top>0)//0状态(初试状态应该是预先设置好的，所以要做状态1，故，初试top进来应该是1
{ //对每次状态分别试探4中方案
for(m=1;m<5;m++)
{" W* m5 q4 z0 X( z/ r
//每次方案的实施是在上次结果状态上做的
s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep;6 r5 }" t' z8 p0 x
s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf;
//用方案m移动，同时检查结果
if(move(top,m)&&check(top))+ A! u6 Y2 `2 u
{
if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf )
{1 x2 {4 A( n' u: y6 A9 _+ i6 x o. ^; j
//打印渡河步骤
display(top);3 U O7 |% `$ T* C1 F9 D- O+ H8 \6 k
//统计方案个数
count++; : s) h- V' m# [* A7 F
fprintf(fp,"count=%d----------------------------\n\n",count);
if(count>1000) exit(1);6 \9 Q$ w! }# t; r# Y3 j! N' l1 ~
}
else
f1(top+1);9 u: @$ t5 N) `5 C
}% V/ h: J6 C# n! H
}//for
}//if(top>=0)
}//f1
! L1 s1 Q7 u: `
O8 w) L5 D7 V. ^! k- Q1 z void f2(). Q) Y9 g' W2 P: g. Z9 I/ T. K* i {& _1 d. Q( b0 ?2 N int top=0,i;" a& Z$ F/ |$ l //开始时都在起始岸 s[top].man=s[top].sheep=s[top].wolf=s[top].cabbage=0; //未开始渡河 s[top].m=4; ]7 X0 F5 g! U while(top>=0) {6 }! _) W# q, Y4 h! `2 M& S! H if(check(top))7 N& ?8 a" `" t; H$ c { if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf )+ Z& E7 }: p) A6 w2 ? {1 j) W0 W5 p+ q5 b* [ //打印渡河步骤 display(top);7 M% v5 f7 d% @, U% T //统计方案个数 count++; , a9 @/ u! i, ~& D! Z L fprintf(fp,"count=%d----------------------------\n\n",count);. U) E" H8 X* Q* N if(count>1000) exit(1);4 k8 D, E1 ]* e u6 M; k //回溯 while(top>=0&&s[top].m>=4) / ]3 b7 D0 }* d# a8 F% A top--; if(top>=0) {, X; ^5 O1 c' ~9 @3 x //在上次状态基础上准备做move$ E- }" l; C' D" p3 y1 W 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; L" h3 S5 h& K2 N: Z i=1;1 T- ?& E, Y* G! T' O& j while(s[top].m+i<5&&!move(top,s[top].m+i)) i++; }
}. U; p& k. R; q% a7 b' j: k9 c/ ~ else { top++;: J/ z. E- H' p( { //在上次状态基础上准备做move7 H9 e1 f7 i( Y- e% l. V6 _* L1 V s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep;7 v0 A4 \$ N' B/ p5 @# J s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf;; U2 X8 L3 H* ^, I5 N i=1;) A) Y0 L% f7 |4 l. }5 | while(i<5&&!move(top,i)) i++;$ _/ \! j7 W8 u5 r% V }
0 @& s/ j3 R6 F- J! r} else {: M5 J. K8 S) z9 c v0 T8 N0 U4 ~5 ] //回溯 while(top>=0&&s[top].m>=4) top--; if(top>=0)! v; j7 K9 }4 d3 x1 [! }+ q {$ n0 c* j+ ]7 s9 s //在上次状态基础上准备做move s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep;0 k! {- g. A, i4 D- W s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf;/ y: L' L7 l# P' G" n$ i i=1; while(!move(top,s[top].m+i)) i++;' G5 w. }( T9 \- I& Q% e. j } }$ }$ L A' D& ?# d0 {; t7 f; z }//while) R: |2 v" r3 [9 t! Z) f' I$ r }//f2) a& L7 m) C; { C# l //---------------------------------2 c, G* @) K* z7 g
| 欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) | Powered by Discuz! X2.5 |