QQ登录

只需要一步,快速开始

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

渡河问题

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

10

主题

1

听众

95

积分

升级  94.74%

该用户从未签到

网络挑战赛参赛者

新人进步奖

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

渡河问题

, \% v; s% V) n# ]5 F9 @5 E2 c- ^

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?

1 E* ~" p' g0 Y6 A$ t, T9 g9 Y

& V S1 S7 Q& X) T

程序代码:

! ?% c+ M" e- c' d- e

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

3 f. v# R3 e8 M. x T

#include <stdio.h>6 s, f: C2 _* e0 \& `. h, a+ o8 K #include <stdlib.h>& E1 P+ V; l8 R/ d #define MAX 50 8 y+ h- q! J: Z$ R. {struct state# G( C& b+ d2 @5 d+ c! z { _9 Q$ ^" g n% O int man,sheep,wolf,cabbage;//0:在起始岸;1:在目的岸! {: @( v1 {# R. ` f int m;//所采取的过河方法,(1--4) ! G; ?8 r3 } I: s5 c* J# @6 X}s[MAX]; 0 H6 U4 A2 O) ?5 xint count=0;. F5 w3 v0 v+ J$ V N FILE *fp=fopen("c:\\2.txt","w+");

& H. X) d0 ?- Q& s9 y x% a" g

void main() % o0 {. @9 M$ P: n1 f& L! V{4 K$ |' y- {. u; { void f1(int ),f2();//f1试探递归 ( j. \* A+ `' T. a$ b9 C0 ~% O s[0].man=s[0].sheep=s[0].wolf=s[0].cabbage=0; 4 f, O9 H. u4 [2 J9 P s[0].m=4; 5 q& E* y- o: e7 [) a s[1].man=s[1].sheep=s[1].wolf=s[1].cabbage=0;* w% u( K7 J- ] f1(1);) ]% F" |8 r5 S' r6 X //f2(); - {- l# L+ g2 B& G fclose(fp); : i1 l7 v, e* R9 n printf("\n");

, C8 [7 U5 J) {

} 8 q% Z! _4 |. |//用m值决定的方法渡河,成功返回1,否则返回04 A# R U7 c2 r8 \4 O% s int move(int top,int m)9 x; Y" r) K# E& X$ S6 w* B { % c$ L) @9 @) |. h3 u- ` switch(m) # S% ?7 L# e6 b5 J5 s { . e* H) \1 c0 v //人带羊过河3 Z8 ?7 F4 w( q* n case 1: + L: N8 f |+ O. z# {. D' ~ //判断人羊是否在同岸& u" C& g% d5 T+ _1 a# g- { if(s[top].man!=s[top].sheep) " }& o! N+ i: q/ y5 }+ t return 0;! e3 d; k3 Z" @, n5 V s[top].sheep=s[top].man=(s[top].man==1)?0:1;# j" v( m) M1 T8 P- j- k s[top].m=m;//存储过河方法3 o) J: u( _. V$ g j* c0 _3 d break; 6 f2 L; D$ H" x# k case 2: 9 }6 L. ~# B) C$ \6 u+ U if(s[top].man!=s[top].wolf)7 R! g& ?. D/ Y" I return 0; 4 r2 n& W! p) ` s[top].wolf=s[top].man=(s[top].man==1)?0:1;' y# k2 Y! X' f7 |9 j4 j$ H: W7 y s[top].m=m;//存储过河方法 , z# T4 _9 K) s- p break;4 i: `; \2 s7 |" _# _0 j3 K, h5 N case 3:7 a f& B5 H/ B+ t if(s[top].man!=s[top].cabbage) 4 S. q0 T" i4 ~ return 0; 2 M3 n" {1 v4 f) s& x ] s[top].cabbage=s[top].man=(s[top].man==1)?0:1; ) ]5 k, D5 g* Z( e4 _9 k s[top].m=m;//存储过河方法 / s7 M' H6 Q2 \3 R8 ] break;* V [( W V. T" Y4 o2 S+ G //人单独过河 % w# t' q2 h# W) A) e' G& \4 i, E% ]$ H& Z case 4: i0 A+ ]* P3 s. ^, w) i s[top].man=(s[top].man==1)?0:1;( t/ M" A6 r& z s[top].m=m;//存储过河方法 / [: h& F" C6 `) g4 \' J break;. x2 c% `8 t8 Q }//switch 7 ?( _; Y7 }" M0 J) h% x/ E return 1;# W0 ~& ~9 m9 m& j- | }//move9 l: p2 ~$ W; q9 L% R# G8 H) E //打印过河步骤 * I; W; V! J/ R# Jvoid display(int top): s6 Z! ^' s {, U! x$ w4 E! _ {3 a1 _1 w, h: f int i=0; / N: p. L9 A) ~' u. s! u% k/ g; [ fprintf(fp,"state%d: man: %d, sheep: %d,wolf: %d,cabbage: %d\n",i,s.man,s.sheep,s.wolf,s.cabbage); 0 Y; c+ |( m1 w! P5 o; o- j7 ? for(i=1;i<=top;i++) & ~8 F+ I8 u- h% v* l {' @- f: b0 m6 L switch(s.m)" D6 e7 z+ H1 j( K ^- w. A3 Y& U {3 v# k+ I6 D3 M- ~ case 1: ) `* q. h; d: l if(s.man==1&&s[i-1].man==0) a7 ^3 X& ]5 {; H% e fprintf(fp,"人带羊从起始岸过河到目的岸\n"); # Y y$ [) a- D: v0 s else z8 q: p: R& N9 A fprintf(fp,"人带羊从目的岸过河到起始岸\n");1 S, L" ~8 h# X# p break; ! E& C; t J7 X: I6 U5 Q" A case 2: 3 k; N" @, T2 f2 ?9 E- t [ if(s.man==1&&s[i-1].man==0) 3 w( \. W+ f3 E fprintf(fp,"人带狼从起始岸过河到目的岸\n"); & H% h6 N0 u0 t! @& j# f/ I ^) w else, ^) S/ A& U, m' } fprintf(fp,"人带狼从目的岸过河到起始岸\n"); 8 \7 X$ b! A y" z7 C5 G9 j break;8 b. E8 e) H( x7 c. K case 3:( t! c p. u/ b" U if(s.man==1&&s[i-1].man==0) 4 J# e& i, |" _# {2 S fprintf(fp,"人带菜从起始岸过河到目的岸\n");) k1 d! k2 w! L% h/ m$ x( X4 |0 F else) _( |" ~7 G8 d1 g fprintf(fp,"人带菜从目的岸过河到起始岸\n");8 d( \2 o8 V: x7 z* C) J2 j7 g break; # e+ O2 V, w* \ case 4: & ]2 d2 K# Y0 P9 m N. R if(s.man==1&&s[i-1].man==0)" \& ~2 O% D4 ?; {$ f! A' N fprintf(fp,"人单独从起始岸过河到目的岸\n"); ) O: x4 i: D4 h3 | else% x1 e/ A% G `; A2 n fprintf(fp,"人单独从目的岸过河到起始岸\n"); * y* A" y8 B& [+ H; X. P' O break;. ^7 S2 B0 p; f3 P! b6 w$ ^ K7 N }//switch : J0 ^2 P' T' I% b# y fprintf(fp,"state%d: man: %d, sheep: %d,wolf: %d,cabbage: %d\n",i,s.man,s.sheep,s.wolf,s.cabbage); 4 w' _! `2 o2 z- w9 T0 [ / t# ?; F5 h3 f i8 u) n! U }//for 1 ~ U7 l, W2 R+ e3 sfprintf(fp,"All ferried successfully!\n");% Y3 r: s$ x8 M' C. } }//display

6 S/ g7 C" E6 f# N

//检查两岸合法性已经有无状态与历史重复性 - F8 n/ G8 r' Tint check(int top). I$ g/ X+ X9 @ {! ^" r6 j. i- X5 J) C) x int i; ' \9 t6 h. g2 x//检查两岸合法性 . z! N6 l* M- C* W) V$ c& N4 } if((s[top].sheep!=s[top].man&&s[top].cabbage!=s[top].man)|| 6 K0 E! v: o6 w0 W (s[top].wolf!=s[top].man&&s[top].sheep!=s[top].man))% G6 V. r3 Q0 j1 _) y7 a0 G return 0; ( I6 w! a: ^ L6 G& C7 I/ g //检查历史重复性 8 G9 g- n; o, g L* k for(i=0;i<top;i++)* a5 E6 J. f: F) H if(s.man==s[top].man&&s.sheep==s[top].sheep&&s.cabbage==s[top].cabbage&&s.wolf==s[top].wolf)2 N. M( \0 h# M, N) j E8 R return 0;7 p, j, z- v8 b+ D8 L m D //ok [4 M* ?4 y* f# w3 v4 `1 E, L return 1;+ L9 O0 z2 s2 J4 l% |& Y } ( h8 x; O! E. g k. x Rvoid f1(int top) $ Y7 ~0 D6 w& B) L' w% a v{ , B: d9 C& _% s int m; , U; m$ w$ S5 }) m" e- [9 _& y if(top>0)//0状态(初试状态应该是预先设置好的,所以要做状态1,故,初试top进来应该是1# b. y4 |0 P' u { //对每次状态分别试探4中方案 9 }8 R- R, p( t* ]5 @ Z7 e' x for(m=1;m<5;m++)) a/ ?; B% i9 A6 {( _+ h1 \ {' B4 `4 z' e; j6 {9 @' X, D //每次方案的实施是在上次结果状态上做的 / `7 Z- P. ?6 z8 K+ G s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; ! Y: o6 L; _) C# [$ r s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf; % |! ~, I4 H: H8 v: z- d1 O, e& L //用方案m移动,同时检查结果6 @6 n3 ^! u0 F if(move(top,m)&&check(top))0 H& ]+ Q, h2 X; }$ y4 X1 K4 @3 q { 0 [2 k; H; e! q1 C) C if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf ) : D$ Y0 F7 r4 O; G; E+ e { 1 M. Z, I9 u9 r$ e2 ?* t //打印渡河步骤4 G& T. l" ?$ K. K display(top); / c8 x1 ^& v8 i7 n* J" I //统计方案个数& ]: T$ d' E# [/ a count++; - ]: f6 |+ o: c/ [ fprintf(fp,"count=%d----------------------------\n\n",count);& S) G& F( B- \. e* m9 X if(count>1000) exit(1);; H9 O; t+ h+ F6 B }$ ]) x7 q" I/ U( [1 [1 W0 u else # l0 D2 v! G; \2 L) J- N2 y( J$ v6 H f1(top+1); $ f( T) G8 c, E* y+ C8 Q2 v/ O0 K } - |( ^3 p' s+ J7 _6 t+ m6 f }//for & C+ z& r, r% V) x, }# G, H2 y! l }//if(top>=0); r* _0 G3 h% O" \ }//f1

" P; r* {. |6 m+ v+ r' f7 j

* K2 L$ e4 A5 O, }+ ]

2 r4 C4 F2 k* [) C$ t+ \! e

z7 A( |6 C! [# A0 \ void f2()5 n& p/ u, ~1 v7 V G& H { 0 m8 O4 {7 h% r* D6 O& j int top=0,i;; y" M6 c" s& g //开始时都在起始岸! J8 i% C6 I! ~% W& a- o s[top].man=s[top].sheep=s[top].wolf=s[top].cabbage=0; * c# a% R9 V% _4 s) Y" a, d; [ //未开始渡河 & g: s/ e/ V7 g. m4 D6 t1 l% H s[top].m=4;+ `" h- F4 V6 k# i while(top>=0)- F5 ^* S( k' A {9 h) j( ]( Y* m3 F$ { if(check(top))' P8 \* O9 |& Z& Y {9 L/ Z8 B$ S' k/ z2 l if(s[top].man&&s[top].sheep&&s[top].cabbage&&s[top].wolf )4 ^; I! H2 C: K( q+ B" Y* a7 k3 D {/ ~6 w r( h3 ]3 u" ~ //打印渡河步骤8 W3 e* k7 L2 P# T% F: c display(top);; D9 g' m1 G" z* ^4 [, k6 ^ //统计方案个数* \4 B4 \. j0 ^4 m2 G; O& B count++; 7 N: Q* m; c4 H& }3 ^ fprintf(fp,"count=%d----------------------------\n\n",count);4 A, \/ Z5 u( m" e2 S7 O- E6 \ if(count>1000) exit(1); ( M: \# X# J# W/ i //回溯 , F6 t# `. l' @5 a) |% D' [9 | while(top>=0&&s[top].m>=4) % n( P5 C; z3 @: f% V top--; 1 `( d) N0 d+ f8 q7 M: ^ if(top>=0)+ z: @+ {0 t( V8 ? {- i7 q, I: Q9 a/ |! C3 i, ~ //在上次状态基础上准备做move- P+ W6 `0 I: i3 S8 O. \2 ] s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; # o* x0 g/ `0 c! r# E+ [ s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf;- ?) O- Y5 W; }) N8 @( O/ F i=1;* P3 J7 C/ S `0 W/ L( g# R while(s[top].m+i<5&&!move(top,s[top].m+i))1 @5 t! F0 P* z2 S/ G8 W4 R/ G i++; , ^1 A) Z6 h# @$ f }

. ^0 W. _: o+ [: e

} - }* ~4 f' L2 ]( t6 S else 3 O1 G9 u9 x1 y1 u! e3 j! ] {: ~6 [7 @: [4 K3 F( \% q top++; ' R% x* K) |( ]( x //在上次状态基础上准备做move m4 N$ x1 j( v o+ L$ M% T s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; 6 W4 Q# x/ G$ B- S0 _' N s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf; ) q, n$ S5 i) x& @6 F. e' ~ i=1;' P6 G9 z( p- E( o while(i<5&&!move(top,i)) . W9 q! w0 O8 W2 r, F- B% x g- K i++; 4 `6 K( X! i5 i }

; A; p' E- J# a% `5 [& b: a. A

}2 t% W# P) u0 K' F1 R, F else, j2 T, M1 G+ M) o) e6 r9 r {' j" S7 }# e9 X+ B) ?4 J* q //回溯 - f7 ~/ m3 T C$ u1 R/ z while(top>=0&&s[top].m>=4) {" ] A7 k; l5 z, Q# N f top--;4 q6 m5 @9 {& N6 ?$ q n if(top>=0) 4 c# H6 K4 w- l* Z0 `# x6 } {: w, R% p D- W, M# Q4 A //在上次状态基础上准备做move4 F2 E: S% a4 [ s[top].man=s[top-1].man;s[top].sheep=s[top-1].sheep; ( ^) n$ ~2 W8 v0 P4 G1 f: h' f5 v/ W s[top].cabbage=s[top-1].cabbage;s[top].wolf=s[top-1].wolf;7 Y1 j, V" I4 E* g L& C i=1; % c9 j9 d1 U" j' B+ C' v while(!move(top,s[top].m+i)) p* u# {7 {" |& [$ G, }0 E0 s i++; " ~% x& {2 p1 i _ }8 a/ ]1 y. ?- {! t5 P1 f }( z X+ T# p& x( a/ `, A }//while) o# M @+ X) C- w }//f27 z8 {# N; G7 P1 T: G //---------------------------------1 x2 h$ Q1 i6 I& h) D

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

10

主题

1

听众

95

积分

升级  94.74%

该用户从未签到

网络挑战赛参赛者

新人进步奖

回复

使用道具 举报

1253

主题

443

听众

-516

积分

复兴中华数学头子

  • 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-6-17 21:56 , Processed in 0.487620 second(s), 75 queries .

    回顶部