有一个写字楼有 28 层,每层有 4 个区,每个区有 8 个办公室,有 7 个电梯,每天早高峰有 1 万人上班。怎么做能以最快的速度将早高峰的人送到他们的楼层?(20 分) 1.请做出一些假设 2.请描述你的算法 3.请仿真并实现你的算法 4.请计算出需要的时间
1
tongz OP 没有大佬来解答吗。。
|
2
v9ox 2017-08-18 10:06:26 +08:00 via iPhone
这不是算法题。
|
3
meepo3927 2017-08-18 10:08:44 +08:00
这是实际问题吧。
非常非常实际的问题。 |
4
chisoco 2017-08-18 10:10:54 +08:00
这是建模啊
|
5
chenyu8674 2017-08-18 10:29:26 +08:00 2
没明白电梯跟办公室有什么关系,如果只说楼层间运输的话,初步想法为:
1 号梯:1,2,3,4 层 2 号梯:1,5,11,17,23 层 3 号梯:1,6,12,18,24 层 4 号梯:1,7,13,19,26 层 5 号梯:1,8,14,20,26 层 6 号梯:1,9,15,21,27 层 7 号梯:1,10,16,22,28 层 保证每层都有电梯直达,有急事的坐进最近的电梯最多上下 3 层楼就能到达目的楼层 |
6
irexy 2017-08-18 10:30:03 +08:00
“每层有 4 个区,每个区有 8 个办公室” 这个条件有什么用?
|
7
billion 2017-08-18 10:33:15 +08:00
1.假设所有电梯全部独立,没有联动
2.假设有一个人拿着一把刀,如果发现有人点了多个电梯,就砍死他。 |
9
tongz OP @chenyu8674 和我想的差不多,在这个基础上,有急事的就走楼梯呗。
|
10
Microi 2017-08-18 10:38:50 +08:00
电梯限载几人啊?
|
12
davy1995 2017-08-18 10:41:53 +08:00 via Android
@chenyu8674 一楼还要啥电梯
|
13
SuperMild 2017-08-18 10:44:34 +08:00
在上面限楼层的方案的基础上,再限时段,假设高峰期有 1 个小时,那前半个小时 1 号梯就只上 2 层、3 层,后半个小时就只上 4、5 层,便于员工分流别全挤在一起排队。
|
14
davy1995 2017-08-18 10:45:27 +08:00 via Android
@chenyu8674 早高峰上楼是不是可以把 1 楼去掉,给下楼的留一个带一楼的电梯就好了
|
15
nazor 2017-08-18 10:49:27 +08:00 via iPhone
28 正好 7 的倍数,楼层除以 7 取余数决定乘哪个电梯,再规定 1 楼每个电梯都能到达。
|
16
chenyu8674 2017-08-18 11:05:08 +08:00
@davy1995 1 楼不停咋上人?
|
17
davy1995 2017-08-18 11:14:10 +08:00 via Android
@chenyu8674 😂我的
|
18
wukongkong 2017-08-18 11:16:34 +08:00
@billion 好方法~
|
19
jason19659 2017-08-18 11:45:54 +08:00
这一万是不是能挤进一个电梯里
|
20
tongz OP |
21
GreatHumorist 2017-08-18 11:55:57 +08:00 via iPhone 3
看看硬盘读取算法,基本一致,28 层就是盘片,分区就是扇区,办公室就是存储单元。建议看下操作系统原理。
|
22
misaka19000 2017-08-18 11:56:51 +08:00 via Android
额,这不就是电梯算法吗,Linux 就是用这个算法进行磁盘任务调度的
|
23
GreatHumorist 2017-08-18 11:56:58 +08:00 via iPhone
不过这个只是比磁盘的磁头多,用磁盘读取算法优化一下应该就可以
|
24
sunjourney 2017-08-18 11:58:33 +08:00
最好的算法就是你让他们自己选,选一个月以后,大家各自知道各自上哪个电梯了
|
25
shalk 2017-08-18 12:28:12 +08:00 via iPhone
这是建模题 条件不充分也很开放
|
26
cokepro 2017-08-18 13:03:44 +08:00
@sunjourney 遗传算法?
|
28
skadi 2017-08-18 14:04:28 +08:00 via Android
来个 b 树?
|
29
chinvo 2017-08-18 14:15:21 +08:00
让这 1w 人跑楼梯(逃
|
30
misaka20038numbe 2017-08-18 14:29:58 +08:00
每层有四个区,所以将 4 个电梯分成每个区对应一个专用电梯
剩 3 个电梯作为公共电梯,4 个区都可用,一个电梯直上另一个电梯就直下,剩一个可上可下。 |
31
tao1991123 2017-08-18 14:55:53 +08:00
@sunjourney 你这个叫做遗传算法......
|
32
nosugar 2017-08-18 15:00:24 +08:00
|
33
nosugar 2017-08-18 15:00:58 +08:00
|
34
tongz OP @GreatHumorist 谢谢,学习了。
|
35
LancerEvo 2017-08-18 15:19:48 +08:00 1
我的一点分析,并非解答:
首先假设早高峰 60 分钟,1 万人,除去 1 层的,7 电梯,平均每个电梯每分钟运 23 人,而正常大小的电梯至少得两趟才能运 23 人,也就是说半分钟一趟,平均楼层 14.5,往返,加开门关门上下人,这个题目是不可能的。 不过题目允许你自己假设,你可以假设早高峰有俩小时,某个楼层的只能某个时间段来,就完了。 但我感觉这并不是题目的本意,题目的本意应该是假设所有人同时到,或者在某个时间段内随机到,如何运作电梯最有效,或者所有人总的等待时间最短。 然后题目里的区和办公室看起来没用,因为题目并没有限定说某个电梯只能到某个区。 前头的回答里,每层只有一个电梯能到,从而保证每个电梯都停的次数最少,直观感觉是最快的,因为毕竟停、上下人、再启动是最耗时的,但实际中,这是否比有两个电梯都能到达某一层从而减少了等待时间更好,我没验证过。 之所以我有这个质疑,1 是因为我原来公司正好 28 层,6 电梯,如果没记错是 3 个能到 1-x 层的,另外 3 个是 x 以上高楼层的,实际体验不错,然而另外某人力公司也是在 28 层左右,也是有 6 电梯,但貌似只有 1 个还是 2 个能到 28 层,实际体验很糟糕,总要等很久; 2 是因为实际中貌似很少有某个写字楼只有一个电梯能到某一层的,并且也没见过哪儿是求余来安排的尽量分散的,我猜可能是因为停 2-3-4 层的平均运行速度未必比停 5-10-15 要慢,要想加速可能得停 5-25 这样才能体现出来。记得原来某个公司电梯是 5-19 之间不停,期间速度明显是要快于隔两层停一下的。各大电梯厂商应该想的比我明白,我相信他们的算法就是最优的,即使不是,也是经过很久的时间检验的,比我连实验都没做要强的多。 只提一句磁盘读取算法的各位,说这个等于没说,估计只知道磁盘读取用的电梯算法但不知道到底算法是啥。 磁盘读取算法只是请求排序之后先往一头扫,到头以后再往回扫( SCAN )或者从 0 再开始扫( C-SCAN )。早高峰上到头再下到 0 层(或者 1 层,取决于你的哲学观点)这本身就是 C-SCAN,没有任何人傻到想出一个非 C-SCAN 的先停 4 层下人再回到 3 层下人再上到 5 层下人的算法的。 如果能谈谈单盘片单盘面多磁头的调度,才是本题。 说多了,我感觉出题人没想到我这么多,233,可能人就是想让你写个代码解决个实际问题看看你 coding 能力。 |
36
silencefent 2017-08-18 16:12:39 +08:00
@chenyu8674 你这个思路只是苦了送外卖 /快递的,因为只考虑上下班不考虑楼层上下
|