腾讯笔试题_电梯问题_思路和初步的算法_討論一下
题如下:
一座楼里没有楼梯，只有一架电梯，电梯一次最多只能乘3人，已知楼共有20层，每层有一个人，每个人都有1~20中唯一的编号，他们要去对应的楼层。
电梯初始状态：在一楼。
目标状态：每个人在相应楼层。
试编写一个算法，完成目标状态，而且使电梯移动最小距离。
我的思路:
尽可能让电梯满载运行,而且优先解决远处的需求.使得电梯的运行轨迹类似于一个作往复运动的弹簧由于阻尼最后停下来. 对于正态分布的情况, 电梯最后的状态应接近于中点. 理想情况是对于平均分布的输入集合,电梯的运行层数为每个人的(需行层数+3+3)/3,之所以要加两个3是因为电梯在最初运行和达到目标的时候分别有一段必须空载的距离(在初始状态,电梯至少要运行三层才能装满). 当然对于大量数据来说, 实际运行的効率应该趋近这个最优结果的渐近线.
以下是我的程序:目前只是初步实现了一下.拋磚引玉.
C/C++ code#include
#include
/*
* The Question:
*
*一座楼里没有楼梯，只有一架电梯，电梯一次最多只能乘3人，已知楼共有20层，每层有一个人，
每个人都有1~20中唯一的编号，他们要去对应的楼层。电梯初始状态：在一楼。目标状态：每个人在相应楼层。
试编写一个算法，完成目标状态，而且使电梯移动最小距离。
*
* ZhanZongru(Z80_AT_whut.edu.cn)
* 2009,May,30th
*
* For the sake of simpliticy.
*
* The Building uses a United Kingdom Floor naming fashion.
* 0-19 Floors.
* The people in every floor use a United States naming fashion to express their destinations.
* 1-20 Floors.
*
* In one words, 20 Americans in a UK building...
*/
/*Every floor can content 1 to 20 person.*/
unsigned char FloorContent[20][20];
/*The carrier struct.*/
typedef struct _Carrier{
unsigned char Position_uk;
unsigned char Passager_us[3];
}Carrier;
#define CAR_CAP 3
Carrier theCar;
typedef enum _CurrentDirect{
UP_WARD = 0,
DOWN_WARD
}CurDir;
CurDir theDir = UP_WARD;
unsigned char cur_bottom = 0;
unsigned char cur_top = 19;
unsigned char IsSuccessed = 0;
unsigned long RunFloorCount = 0;
void Run_One_Floor(void);
void LayToFloor(unsigned char pos_uk, unsigned char set_id);
void LoadToCar_Up(unsigned char floor_uk, unsigned char id);
void LoadToCar_Down(unsigned char floor_uk, unsigned char id);
unsigned char JudgeStatus();
unsigned char FloorSize(unsigned char floor_uk);
void ReCalc_Bot_Top(void);
void Show_Status(void);
unsigned char FloorFirstOne(unsigned char floor_uk);
unsigned char Min_Passger_id(void);
unsigned char Max_Passger_id(void);
int main(int argc, char** argv)
{
char input_file[50];
char output_file[50];
FILE* fp=NULL;
int i=0;
int simple_crc=0;
if(argc==1)
{
strcpy(input_file, "input.txt");
strcpy(output_file, "output.txt");
}
else if(argc==2)
{
strcpy(input_file, argv[1]);
strcpy(output_file, "output.txt");
}
else if(argc>=3)
{
strcpy(input_file, argv[1]);
strcpy(output_file, argv[2]);
}
else
{
}
fp = fopen(input_file, "r");
if(fp==NULL)
{
perror("Failed:fopen the input file/r/n");
return -1;
}
/*Read in the initial status, the status could generated by another program, now by hand editing.*/
for(i=0;i<20;i++)
{
fscanf(fp, "%d", (int*)&FloorContent[i][0]);
simple_crc+=FloorContent[i][0];
}
fclose(fp);
/*A very simple check to ensure 20 numbers are different.*/
if(simple_crc!=210)
{
}
/*The carrier initialiy stop at the bottom.*/
theCar.Position_uk = 0;
theCar.Passager_us[0] = 0;
theCar.Passager_us[1] = 0;
theCar.Passager_us[2] = 0;
/*It is the main loop, after run every floor, check whether completed.*/
while(!IsSuccessed)
{
#ifdef _DEBUG
Show_Status();
system("pause");
#endif
Run_One_Floor();
}
printf("Success %ld Times/r/n", RunFloorCount);
fp=fopen(output_file, "w");
for(i=0;i<20;i++)
{
fprintf(fp, "%d ",FloorFirstOne(i));
}
fclose(fp);
return 0;
}
/*For debug*/
void Show_Status(void)
{
int i,j=0;
for(i=0;i<20;i++)
{
printf("Floor%d: ",19-i);
for(j=0;j<20;j++)
{
printf(" %02d ", FloorContent[19-i][j]);
}
printf("/r/n");
}
printf("The Car status: %02d, %02d, %02d, %02d, %c/r/n",
theCar.Position_uk, theCar.Passager_us[0], theCar.Passager_us[1], theCar.Passager_us[2],
theDir==UP_WARD? '^':'v');
}
void Run_One_Floor(void)
{
int i=0;
//First decite the run direction of the car
if(theCar.Position_uk==cur_bottom)
{
theDir = UP_WARD;
ReCalc_Bot_Top();
}
if(theCar.Position_uk==cur_top)
{
theDir = DOWN_WARD;
ReCalc_Bot_Top();
}
//To see whether need to lay down someone whose destination is this floor
if(theCar.Passager_us[0]==(1+theCar.Position_uk))
{
LayToFloor(theCar.Position_uk, 0);
}
if(theCar.Passager_us[1]==(1+theCar.Position_uk))
{
LayToFloor(theCar.Position_uk, 1);
}
if(theCar.Passager_us[2]==(1+theCar.Position_uk))
{
LayToFloor(theCar.Position_uk, 2);
}
//Fill the carrier if it has some empty space,or swap when worthy
for(i=0;i<20;i++)
{
if( (FloorContent[theCar.Position_uk][i]>(theCar.Position_uk+1)) && (theDir == UP_WARD) )
{
LoadToCar_Up(theCar.Position_uk,i);
}
if((FloorContent[theCar.Position_uk][i]!=0) &&
(FloorContent[theCar.Position_uk][i]<(theCar.Position_uk+1)) && (theDir == DOWN_WARD) )
{
LoadToCar_Down(theCar.Position_uk,i);
}
}
//Advance a floor
if(theDir == UP_WARD)
{
IsSuccessed = JudgeStatus();
if(!IsSuccessed)
{
theCar.Position_uk+=1;
RunFloorCount++;
}
}
else if(theDir == DOWN_WARD)
{
IsSuccessed = JudgeStatus();
if(!IsSuccessed)
{
theCar.Position_uk-=1;
RunFloorCount++;
}
}
else
{
printf("theDir is error/r/n");
return ;
}
}
unsigned char JudgeStatus()
{
int i = 0;
for(i=0; i<20; i++)
{
if( (FloorSize(i)!=1) || (FloorFirstOne(i)!=(i+1)) )
return 0;
}
return 1;
}
/* Return the first person's destination in one floor.*/
unsigned char FloorFirstOne(unsigned char floor_uk)
{
int i=0;
for(i=0;i<20;i++)
{
if(FloorContent[floor_uk][i]!=0)
{
return FloorContent[floor_uk][i];
}
}
return 0;
}
/*return the number of persons in one floor.*/
unsigned char FloorSize(unsigned char floor_uk)
{
int i = 0;
int j = 0;
for(i=0; i<20; i++)
{
if(0==FloorContent[floor_uk][i])
continue;
j++;
}
return j;
}
/* Re-calculate the current bottom and top floors.*/
void ReCalc_Bot_Top(void)
{
#if 1
int i=0;
if(theDir==UP_WARD)
{
for(i=19;i>=0;i--)
{
if((FloorSize(i)!=1) || (FloorFirstOne(i)!=i+1))
{
cur_top = i;
break;
}
}
}
else if(theDir==DOWN_WARD)
{
for(i=0;i<20;i++)
{
if((FloorSize(i)!=1) || (FloorFirstOne(i)!=i+1))
{
cur_bottom = i;
break;
}
}
}
else
{
}
#endif
}
/* Lay a person from the carrier to the floor.*/
void LayToFloor(unsigned char pos_uk, unsigned char set_id)
{
int i=0;
for(i=0; i<20; i++)
{//Find a empty space to lay down the passager
if(FloorContent[pos_uk][i]==0)
{
FloorContent[pos_uk][i] = theCar.Passager_us[set_id];
theCar.Passager_us[set_id] = 0;
break;
}
}
return;
}
/* When the direction is UPWARD, load a person from the floor to the carrier.*/
void LoadToCar_Up(unsigned char floor_uk, unsigned char id)
{
int i=0;
unsigned char temp=0;
//Find a empty sit set to load the passager
if(theCar.Passager_us[0]==0)
{
#ifdef _DEBUG
printf("the empty set is 0/r/n");
#endif
theCar.Passager_us[0] = FloorContent[floor_uk][id];
FloorContent[floor_uk][id] = 0;
}
else if(theCar.Passager_us[1]==0)
{
#ifdef _DEBUG
printf("the empty set is 1/r/n");
#endif
theCar.Passager_us[1] = FloorContent[floor_uk][id];
FloorContent[floor_uk][id] = 0;
}
else if(theCar.Passager_us[2]==0)
{
#ifdef _DEBUG
printf("the empty set is 2/r/n");
#endif
theCar.Passager_us[2] = FloorContent[floor_uk][id];
FloorContent[floor_uk][id] = 0;
}
else
{//Full, swap if wothy
#ifdef _DEBUG
printf("up swap fig, Min_ID is %d/r/n", Min_Passger_id());
#endif
if(FloorContent[floor_uk][id]>theCar.Passager_us[Min_Passger_id()])
{
temp = FloorContent[floor_uk][id];
FloorContent[floor_uk][id] = theCar.Passager_us[Min_Passger_id()];
theCar.Passager_us[Min_Passger_id()] = temp;
}
}
return;
}
/* return the minium passager's destination in the carrier.*/
unsigned char Min_Passger_id(void)
{
unsigned char min_id = 0;
if(theCar.Passager_us[1]theCar.Passager_us[max_id])
max_id = 1;
if(theCar.Passager_us[2]>theCar.Passager_us[max_id])
max_id = 2;
return max_id;
}
/* When the direction is DOWNWARD, load a person from the floor to the carrier.*/
void LoadToCar_Down(unsigned char floor_uk, unsigned char id)
{
int i=0;
unsigned char temp=0;
//Find a empty sit set to load the passager
if(theCar.Passager_us[0]==0)
{
theCar.Passager_us[0] = FloorContent[floor_uk][id];
FloorContent[floor_uk][id] = 0;
}
else if(theCar.Passager_us[1]==0)
{
theCar.Passager_us[1] = FloorContent[floor_uk][id];
FloorContent[floor_uk][id] = 0;
}
else if(theCar.Passager_us[2]==0)
{
theCar.Passager_us[2] = FloorContent[floor_uk][id];
FloorContent[floor_uk][id] = 0;
}
else
{//Full, swap if wothy
if(FloorContent[floor_uk][id]