|
|
楼主 |
发表于 2006-12-22 10:47:09
|
显示全部楼层
来自： 中国山东青岛
按照编程的思想，14分钟 4 Z! G0 }3 f, N% @" c
先让甲和乙过去,甲回去，丙和丁过去，乙回去，最后甲和乙过去。2+1+7+2+2=14分钟。
/ h4 s& L, I3 @利用求图的最小生成树的算法，很容易解决
* y. w6 w5 O+ K$ Y& f#include
4 a2 e% P- z0 p9 `9 g' E* h2 t+ i#include
9 D& R# N6 z# X4 {
& |8 n9 v: |8 ]# ^# C5 Lint a[4]={1,2,5,7}; //每人过河时间
" x" t6 c ]8 T+ I. E$ kint mark[4]; //0左1右
% p ^. V! H4 x; n( Uint mark1[100]; //状态控制，只有2^4*2=32种状态# X) \1 M% \/ i0 r/ T6 K
int min;//最短时间, Y$ O& `: ^0 A# ?7 r w) Y+ w u. D
* M% p* ^. C; g. l* v/ J* T4 U
int test(int light) //返回状态值
: _6 o" |. n; e( c( ^{
8 k. v. ^" Z: pint i,j;
# e: v5 r8 d6 P) A1 z+ Fj=0;6 B+ c9 \- T0 e) b9 `) z7 i2 G7 v3 K
for(i=0;i<4;i++)2 `) i* L5 _3 P
{
+ @( G; ?4 B$ I& `2 `0 R+ xj*=2;7 I; V! ]. Z; Q8 s T' o* b- E% O
j+=mark;
: K i& A j: U}
+ L8 D& n7 L- {' sj*=2;
6 Q8 ~; E7 H; p `$ ?2 j2 A i# sj+=light;
& B- f0 U+ Q' Z- c- n7 Q2 t" ^return j;+ G' j; v; @; o% C- j+ ]
}
/ |0 T* T) x% M0 q* \" u; J* }- j: v& ]1 n7 S. g4 z0 ~: n |, w
int search(int time,int light) //搜索
6 Y1 B$ C2 W8 L7 u2 F j; r* X$ V5 O{
6 W; n: k# [1 I5 Kint state;
6 l7 p3 Z( I. I. r2 I+ K' cint i,j,stime;" w" N/ e2 m6 p; S& H, Q6 ~
3 y3 M" i$ R. }: d/ Ostate=test(light);! v9 V& F- |# i3 H) I7 P
if(state==31) //终态：人和手电都在右岸
# k: C7 p. x- ]+ ]9 v{
$ c- U1 V3 w1 J2 g# {if(time return 1;
% b+ b, w& W: L; E' I p: ^1 V}; C4 f( T. C* u8 w l' P, ^! x: G
, d9 c b8 }$ Y5 Z& [if(mark1[state]==1) return 0;
% x* W9 q9 |! b! Q7 w7 C0 Q) e
. v9 l f, C0 u0 ~" wmark1[state]=1;5 |5 v! w. C C* l% I
) \9 s: s, e% Bfor(i=0;i<4;i++) //1人, d) J$ b) j) o& y
{
2 b+ j; F7 S0 c" F; f: Gif(mark==light)# y4 K( j- s; D* L! ?
{+ c, }. T7 H5 s; w3 m9 |
mark=!mark;
# c' f9 S3 X8 o: g3 ]stime=a;
0 n4 |5 o9 n% X9 \search(time+stime,!light);
6 e9 d5 H; i D* @; o8 emark=!mark;( ?! d0 W% F9 ^/ G& z2 E
}! o& |* s7 j) N. |6 @
}
; O4 c" E/ l* s1 d# J; H1 k# B; ^
: G0 v6 j' I% e! C/ n2 P/ b& A+ hfor(i=0;i<4;i++) //2人
) S3 c% r5 L& G, g& o( b1 e{6 ~2 p6 s* ]: z0 v$ w6 t
if(mark==light)
% K: w- v4 ^! l3 Z! s; c) X5 u{, W5 C j- b8 g. g! o
mark=!mark;
% G. B7 M! g; A5 |, @( C6 J( y J. B7 c9 ^0 g6 u# \0 e8 B
for(j=i+1;j<4;j++) ' S. _/ n: h3 t: G( D' L
{% W$ y3 x# E! D. J
if(mark[j]==light)
! G# G% i/ _; b6 A) O{
" X8 {6 a! S) e" W- bmark[j]=!mark[j];' y6 {4 K. f" G4 j# L7 y/ g2 |
stime=a[j]>a?a[j]:a;/ n; k, n4 a; ^+ J7 X$ ^5 s
7 N, O1 p0 m( ?3 y" P* I: g# Ysearch(time+stime,!light);
& J) ?$ h! k- b7 q. m# R- Cmark[j]=!mark[j];
8 n" ^3 N* S" \) m4 }( G( m}5 r% U$ c6 E( q, d) Y) A
}2 X' a7 [' S/ i! I; C' N
) ?% ~) k) G0 q$ s3 J6 j
mark=!mark;
: S3 e, Y' O$ h' m2 x- v6 U s2 T: O}2 b, F" i8 \3 c& s
}
g4 }9 ~& C' J6 |9 \
5 m1 c0 i" L1 s* z3 T# h) T" o7 T% x3 S' t: z( K8 N( C
mark1[state]=0;# m4 r7 n: M9 @+ V6 X
return 0;
! X9 A" v9 P0 X}
" r E4 M% `( w3 w8 T( r* f! J8 d4 l6 _; D' x' l- h
void main()
0 |, ~* U3 p7 T: J- L: Z" q, p% c{( o& W( W! W0 L' I2 ~" K6 L7 ]
memset(mark,0,sizeof(mark));
5 E. V2 E3 B% Y) p& lmemset(mark1,0,sizeof(mark1));( s$ I; O; R: b
/ F: O$ u" S" b7 ^# S- Nmin=100;
9 W7 |; c7 N- ~* L6 e7 ~, p W8 W* H0 g- m9 N' U9 a
search(0,0);' R, S# V% T0 s# ^
) T0 c, C4 B) A; @ vprintf("%d\n",min);" C' z- J- l1 y* O
}
& ]5 _- |3 Z4 m6 o( F9 c结果是14分钟。8 F l4 P# r# u: q' \
提供一个思路：让走的慢的两人同时过桥。 |
|
发表于 2006-12-19 17:40:37
发表于 2006-12-19 19:46:17
8min
5 I b N6 Z/ m7 J# C& J
发表于 2006-12-22 13:30:05
