首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > C++ >

腾讯笔试题_电梯有关问题_思路和初步的算法_討論一上

2013-01-05 
腾讯笔试题_电梯问题_思路和初步的算法_討論一下本帖最后由 zhanzongru 于 2009-06-21 19:46:42 编辑问题

腾讯笔试题_电梯问题_思路和初步的算法_討論一下
本帖最后由 zhanzongru 于 2009-06-21 19:46:42 编辑 问题如下:
一座楼里没有楼梯，只有一架电梯，电梯一次最多只能乘3人，已知楼共有20层，每层有一个人，每个人都有1~20中唯一的编号，他们要去对应的楼层。
  电梯初始状态：在一楼。
  目标状态：每个人在相应楼层。
试编写一个算法，完成目标状态，而且使电梯移动最小距离。

我的思路:
尽可能让电梯满载运行,而且优先解决远处的需求.使得电梯的运行轨迹类似于一个作往复运动的弹簧由于阻尼最后停下来. 对于正态分布的情况, 电梯最后的状态应接近于中点. 理想情况是对于平均分布的输入集合,电梯的运行层数为每个人的(需行层数+3+3)/3,之所以要加两个3是因为电梯在最初运行和达到目标的时候分别有一段必须空载的距离(在初始状态,电梯至少要运行三层才能装满). 当然对于大量数据来说, 实际运行的効率应该趋近这个最优结果的渐近线.

以下是我的程序:目前只是初步实现了一下.拋磚引玉.

#include <stdio.h>
#include <string.h>

/*
 * 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_CAP3

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[min_id])
min_id = 1;

if(theCar.Passager_us[2]<theCar.Passager_us[min_id])
min_id = 2;

return min_id;
}

/* return the maxium passager's destination in the carrier.*/
unsigned char Max_Passger_id(void)
{
unsigned char max_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]<theCar.Passager_us[Max_Passger_id()])
  {
  temp = FloorContent[floor_uk][id];
  FloorContent[floor_uk][id] = theCar.Passager_us[Max_Passger_id()];
  theCar.Passager_us[Max_Passger_id()] = temp;
  }
  }
return;
}

[解决办法]
很晚啦，把代码贴上来先，欢迎指教！


#include "stdafx.h"
#include <iostream>
#include<ctime>
#include <algorithm>
using namespace std;

struct Elevator//电梯的状态结构
{
int count;//电梯当前承载人数
int pos;//电梯当前位置
int numsOfPersons[3];//
int direction;//电梯方向，1为向上，-1为向下，0表示完成
};
struct NumsOfOneFlat//一层楼的人所对应的号，每层楼同时最多可能有两人
{
int first;
int sec;
};

int minNumOfElevator(int*arr,int n);
int ascertainDirection(NumsOfOneFlat*arr,int n,int curPos);
int testz(int *n);

int _tmain(int argc, _TCHAR* argv[])
{
srand( static_cast<unsigned>( time(NULL) ) );  //随机种子还是要提供的
 int elevatorNums[20];
 int n=20;
for(int i=0;i<n;i++)
{
elevatorNums[i]=i;


}
 random_shuffle( elevatorNums,elevatorNums+20 ); //随机重排第一次

for(int i=0;i<n;i++)
{
cout<<elevatorNums[i];
cout<<"  ";
}
int *stepsArray;
int volume=1000000;
stepsArray=new int[volume];
double total=0;
for(int i=0;i<volume;i++)
{
for(int j=0;j<n;j++)
{
elevatorNums[j]=j;
}
random_shuffle( elevatorNums,elevatorNums+20 ); //随机重排第一次
stepsArray[i]=minNumOfElevator(elevatorNums,n);
total+=stepsArray[i];
cout<<stepsArray[i]<<"  ";
}
cout<<endl<<"Min Steps:"<<total/volume<<endl;
return 0;
}

int minNumOfElevator(int *arrNum,int n)//对一组数据计算电梯最小移动步数
{
NumsOfOneFlat*arr;//定义一个NumsOfOneFlat类型的指针变量，用来存储arrNum数组的值
Elevator elevator;//定义一个Elevator型变量，用来表示电梯当前的状态
int eleSteps=0;//对电梯移动的层数计数

//初始化化化elevator
elevator.count=0;
elevator.pos=0;
//初始化arr
arr=new NumsOfOneFlat[n];
for(int i=0;i<n;i++)
{
arr[i].first=arrNum[i];
arr[i].sec=-1;//-1为无效值
}
while(true)
{
if(elevator.count==0)//当电梯中的人数为0时，重新确定电梯运行的方向
{
elevator.direction=ascertainDirection(arr,n,elevator.pos);
if(elevator.direction==0)//此时所有的人都回到了对应的楼层，故返回
return eleSteps;

if(elevator.pos!=arr[elevator.pos].first)
{
elevator.count++;
elevator.numsOfPersons[0]=arr[elevator.pos].first;
arr[elevator.pos].first=arr[elevator.pos].sec;
arr[elevator.pos].sec=-1;
}
}
if(elevator.pos==1)
elevator.pos=1;
if(elevator.direction==1)//此时电梯向上运行
{
elevator.pos++;
eleSteps++;

if(elevator.count>0&&elevator.numsOfPersons[0]==elevator.pos)
{
if(arr[elevator.pos].first==-1)
arr[elevator.pos].first=elevator.pos;
else
arr[elevator.pos].sec=elevator.pos;

for(int i=0;i<elevator.count-1;i++)
elevator.numsOfPersons[i]=elevator.numsOfPersons[i+1];
elevator.count--;
}
if(arr[elevator.pos].first>elevator.pos)
{
if(elevator.count==3)
{
if(arr[elevator.pos].first>elevator.numsOfPersons[0])
{
int temp=arr[elevator.pos].first;
arr[elevator.pos].first=elevator.numsOfPersons[0];
elevator.numsOfPersons[0]=temp;
}
}
else
{
elevator.numsOfPersons[elevator.count]=arr[elevator.pos].first;
elevator.count++;
arr[elevator.pos].first=arr[elevator.pos].sec;
arr[elevator.pos].sec=-1;
}
//当此时电梯中人数超过2时，重新对电梯中的人进行排序，即elevator.numsOfPersons中的数是从上到大的
if(elevator.count>=2)
{
for(int i=0;i<elevator.count;i++)
for(int j=i+1;j<elevator.count;j++)
{
if(elevator.numsOfPersons[i]>elevator.numsOfPersons[j])
{
int temp=elevator.numsOfPersons[i];
elevator.numsOfPersons[i]=elevator.numsOfPersons[j];
elevator.numsOfPersons[j]=temp;
}
}
}
}
}
else
{
elevator.pos--;
eleSteps++;
if(elevator.count>0&&elevator.numsOfPersons[0]==elevator.pos)
{
if(arr[elevator.pos].first==-1)
arr[elevator.pos].first=elevator.pos;
else
arr[elevator.pos].sec=elevator.pos;

for(int i=0;i<elevator.count-1;i++)
elevator.numsOfPersons[i]=elevator.numsOfPersons[i+1];
elevator.count--;
}
if(arr[elevator.pos].first<elevator.pos&&arr[elevator.pos].first>=0)


{
if(elevator.count==3)
{
if(arr[elevator.pos].first<elevator.numsOfPersons[0])
{
int temp=arr[elevator.pos].first;
arr[elevator.pos].first=elevator.numsOfPersons[0];
elevator.numsOfPersons[0]=temp;
}
}
else
{
elevator.numsOfPersons[elevator.count]=arr[elevator.pos].first;
elevator.count++;
arr[elevator.pos].first=arr[elevator.pos].sec;
arr[elevator.pos].sec=-1;
}
//当此时电梯中人数超过2时，重新对电梯中的人进行排序，即elevator.numsOfPersons中的数是从上到大的
if(elevator.count>=2)
{
for(int i=0;i<elevator.count;i++)
for(int j=i+1;j<elevator.count;j++)
{
if(elevator.numsOfPersons[i]<elevator.numsOfPersons[j])
{
int temp=elevator.numsOfPersons[i];
elevator.numsOfPersons[i]=elevator.numsOfPersons[j];
elevator.numsOfPersons[j]=temp;
}
}
}
}
}
}
}
int ascertainDirection(NumsOfOneFlat*arr,int n,int curPos)//确定电梯运行方向
{
int down=-1,up=-1;
for(int i=curPos;i>=0;i--)
{
if(arr[i].first>=0&&arr[i].first<i)
{
down=curPos-i;
break;
}
}
for(int i=curPos;i<n;i++)
{
if(arr[i].first>=0&&arr[i].first>i)
{
up=i-curPos;
break;
}
}

if(down==-1&&up==-1)
return 0;
else if(down==-1&&up!=-1)
return 1;
else if(down!=-1&&up==-1)
return -1;
else if(down!=-1&&up!=-1)
{
if(up<down)
return 1;
else
return -1;
}

}
[解决办法]
//#include "Elevator.h"
#include <math.h>
#include <iostream.h>

#define TRUE  1
#define FALSE 0
#define _ void main()
#define __ {;}
typedef struct {

int    peoNum;           //电梯人数

int    position;         //电梯所在楼层

bool   moveFlag;         //电梯下一步方向

int    moveLastflag;     

int    destination[3];   //电梯里面的人的目的地

}LiftBox;

class Lift
{
protected:
LiftBox *liftBox;

int people[20];         //标记每层楼的人所要达到的目的地

    int step;              //记录电梯的步数

int updownFlag;        //记录所在楼层的人是要上还是下
public:

Lift();

~Lift();

void  UpdatePosition(bool moveFlag, int &position);  //电梯移动位置

void   UpdateLift(int position, int *desination, int flag);//如果需要上下电梯,更新desition数组,不更新和只上不下返回0,有下返回下的值

bool  GoOnFlag(int *people, int position, int moveLastFlag);//电梯移动的方向

int Min_Max(int flag,int a,int b,int c);//返回的数值是最大或者最小

void Swap(int &a, int &b);

bool AreYouOK();  //走完了吗

bool ChangeFlag();//改变电梯方向

bool UpDown(int position); //要上还是下



void  Run(); 


};
Lift::Lift()
{
liftBox = new LiftBox;
for(int i = 0; i<=2; i++)
{
liftBox->destination[i] = 0;

}

liftBox->moveFlag = 1;
liftBox->moveLastflag = 1;
liftBox->peoNum = 0;
liftBox->position = 1;
for(int j = 0; j<=19; j++)
{
people[j] = 20-j;
}
    updownFlag = 1;
step = 0;
Run();

}

Lift::~Lift()
{
delete liftBox;
}
void Lift::UpdatePosition(bool moveFlag, int& position)
{

(moveFlag)?(position++):(position--);
liftBox->moveLastflag = liftBox->moveFlag;
step++;

}
int Lift::Min_Max(int flag,int a,int b,int c)
{
if(!a)
{
return 0;
}
else
{
if(!b)
{
return 1;
}
else
{
if(!c)
{
return 2;
}
}
}
if(!flag)
{//max
if(a>b)
{
if(a>c)
{
return 0;
}
else
{
return 2;
}
}
else
{
if(b>c)
{
return 1;
}
else
{
return 2;
}
}

}
else
{
if(a<b)
{
if(a<c)
{
return 0;
}
else
{
return 2;
}
}
else
{
if(b<c)
{
return 1;
}
else
{
return 2;
}
}

}
}
void Lift::Swap(int &a, int &b)
{
int t;
t = a;
a = b;
b = t;
}
void  Lift::UpdateLift(int position, int *desination, int flag)
{
UpDown(position);
int val;
for(val = 0;val<3;val++)
{
if(desination[val]==position)
{
Swap(desination[val],people[position-1]);
return;
}
}
val = Min_Max(flag, desination[0], desination[1], desination[2]);
if(updownFlag == flag)
{

if(flag)
{

if((desination[val]<people[position-1])
[解决办法]
(desination[val]==0))
{
Swap(desination[val],people[position-1]);
return;
}
}
else
{
if((desination[val]>people[position-1])
[解决办法]
(desination[val]==0))
{
Swap(desination[val],people[position-1]);
return;
}

}

}
}
bool  Lift::GoOnFlag(int *people, int position, int moveLastFlag)
{
if(moveLastFlag)
{
if(position==20)
{
return FALSE;
}
for(int i = position;i<20;i++)
{
if((i+1)!=people[i])
{
return TRUE;
}
}
}
else
{
if((position==1)&&(step!=0))
{
return FALSE;
}
for(int i = position;i>0;i--)
{
if(i!=people[i-1])
{
return TRUE;
}
}

}
return FALSE;


}
bool Lift::UpDown(int position)
{

((people[position-1]-position)>0)?(updownFlag = 1):(updownFlag = 0);
return updownFlag;

}
bool Lift::AreYouOK()
{
for(int i = 1;i<21; i++)
{
if(people[i-1]!=i)
return FALSE;
}
return TRUE;
}
bool Lift::ChangeFlag()
{
if(!AreYouOK())
{
liftBox->moveFlag = !(liftBox->moveLastflag);
return TRUE;
}
return FALSE;

}
void Lift::Run()
{
while(!AreYouOK())
{

UpdateLift(liftBox->position, liftBox->destination, liftBox->moveFlag);
if(!GoOnFlag(people, liftBox->position, liftBox->moveLastflag))
{
ChangeFlag();
}
UpdatePosition(liftBox->moveFlag, liftBox->position);
cout<<liftBox->position<<endl;

}
cout<<step;
}
Lift theLift;
_
__


[解决办法]
说明：
1. 首先说明一下目的地的生成规则，第一种是每个人的目的地都不相同，但随机排列（20!种情况）；第二种是每个人的目的地都是完全随机的，可以重复（20^20种情况；上面的测试结果使用的是第一种生成规则；
2. 关于人在到达目的地之前是否可以下电梯，为了实际应用考虑，本算法规定不能；
3. 本算法的原理是找出所有可能的电梯运行路线，从中选出最优的策略；可以通过参数调节计算量，并影响结果的准确度；所以本算法不能得到所有情况的最优结果。

读书人精选
热点排行