一道小学题目

前两天在同学群里有人转了一篇文章,里面有一道小学题目:

烙饼的时候,第一面需要烙两分钟,烙第二面的时候,因为饼已经比较干了,所以只需要烙一分钟,锅里面刚好能放下两张饼,问烙15张饼最少一共需要多少时间?

文章的作者给出的答案是这样的:

两张一组,先正面再反面,3分钟烙好两张饼,前14张照此办理,共需要14/2*3=21分钟;最后一张饼单独烙,正反面一共3分钟,加在一起:总时间24分钟。

然后作者说,他的一位家长朋友说他的解法并非最优,更好的方法是:

1. 两张一组,烙完12张,共耗时18分钟

2. 第13、14张饼,烙完第一面,2分钟

3. 放第15张饼,烙第一面的2分钟里,另一边依次烙第13、14张饼的第二面

4. 然后第15张饼翻面再烙1分钟就完成了

总时间:18+2+1+1+1=23分钟。

确实比最初的24分钟的方案省了1分钟。

要说我的同学们还是厉害,很快就有人指出:最快的方法难道不是22.5分钟吗?

确实,省时间的要点就在于锅不能闲着:在作者最初的24分钟方案里,最后3分钟的时间,有一半锅是闲着的;在后面的23分钟方案里,最后1分钟时间,有一半锅是闲着的。

那么,什么方案是让锅始终不闲着呢?

在揭晓答案之前,我们先来算一下,理论上最快的方案所能到达的极限在哪里:一张饼需要3分钟,15张饼需要45分钟,锅里可以同时烙两张,如果有一个让锅完全不闲着的方案,最少也得需要45/2,也就是22.5分钟。

那么这个锅不闲着的方案存在吗?当然存在:

1. 前12张饼正常烙,18分钟

2. 烙第13,14的正面,1分钟(此时正面还没烙好)

3. 烙第13,15的正面,1分钟(此时13号饼的正面好了)

4. 烙第14,15的正面,1分钟(此时14,15的正面好了)

5. 烙第13,14的反面,半分钟(此时反面还没烙好)

6. 烙第13,15的反面,半分钟(此时13号饼的反面好了)

7. 烙第14,15的反面,半分钟(此时14,15的反面好了)

总耗时:18+1+1+1+0.5+0.5+0.5=22.5。

在这个方案下,锅没有闲着,也就达到了理论上的最优值:22.5分钟。

问题此时算是达到了完美解决,甚至于有同学指出,当锅可以同时烙n张饼,而总共有m张饼需要烙的时候,当m>=n时,需要时间是3*m/n,具体方案与我们的22.5分钟方案类似组合即可。

但是这个方法有一个问题:

一张饼第一面的两分钟,是可以间断的吗?

在上面的方案里,第2步烙了第14张饼的正面1分钟,然后空了1分钟再去烙第14张饼正面的第二个1分钟。如果可以间断,那这个方案就是成立的,如果不能间断,恐怕还是要之前的23分钟方案才行。

这也涉及到经常有人好奇的一个问题:

双核的速度一定是单核的两倍吗?(类似的问题:四核的速度一定是单核的四倍吗?)

用上面题目的例子就知道了,这取决于要处理的问题本身是否可以很好的并行化:锅是双核的,但如果烙一面饼不能间断(任务不能完全并行化),那就不一定能达到双倍速度。

而在现实中,不能完全并行化的任务还是很多,所以双核处理器并不总能达到双倍的速度。

回到这道题目上,不知道大家是否注意到一点:不管是什么方案,我们都忽略了把饼从锅里拿出来、再换进另外一张饼所需要的时间。如果这个时间是不能忽略的,那总时间相应地还会增加,对应到双核单核的问题上,我们管饼拿出来、换进去的时间,叫做上下文切换时间,这,也是双核速度翻倍的一个制约因素。

于是我又想到了一个经典问题:

一个码农两个月能完成的工作,两个码农一个月能完成吗?

发表评论

电子邮件地址不会被公开。 必填项已用*标注