随堂练习——电梯调度算法

浏览数：234 / 时间：2015年06月08日

题目要求：

    石家庄铁道大学基础大楼一共有四部电梯，每层都有人上下，电梯在每层都停。信1201-1班的张一东觉得在每层都停觉得不耐烦。
     由于楼层不太高，在上下课高峰期时时，电梯从一层上行，但只允许停在某一楼层。在一楼时，每个乘客选择自己的目的层，电梯则自动计算出应停的楼层。
      问电梯停在那一楼层，能够保证这次乘坐电梯的所有乘客爬楼梯的层数之和最少。

一、解决思路

　　对于一个i层, 假设数组中比i层小的有blowc个，等于i层的有equlc个，大于i层的有highc个。需要设置一个到i层的要走所有楼层的和的绝对值数组，来记录停在每个楼层一共需要走的层数之和，小于i+1的有blowc+equlc层，大于i+1的有blowc-equlc层，相比较Y(i)的情况，高于i层的和低于i层的的差的绝对值，增加了blowc+equlc，减少了 blowc-equlc。求出停在各楼层时爬楼梯的总和分别是多少，选择最少的停下来。

二、程序代码

 1 #include "stdafx.h"
 2 #include<iostream.h>
 3 #include "stdlib.h"
 4 #define max 1000
 5 void FloorNum(int *in, int num)
 6 {
 7      int result[max]={0};
 8      int blowc,equlc,highc;      //分别表示小于、等于、大于第i个数
 9      int cur=0,i;
10      int b=0,h=0;
11      blowc=0;
12      highc=num;
13      equlc= 0;
14      for(i=0;i<num;i++){
15          h=in[i]+h;
16     }
17      result[0] = h;
18      cout<<"停在各楼层时爬楼梯的总和分别为:"<<endl;
19      for(i=1;i<=in[num-1];i++){
20          blowc=equlc+blowc;
21          highc=equlc-highc;
22          h=highc-h;
23          b=blowc+h;
24          result[i]=b+h;
25          {
26          cout<<"停在"<<i<<"层"<<"爬楼梯总数为："<<result[i]<<endl;
27          }
28          equlc=0;
29          while(in[cur]==i){
30              cur++;
31              equlc++;
32          }
33      }
34 }
35 int main(int argc, char* argv[])
36 {
37     int nperson;
38     int in[max];
39     cout<<"进电梯的人数："<<endl;
40     cin>>nperson;
41     cout<<"请输入每个人进入电梯后按下的楼层数"<<endl;
42     for(int i=0;i<nperson;i++)
43     {
44        cin>>in[i];
45     }
46    FloorNum(in,nperson);
47     return 0;
48 
49 }

三、结果截图

技术分享

四、心得体会

上课的时候，一开始很纠结为什么要把好好的电梯设计成这样，在实际生活中根本不能够应用，后来想通了，其实这就是一个算法，一个优化设计，后来在老师的指导下，我把它当成一道数学题来做。最先考虑到的最简单也是最笨的的解决方案，即从第一层开始枚举x一直第N层，然后计算如果电梯在第x层停的话所有乘客总共要爬多少层楼。这个程序代码是两重循环，但效率太低，时间复杂度较高，后来经过老师点醒，用到了先前的计算的结果，是每一次运算都能最大利用，把时间复杂度由O(N^2)降低到了O（N）。实现了算法优化，达到了程序设计的目的。

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

随堂练习——电梯调度算法