小明一家过桥问题
时间：2010-09-07 来源：wsnhyjj
现在小明一家过一座桥，过桥的时候是黑夜，所以必须有灯。现在小明过桥要1秒，小明的弟弟要3秒，小明的爸爸要6秒，小明的妈妈要八秒，小明的爷爷要12秒。每次此桥最多可过两人，而过桥的速度依过桥最慢者而定，而且灯在点燃后30秒就会熄灭。问小明一家如何过桥？（原本是个智力题，这里用程序来求解）
#include "stdafx.h"
#define N 5
#define SIZE 64
// 将人员编号：小明-0，弟弟-1，爸爸-2，妈妈-3，爷爷-4
// 每个人的当前位置：0--在桥左边， 1--在桥右边
int Position[N];
// 过桥临时方案的数组下标； 临时方案； 最小时间方案；
int Index, TmpScheme[SIZE], Scheme[SIZE];
// 最小过桥时间总和，初始值100；每个人过桥所需要的时间
int MinTime=100, Time[N]={1, 3, 6, 8, 12};
// 寻找最佳过桥方案。Remnant:未过桥人数; CurTime:当前已用时间;
// Direction:过桥方向,1--向右,0--向左
void Find(int Remnant, int CurTime, int Direction)
{
if(Remnant==0){ // 所有人已经过桥，更新最少时间及方案
MinTime=CurTime;
for(int i=0; i<SIZE && TmpScheme[i]>=0; i++)
{
Scheme[i]=TmpScheme[i];
}
}else if(Direction==1){ // 过桥方向向右，从桥左侧选出两人过桥
for(int i=0; i<N; i++)
{
if(Position[i]==0 && CurTime+Time[i]<MinTime){
TmpScheme[Index++] = i;
Position[i] = 1;
for(int j=0; j<N; j++)
{
int TmpMax = (Time[i]>Time[j] ? Time[i] : Time[j]);
if(Position[j]==0 && CurTime+TmpMax<MinTime)
{
TmpScheme[Index++] = j;
Position[j] = 1;
Find(Remnant-2, CurTime+TmpMax, !Direction);
Position[j] = 0;
TmpScheme[--Index] = -1;
}
}
Position[i] = 0;
TmpScheme[--Index] = -1;
}
}
}else{ // 过桥方向向左，从桥右侧选出一个人回来送灯
for(int j=0; j<N; j++)
{
if(Position[j]==1 && CurTime+Time[j] < MinTime)
{
TmpScheme[Index++] = j;
Position[j] = 0;
Find(Remnant+1, CurTime+Time[j], !Direction);
Position[j] = 1;
TmpScheme[--Index] = -1;
}
}
}
}
int main(int argc, char* argv[])
{
for(int i=0; i<SIZE; i++) // 初始方案内容为负值，避免和人员标号冲突
Scheme[i] = TmpScheme[i] = -1;
Find(N, 0, 1); // 查找最佳方案
printf("MinTime=%d:", MinTime); // 输出最佳方案
for(int i=0; i<SIZE && Scheme[i]>=0; i+=3)
printf(" %d-%d %d", Scheme[i], Scheme[i+1], Scheme[i+2]);
printf("\b\b ");
return getchar();
}
相关阅读 更多 +
