计算机科学概论中关于算法的一道题,
来源:学生作业帮 编辑:作业帮 分类:综合作业 时间:2024/08/23 21:20:42
计算机科学概论中关于算法的一道题,
有4位采矿者,他们只有一个手电筒,并且必须走过挖矿的坑道.他们最多可以两个人一起通过,并且其中一个人必须拿着手电.这4位采矿者分别叫Andrews、Blake、Johnson和Kelly,他们单独通过坑道的时间分别是1min、2min、4min和8min.当两个人一起通过坑到时,要以速度慢的人的速度为准,如何安排才能使这4人在15min内通过坑道?
(不太清楚题干要求是当一个人通过坑道时也必须拿着手电,还是只有两个人通过时才必须使用手电.如果是后者则问题很好解决,但如果是前者,要在15min内全部通过,则几乎是不可能的事)
有4位采矿者,他们只有一个手电筒,并且必须走过挖矿的坑道.他们最多可以两个人一起通过,并且其中一个人必须拿着手电.这4位采矿者分别叫Andrews、Blake、Johnson和Kelly,他们单独通过坑道的时间分别是1min、2min、4min和8min.当两个人一起通过坑到时,要以速度慢的人的速度为准,如何安排才能使这4人在15min内通过坑道?
(不太清楚题干要求是当一个人通过坑道时也必须拿着手电,还是只有两个人通过时才必须使用手电.如果是后者则问题很好解决,但如果是前者,要在15min内全部通过,则几乎是不可能的事)
首先肯定是前者,我简单的将4人分为A、B、C、D,AB先一起过,A拿回手电,总共3min;CD一起过,B拿回手电筒,总共10min;再AB一起过,需2min;总计15min.望采纳~