学步园

<!--
@page { margin: 0.79in }
H2 { margin-top: 0.18in; margin-bottom: 0.18in; line-height: 173%; page-break-inside: avoid }
H2.western { font-family: "Arial", sans-serif; font-size: 16pt }
H2.cjk { font-family: "黑体", "SimHei"; font-size: 16pt }
H2.ctl { font-family: "DejaVu Sans"; font-size: 16pt }
P { margin-bottom: 0.08in }
-->

现在小明一家过一座桥，过桥的时候是黑夜，所以必须有灯。现在小明过桥要
1秒，小明的弟弟要
3秒，小明的爸爸要
6秒，小明的妈妈要八秒，小明的爷爷要
12秒。每次此桥最多可过两人，而过桥的速度依过桥最慢者而定，而且灯在点燃后
30秒就会熄灭。问小明一家如何过桥？（原本是个智力题，这里用程序来求解）

方案：    －－>   3min   明、弟

                <－－   1min   明

                －－>   6min   明、爸

                <－－   1min   明

                －－>   12min 明、爷

                <－－    3min  弟

                －－>    3min  明、弟                  总时间： 29min

总结：一定要让弟弟（时间次小）的充当一次送灯人，而且最长的两个时间要一起过来，这样的话，弟弟（次小时间的人）将会起到送灯作用。

代码：    （使用递归计算）

#include "stdio.h"<br /> #define N 5<br /> #define SIZE 64<br /> // 将人员编号：小明-0，弟弟-1，爸爸-2，妈妈-3，爷爷-4<br /> // 每个人的当前位置：0--在桥左边， 1--在桥右边<br /> int Position[N];<br /> // 过桥临时方案的数组下标； 临时方案； 最小时间方案；<br /> int Index, TmpScheme[SIZE], Scheme[SIZE];<br /> // 最小过桥时间总和，初始值100；每个人过桥所需要的时间<br /> int MinTime=100, Time[N]={1, 3, 6, 8, 12};<br /> // 寻找最佳过桥方案。Remnant:未过桥人数; CurTime:当前已用时间;<br /> // Direction:过桥方向,1--向右,0--向左<br /> void Find(int Remnant,int CurTime,int Direction)<br /> {<br /> //所有的人已经过桥，更新最小时间及方案<br /> if(Remnant == 0)<br /> {<br /> MinTime = CurTime;<br /> for(int i=0;i<SIZE && TmpScheme[i]>=0;i++)<br /> Scheme[i] = TmpScheme[i];<br /> }<br /> else if(Direction == 1) //过桥方向为右，从桥的左侧选出两个人过桥<br /> {<br /> for(int i=0;i<N;i++)<br /> {<br /> if(Position[i] == 0 && CurTime+Time[i]<MinTime)<br /> {<br /> TmpScheme[Index++] = i;<br /> Position[i] = 1;<br /> for(int j=0;j<N;j++)<br /> {<br /> int TmpMax = (Time[i]>Time[j] ? Time[i]:Time[j]);<br /> if(Position[j] == 0 && CurTime+TmpMax<MinTime)<br /> {<br /> TmpScheme[Index++] = j;<br /> Position[j] = 1;<br /> Find(Remnant-2,CurTime+TmpMax,!Direction);<br /> Position[j] = 0;<br /> TmpScheme[--Index] = -1;<br /> }<br /> }<br /> Position[i] = 0;<br /> TmpScheme[--Index] = -1;<br /> }<br /> }<br /> }<br /> else //过桥方向向左，从桥右边选出一个人过来送灯<br /> {<br /> for(int j=0;j<N;j++)<br /> {<br /> if(Position[j] == 1 && CurTime+Time[j]<MinTime)<br /> {<br /> TmpScheme[Index++] = j;<br /> Position[j] = 0;<br /> Find(Remnant+1,CurTime+Time[j],!Direction);<br /> Position[j] = 1;<br /> TmpScheme[--Index] = -1;<br /> }<br /> }<br /> }<br /> }<br /> int main()<br /> {<br /> for(int i=0;i<SIZE;i++) //初始方案内容为负值，避免与人员标号冲突<br /> Scheme[i] = TmpScheme[i] = -1;<br /> Find(N,0,1);<br /> printf("MinTime = %d:",MinTime);<br /> for(int i=0;i<SIZE && Scheme[i]>=0;i+=3)<br /> printf(" %d-%d %d",Scheme[i],Scheme[i+1],Scheme[i+2]);<br /> printf(" --The last '-1' means calculate completely!");<br /> getchar(); //如果不使用getchar(),程序运行一闪而过，将看不到结果<br /> //printf("/n"); //如果包含这行，就可以不要getchar()那行，会输出一个回车再退出<br /> return 0;<br /> }