渡河问题
8 t6 g/ W1 a0 WA 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?
' s0 J% L* S& _+ r) y
程序代码：
//以下程序在Win98＋vc6.0运行通过
#include <stdio.h>
#include <stdlib.h>
#define MAX 50 K% k" R% ^6 _3 F: ]: o
struct state+ f& e2 ^( l* K7 [( U/ R3 b; r: K
{: I, D- j p' a& B. N! t; A$ Z/ l
int man,sheep,wolf,cabbage;//0:在起始岸；1：在目的岸 O% [: j/ }9 A# Z
int m;//所采取的过河方法，(1--4)8 U: U. P9 o; `% |7 ]5 _
}s[MAX];# x+ |! N1 p; l
int count=0;
FILE *fp=fopen("c:\\2.txt","w+");
void main()
{
void f1(int ),f2();//f1试探递归7 f& K* D: t& E* l C7 p
s[0].man=s[0].sheep=s[0].wolf=s[0].cabbage=0;
s[0].m=4; \4 Q2 v. D, _6 x" _4 M
s[1].man=s[1].sheep=s[1].wolf=s[1].cabbage=0;4 e/ ^2 N( Z8 e: I4 g( q
f1(1);
//f2();7 B5 O- ^6 C; M: t' _1 m2 W
fclose(fp);/ z$ ~: J. u! P. Q9 C) l2 E4 ~
printf("\n");
}: Q/ E( O1 ^2 Q1 E2 l! m$ f
//用m值决定的方法渡河，成功返回1,否则返回0, ?$ \! q- i/ Y2 {. X- x
int move(int top,int m)
{
switch(m)9 ~1 ? w. Y. D4 j7 V4 N+ W
{
//人带羊过河! z: k6 D" y! ?2 t
case 1: 8 B( ^: g ]. H8 [3 a9 P+ Z. x
//判断人羊是否在同岸
if(s[top].man!=s[top].sheep)
return 0;5 b4 b& \0 a6 A6 }
s[top].sheep=s[top].man=(s[top].man==1)?0:1;
s[top].m=m;//存储过河方法
break;
case 2:( n( G' ` t( |( E& p# J
if(s[top].man!=s[top].wolf)
return 0;9 X/ o& u4 {% H- p" C5 ?+ A
s[top].wolf=s[top].man=(s[top].man==1)?0:1;
s[top].m=m;//存储过河方法
break;
case 3:2 }, q" W* ]4 w. J( J; m
if(s[top].man!=s[top].cabbage)$ Y9 |( w* j# ^! B. Q: J2 l
return 0;. i4 q+ M2 ^/ i
s[top].cabbage=s[top].man=(s[top].man==1)?0:1;
s[top].m=m;//存储过河方法
break;/ j" V3 W, V" E" A
//人单独过河
case 4:
s[top].man=(s[top].man==1)?0:1;
s[top].m=m;//存储过河方法
break;
}//switch( H7 m& b$ y- W: t: [
return 1;# I+ x2 B! ?8 H4 m. l! s
}//move
//打印过河步骤
void display(int top). U$ {3 g8 v7 \# `' ~9 I
{
int i=0;' V+ @2 E0 O' f$ S
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++)6 ?! B: D' [* d; F
{
switch(s.m)
{
case 1:
if(s.man==1&&s[i-1].man==0)7 B; X' v) N/ P
fprintf(fp,"人带羊从起始岸过河到目的岸\n");
else
fprintf(fp,"人带羊从目的岸过河到起始岸\n");
break;
case 2:
if(s.man==1&&s[i-1].man==0)/ ~, c. W e& a$ o
fprintf(fp,"人带狼从起始岸过河到目的岸\n");
else
fprintf(fp,"人带狼从目的岸过河到起始岸\n");
break;
case 3:
if(s.man==1&&s[i-1].man==0)
fprintf(fp,"人带菜从起始岸过河到目的岸\n");
else& L: z) }( U% i; M
fprintf(fp,"人带菜从目的岸过河到起始岸\n");3 h* h. I! _/ r$ `$ l
break;
case 4:
if(s.man==1&&s[i-1].man==0)! f: R( g# s) ^6 G6 d' b
fprintf(fp,"人单独从起始岸过河到目的岸\n");3 V" ?3 E7 P! c: _
else
fprintf(fp,"人单独从目的岸过河到起始岸\n");9 O$ d* H/ ], v; t7 X6 H
break;. w6 q$ m" k$ k6 t5 d# D/ y
}//switch& L: I6 E D, d) n; j
fprintf(fp,"state%d: man: %d, sheep: %d,wolf: %d,cabbage: %d\n",i,s.man,s.sheep,s.wolf,s.cabbage);
; {/ F& Y2 F* e' K. y9 u! N
}//for/ F: X# V; a; w' b: r; L6 X! K
fprintf(fp,"All ferried successfully!\n");
}//display
//检查两岸合法性已经有无状态与历史重复性
int check(int top)
{
int i;
//检查两岸合法性" L& o+ ~9 P- t, }0 W2 P; G
if((s[top].sheep!=s[top].man&&s[top].cabbage!=s[top].man)||2 N) S4 ]/ `; F! X6 ]# q9 V
(s[top].wolf!=s[top].man&&s[top].sheep!=s[top].man))# x4 |* a/ z' T9 F- H- K9 S" ]7 q2 @
return 0;
//检查历史重复性
for(i=0;i<top;i++). M7 w4 b; g- K! E/ k
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;7 b9 F' _7 h$ U+ i- t
}& y( R) \; z+ Y* h* }4 K! o" a: n
void f1(int top)0 Z d* n: C0 G9 {) P" Q
{+ _8 G3 N2 {% {9 e9 [* o$ R
int m;, \( n; q+ d0 l9 c6 \% c8 N
if(top>0)//0状态(初试状态应该是预先设置好的，所以要做状态1，故，初试top进来应该是1( F4 k4 ~) y* E" |5 U% m
{ //对每次状态分别试探4中方案
for(m=1;m<5;m++)/ c3 S& z' z0 e
{
//每次方案的实施是在上次结果状态上做的( Q' o/ ?, F1 ^- S+ r4 ]! ?
s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep;+ G! J, C, J& |4 F+ j" K) B
s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf;
//用方案m移动，同时检查结果
if(move(top,m)&&check(top))
{7 L, t" _' d9 i( W. ^
if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf )4 Z8 G+ ?! a+ r1 [* _7 y* Z- w
{) @( t' e9 w7 X3 i) @
//打印渡河步骤/ W a G& @ ?& D' b! A, R4 ]
display(top);
//统计方案个数9 n G& t U, M: E
count++;
fprintf(fp,"count=%d----------------------------\n\n",count);8 n$ f# \4 v) u) `8 ^, [# x
if(count>1000) exit(1);
}* F8 X1 K4 k2 ~2 E
else
f1(top+1);
}; u% R' w/ ^. G: u) E* d6 A
}//for
}//if(top>=0)
}//f1
) F% W$ q0 I- Y `
/ ?6 u4 F5 F+ \: d& c. K
% z- w0 y. z3 i void f2()2 n! w6 z9 @4 [- g n { int top=0,i; //开始时都在起始岸/ Q4 B* n4 d' B( L, V s[top].man=s[top].sheep=s[top].wolf=s[top].cabbage=0;" \1 ^0 y1 D5 x, V' P' y //未开始渡河 s[top].m=4;- v+ k; I& h; X$ K: l; j! y6 T while(top>=0) { if(check(top)) { if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf ) {4 j$ ?* A' W3 z) e //打印渡河步骤 display(top); //统计方案个数 count++; 4 u" m- s3 X% A: N fprintf(fp,"count=%d----------------------------\n\n",count);! f* U$ H x r) p- {3 m" Y if(count>1000) exit(1); //回溯% h o; x; W# S0 p z while(top>=0&&s[top].m>=4) + k. P0 {/ ~$ V9 W2 d2 u6 F3 t, ?' @ top--; if(top>=0) { //在上次状态基础上准备做move* O2 v0 Q* R- g' \ s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep;4 Q. \, f; o4 S) }5 ?5 N- C s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf; i=1;/ A$ j9 s ^6 A# W0 I9 [$ C while(s[top].m+i<5&&!move(top,s[top].m+i)) i++; }
} else7 K' W* m1 [- [( a {6 z0 q7 N7 R6 n. d8 g2 |6 Z6 X top++; //在上次状态基础上准备做move2 y; e/ i% U7 O' A; N8 p2 `% d' f 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;) l% F. o, }8 w: i while(i<5&&!move(top,i)) i++;' J4 Y+ N6 m$ j4 m2 h }
} else {2 U- u8 s/ _3 p J* Z' ` //回溯' p- l# s9 w" q* q( T( B/ P while(top>=0&&s[top].m>=4) top--; if(top>=0), }1 E4 V8 T8 ^9 T! g6 I$ o { //在上次状态基础上准备做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; while(!move(top,s[top].m+i)) d! j0 M, a; q# t j i++;. M1 A3 _0 u: {) z4 C9 x }3 C4 R* a9 l. J& T: m }/ D6 P. |5 f+ }" t* O& ?0 y: w }//while4 a' R7 C3 k4 t! a& b& c. ? }//f2 //---------------------------------
| 欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) | Powered by Discuz! X2.5 |