QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 7751|回复: 4
打印 上一主题 下一主题

渡河问题

[复制链接]
字体大小: 正常 放大
sally        

10

主题

1

听众

95

积分

升级  94.74%

该用户从未签到

网络挑战赛参赛者

新人进步奖

跳转到指定楼层
1#
发表于 2004-6-5 11:57 |只看该作者 |倒序浏览
|招呼Ta 关注Ta

渡河问题

) P# a$ i7 T' E; B

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?

0 H* Q- @9 }2 k& v

' I/ B: o5 S! s5 f# T& n- e

程序代码:

5 k# j$ W& b. e3 o

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

2 g2 |5 {7 L/ D4 t7 X' @) g

#include <stdio.h>/ j6 c9 x# {* `# M9 g) R #include <stdlib.h>! o/ M/ ]. ^. ~0 o* ?8 o z! g #define MAX 50 8 R" H) _2 l8 `# J l7 k2 Estruct state 0 {/ Z+ Q8 X8 h: h: a# ^{. I& O0 h. f1 L1 N int man,sheep,wolf,cabbage;//0:在起始岸;1:在目的岸8 c2 P6 q/ F% V( E int m;//所采取的过河方法,(1--4) ; {% ~2 i+ y: |}s[MAX];6 n% V2 }2 r X3 |* | int count=0; 5 n7 Y. _( |# `4 V8 ^( N+ VFILE *fp=fopen("c:\\2.txt","w+");

$ P) B0 U6 R0 S) Y

void main()4 [) G0 F% d, e9 @ { 3 r0 k: B* l9 ?' ] void f1(int ),f2();//f1试探递归 # v6 F0 f/ X2 |, R s[0].man=s[0].sheep=s[0].wolf=s[0].cabbage=0;8 O$ T# m) t/ v* e }8 D s[0].m=4; - y, r. u# t- k I' K0 b' i2 K s[1].man=s[1].sheep=s[1].wolf=s[1].cabbage=0; 6 G$ D6 p# N! b$ N f1(1);" q( j+ P/ j; |/ l* { //f2();. v7 D+ |+ \, z7 _ fclose(fp);7 Q0 ~0 w+ @& ~& w printf("\n");

o2 y$ C: a+ u/ \& ]6 `. j( q I

} 8 g) Q/ H0 l, j; m$ ?: ]- N7 T0 z//用m值决定的方法渡河,成功返回1,否则返回0" e6 Q7 |0 B4 H# ? int move(int top,int m), P5 U& H: p& C4 ]( h% ^6 X {. \, v. w h; \. M switch(m)- r' Y4 L& S J, c. f, A1 F, \7 L. y* f { # \2 n1 L* Q" v, _& Q //人带羊过河 C% J! n7 k& e5 Y [, G$ _4 | case 1: & T' T; Z( i7 C* w! L# V //判断人羊是否在同岸! H9 @) T3 H; s) I if(s[top].man!=s[top].sheep) ( t8 J! n* m3 p# h% C, \8 @ return 0;4 [) x& ~! o- G0 ]1 f. y' q s[top].sheep=s[top].man=(s[top].man==1)?0:1; $ Z4 r/ F4 M2 D+ ]0 G s[top].m=m;//存储过河方法 - L1 O Y @: u: p8 O break;, e ^3 S0 b8 w9 p case 2:' q3 n/ k. }6 t; t& l9 |! ?# { if(s[top].man!=s[top].wolf)) S+ \6 G n' g5 A% ^' f return 0;& D" O$ V3 {/ i* s, c2 [ s[top].wolf=s[top].man=(s[top].man==1)?0:1; / x3 i5 ~! l5 W# Q m0 J; @ s[top].m=m;//存储过河方法0 O6 W/ p# Q- E5 L break; 0 x: A$ G E& u2 ?* n4 g3 m case 3: # j9 x, _, S. `! F! F if(s[top].man!=s[top].cabbage)# i g' {) J* s, n$ n3 ?" {; z return 0;! v/ ~8 n4 D7 D/ D1 @5 \ s[top].cabbage=s[top].man=(s[top].man==1)?0:1;" O0 l# |, K2 y s[top].m=m;//存储过河方法 9 G! p& y, ]' X8 h# g break; " r: D( p/ x2 | //人单独过河3 @9 r# L p! o7 v8 }. W& x& v# t case 4:& f( d9 Y2 A( o8 ]/ C8 W; M y s[top].man=(s[top].man==1)?0:1; " H P& K+ D- y# H& s x; I s[top].m=m;//存储过河方法, O8 E |- Q5 i$ f, @2 c9 d" N) d break;3 a9 d3 \2 x& Y, I& P$ [! M9 n* u9 _ }//switch , P% ?" I0 S- g+ ` return 1; , y( N# o9 I3 o}//move / t7 ?/ K* f9 ]! }0 X//打印过河步骤 " I" e3 \# R0 I" ?7 r1 u2 z7 ^# yvoid display(int top)) E$ s* x U' f( m {" q+ P) n5 y9 c: Z$ e8 ^ int i=0;5 f9 Z: ?5 J6 f3 T m6 Z6 z5 g fprintf(fp,"state%d: man: %d, sheep: %d,wolf: %d,cabbage: %d\n",i,s.man,s.sheep,s.wolf,s.cabbage);: {: N2 T w2 i for(i=1;i<=top;i++)% B8 `2 J+ I/ O# w' ~ {; {, ?5 Q7 y/ r: {( S+ Y switch(s.m)+ S2 F4 T3 o$ i/ B5 K0 w {9 Y& \" ?! q, @4 Z; K; R case 1:3 C* @! X r% b* ? if(s.man==1&&s[i-1].man==0) ( z: P, m( }1 H) T: Q fprintf(fp,"人带羊从起始岸过河到目的岸\n");! k: ^& K: o+ o% S else " F1 o8 x) F- H8 `' Q fprintf(fp,"人带羊从目的岸过河到起始岸\n"); 9 n' t) m" }# E3 t break; . y1 _% y' ~7 S& u7 \& C" ] case 2: 7 u+ s( E n- K0 A7 k6 n2 @ if(s.man==1&&s[i-1].man==0)- V0 ~0 `( w9 Y5 R- B2 x! B; k$ ` fprintf(fp,"人带狼从起始岸过河到目的岸\n"); ) k. o0 f6 i# K5 c else3 A. d$ t3 r/ X O% P fprintf(fp,"人带狼从目的岸过河到起始岸\n"); 0 b5 q7 c6 M5 d0 y" m$ c break;1 l4 \& r# v) g) X case 3:( c; s( m2 h& X# Z" Q, } if(s.man==1&&s[i-1].man==0) 5 Q1 V% A! ?! E; s fprintf(fp,"人带菜从起始岸过河到目的岸\n");; Y8 a, F7 m! q4 v8 R( e else 7 p' Q: Y( ~, N i( J+ V a. r/ u fprintf(fp,"人带菜从目的岸过河到起始岸\n");- r' t! V; `8 U2 r# ]& Q( d break;" P3 P, V: G/ T) }0 d case 4:5 f# g U7 h* Y6 \& J) ? if(s.man==1&&s[i-1].man==0)& c6 b7 L% A: d fprintf(fp,"人单独从起始岸过河到目的岸\n");1 ]3 O! w K/ a* n else 7 a7 A' K* s) W1 t# t# N4 g7 x fprintf(fp,"人单独从目的岸过河到起始岸\n"); 9 L) U5 I3 m/ R- X3 y2 F1 G5 q break; / o, Y3 h R$ V4 } }//switch 9 [0 z- d. X# \' Y; N, h fprintf(fp,"state%d: man: %d, sheep: %d,wolf: %d,cabbage: %d\n",i,s.man,s.sheep,s.wolf,s.cabbage);1 W( S L2 `6 ] k . K, \* Y6 H7 G$ i! H! \7 d) m }//for; p% Q0 w) x& O" \7 A fprintf(fp,"All ferried successfully!\n");- W# m) ]8 N. f. t6 B8 j }//display

; W$ a" f# i6 q

//检查两岸合法性已经有无状态与历史重复性 q% R! j1 z" s/ R6 [- p+ U, V- s0 Aint check(int top) 9 Q1 `% h1 c7 o x{ 8 r7 F P. g; P int i; 1 r4 h* k& d/ t7 t$ O//检查两岸合法性- Y* o5 c( G% D% t- f- T& T/ g if((s[top].sheep!=s[top].man&&s[top].cabbage!=s[top].man)|| 4 B1 o {0 _' y* X- t& w (s[top].wolf!=s[top].man&&s[top].sheep!=s[top].man))0 r, u- c3 P. o* j* l return 0;: B( p; l2 d& P6 N) P7 m //检查历史重复性8 n! U: z4 E' L for(i=0;i<top;i++)% Q; x, W$ A; F/ T) y* B/ C if(s.man==s[top].man&&s.sheep==s[top].sheep&&s.cabbage==s[top].cabbage&&s.wolf==s[top].wolf)4 H5 ^# _2 V. g" I8 D! v% z return 0;8 P, f9 s, L7 [5 @ //ok* W; p( B! b: ^9 Y( ] return 1;: s& \( ?8 u$ c3 {! l; W0 |0 L }7 ]" T. K1 U ]5 S void f1(int top)" R* @& K( |! y3 j" c5 r( b { . D% }6 K& l0 @2 N% G0 N+ g int m; % m+ _3 ~9 K" ` if(top>0)//0状态(初试状态应该是预先设置好的,所以要做状态1,故,初试top进来应该是12 w: {- Q) L# a8 ^6 ? { //对每次状态分别试探4中方案 + h* X3 V0 j8 ?, v2 r$ ? for(m=1;m<5;m++) % l7 G. ?! J# [& O {* z3 F- p! L' J //每次方案的实施是在上次结果状态上做的 2 `$ K6 C! m9 S5 w# f7 B s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; + ^, d1 u; H) O5 h- L s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf; 8 y- g* m4 \. H2 Y //用方案m移动,同时检查结果 / ^1 @; I. ^5 E$ x) \, M4 J9 v if(move(top,m)&&check(top)) f. ^1 T, Z' W4 ]( d9 S( | { * N2 |! q7 }( \ C if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf )( T2 c- Q/ g" M8 D( L. t {6 I3 D7 W3 Z. ?8 C- G' m' m //打印渡河步骤, y$ ?8 H. x7 |4 S1 h' N+ v) L display(top); ) _$ l/ c6 n9 o& Y% E: s //统计方案个数8 d3 w$ v; h" z- {+ R count++; 3 V w* ~8 Z) X6 h0 w0 q. J2 O fprintf(fp,"count=%d----------------------------\n\n",count);4 y# w5 k) O0 K; P if(count>1000) exit(1);+ u2 E3 d8 e$ R ? } : y: W; N! ?0 ^0 u else 7 O, P# s5 X( B5 I4 e f1(top+1); 0 W! p1 z6 t# T1 Q' S! { }& \7 J7 V: h/ n; O6 W5 d) d5 m }//for 3 k3 @# u, A: k& G }//if(top>=0)" t9 Y; R: M3 T }//f1

0 b f; [# `6 d

: ?' p4 m& y+ p3 s7 _) T1 T

7 Q# J% ]2 x+ F5 o, G; `: m1 J

/ i$ h4 R. g1 N- \void f2() $ M" T& N, V+ `{3 q7 m" P8 @* M int top=0,i;/ v$ S: k+ C5 y/ S6 ~1 X4 ] K& S //开始时都在起始岸0 o( d# W/ n7 v- s s[top].man=s[top].sheep=s[top].wolf=s[top].cabbage=0; ) L3 j; M% J: R6 Q# F5 Z! D) c //未开始渡河 6 g( n1 ~, c. J, K s[top].m=4; - E% A4 p4 A/ B, l while(top>=0); X* r5 A% B. N { Q; ^% n: R: s8 y if(check(top)) / X) u# m4 r, j$ l {) z: R. |4 q- Y T, \ if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf )! f% j. c# a$ ^4 G" D { & s$ \) w2 B8 b! p //打印渡河步骤9 u9 j4 R7 G0 Z/ D- h$ D display(top); 8 ]) A2 `2 G3 j/ A4 w- ~: S h' B; I) u //统计方案个数# A4 W+ b! m; t3 e& N3 s' { count++; 4 I0 s! [2 y, V fprintf(fp,"count=%d----------------------------\n\n",count);% ^# ~* v. S+ n8 M if(count>1000) exit(1);4 Y; H( a$ X! W7 M4 U( E/ e //回溯! h$ T# F7 u8 W; Q while(top>=0&&s[top].m>=4) 1 i+ E7 S4 W$ K$ _ ^. U top--; _4 ]0 v: k& G9 i if(top>=0)9 Y8 v! @. z: s5 n {% O/ }0 ?, f5 N) b% Y# T5 a //在上次状态基础上准备做move- g% b+ U/ _- y3 U# F7 ~ s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; . i% I7 \# h: D s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf;/ X2 z @2 G7 T: ]/ M% _' [ i=1;6 J# M& w! W4 L) R. ? while(s[top].m+i<5&&!move(top,s[top].m+i)); X6 B6 y/ V" c* u i++; 3 R7 w+ ?) S3 Z* _" @ }

* b1 [; I( F+ B% \% i" z

}! v/ g) `! ~( g' c) S% d else $ U0 m0 K5 f% n6 \0 j { . P5 f s9 L5 `1 k# K- D2 c3 J" Z& ] top++;3 b1 x- s# O# O" b# d0 T$ G) V- K' | //在上次状态基础上准备做move: u* u, Z3 q5 n s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; 2 M. W. z- v$ v0 x6 C s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf;* b0 t! _ `( f* t3 z" } i=1; ' H6 o/ e& n4 x/ h1 T% t; g while(i<5&&!move(top,i)) ! Q6 a' F. X) k! Q i++;& F8 }/ Y# e* z: p }

5 [# r) C9 X) K2 m

}* J* ~1 O# C2 A5 M) d( `7 Z else 7 ?$ q7 n `" t; o7 [, ?# R( O( R { / ^. M5 y4 W. g0 E //回溯 8 F3 a3 y/ R) E* w while(top>=0&&s[top].m>=4) , x6 ?, _, l0 j' c' o* h/ f) H top--;. c% x- s/ K/ V! N: v5 R4 e+ ` if(top>=0) 8 B3 {3 \) j1 e- [ {- g3 W% S3 @3 C6 P$ ~0 @4 ^" P2 w5 O //在上次状态基础上准备做move* q+ S" |+ v& h$ F s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep;8 Q9 J7 X% ~* \ M4 W" d% K2 o s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf; ; k8 M) u0 r2 k: a' S' q i=1; ) z7 j! q5 u) I2 X while(!move(top,s[top].m+i)) / J. F, O8 r; P( e i++;# e% K$ l V! W! G }4 V+ y/ E7 z1 h9 h } ( j6 V: |% B% Q+ t }//while4 W3 a2 I4 |) B- h }//f2# ]6 E" |: G& L' H' s. W$ M: O //---------------------------------6 t3 b$ r/ R2 M& X

zan
转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
阳光总在风雨后
sally        

10

主题

1

听众

95

积分

升级  94.74%

该用户从未签到

网络挑战赛参赛者

新人进步奖

回复

使用道具 举报

1253

主题

442

听众

-586

积分

复兴中华数学头子

  • TA的每日心情
    开心
    2011-9-26 17:31
  • 签到天数: 3 天

    [LV.2]偶尔看看I

    自我介绍
    数学中国网站(www.madio.cn)是目前中国最大的数学建模交流社区

    邮箱绑定达人 优秀斑竹奖 发帖功臣 元老勋章 新人进步奖 原创写作奖 最具活力勋章 风雨历程奖

    群组越狱吧

    群组湖南工业大学数学建模同盟会

    群组四川农业大学数学建模协会

    群组重庆交通大学数学建模协会

    群组中国矿业大学数学建模协会

    回复

    使用道具 举报

    lynn324        

    1

    主题

    2

    听众

    40

    积分

    升级  36.84%

    该用户从未签到

    国际赛参赛者

    新人进步奖

    回复

    使用道具 举报

    mnpfc 实名认证      会长俱乐部认证 

    131

    主题

    38

    听众

    1万

    积分

    升级  0%

  • TA的每日心情
    开心
    2018-12-4 08:49
  • 签到天数: 282 天

    [LV.8]以坛为家I

    邮箱绑定达人 新人进步奖 最具活力勋章 风雨历程奖 元老勋章

    群组2010MCM

    群组数学建模

    群组中国矿业大学数学建模协会

    群组华中师大数模协会

    群组Mathematica研究小组

    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2026-5-2 13:03 , Processed in 0.394788 second(s), 74 queries .

    回顶部