2013年07月26日

火车运煤问题


火车运煤和鸡蛋挺住问题

在CoolShell上看到一道智力题,挺有意思的,并且和前段时间在陈利人微薄上看到的鸡蛋挺住笔试题有一曲同工之妙,就将这两题一遍摘抄到此。

火车运煤

问题描述简化如下,原题链接点这: > 将3000吨煤从A点运输到B点,A与B之间路线为1000公里,有一辆烧煤的火车来运输,最多只能装满1000吨煤,并且每一公里消耗一吨煤,问,最多> 能有多少吨煤运到B点。

初看此题可能发现没法运阿,运过去就消耗没了,火车还回不来了,但既然能够运过去,肯定就不能直接运过去,得分段,一段段的运输。在后面网友给出了强大的分析过程。可以查看上面的链接,看到网友的分析。下面这段也是从那借鉴过来。

分析

要得到最优解,先了解其两个特征:

1 火车肯定要从起点出发3次,因为每次最多只能运输1000吨 2 火车前两次回到起点要用完车上存煤,否则浪费

火车是每次运1000吨煤出发,到X点,卸下1000-2X吨煤,然后回去,前两次到X点都卸下同样多的煤,第三次到达X点,则共有煤2*(1000-2x) + 1000-x = 3000-5x,倘若这剩下的小于1000吨,则火车可以一次运到终点,边界条件如下,

3000-5x <= 1000 d = 3000-5x-(1000-x)

求解得x>=400,d <= 400,则可以运到终点最多400吨。倘若剩下的还是多余1000吨,这样问题就变成从X点出发到B点,距离为1000-x,煤的总量为3000-5x,然后依此类推,找取下一个X点。 这样观察若要保证到终点煤的总量最大:

3 火车回程要尽可能短

之所以要回程尽可能短,后面火车要尽可能少回头,尽可能多的装载,理想状态是每次回去后都装满1000吨煤出发。则要使第三次到达X点剩余2000吨,3000-5x=2000 x=200,第二次到达Y点,2000-3y=1000 y=333.33,则最终到达终点可以1000-(1000-200-333.33)= 533.33

推广

根据上面的分析,可以推广为火车容量为K,要运载NK的煤到距离为K外的点,那么每个中转站点X为N*K-(2N-1)X=(N-1)k。但是还有一个问题,火车容量为K,运输距离为D,煤的总量为N,这三个数之间没有关联,怎么破?

鸡蛋挺住

此问题是在陈利人老师的微博上看到的,在图灵社区找到这个题目的地址,问题描述如下:

两个鸡蛋,软硬程度一样但未知的鸡蛋,它们可能都在一楼就摔碎,也可能从一百楼摔下来没事,有座100层的建筑,要你用这两个鸡蛋以最少的» 次数确定哪一层是鸡蛋可以安全落下的最高位置,可以摔碎两个鸡蛋。

分析

此问题和上面的十分相似,因为鸡蛋只有两个,在某个楼层扔下来摔破了就没有了,所以一定得谨慎,假如从第i层掉下来,鸡蛋破了,则必须从某层到第i-1层依次测试,才可以得出结果,如果没有破,则可以测试第j层,依此往复得到结果。现在的目标是用最小的次数找到目标楼层,很快想到的是利用二分法的思想一段一段的测试,现在的问题是如何确定每一段的大小。

假设最小的次数是M次,我们首先拿第一个鸡蛋测试,第一次选取第i层测试,如果鸡蛋破了,那么第二个鸡蛋则必须要从1到i-1依次测试,那么测试的次数一共为i次,则i<=M。若鸡蛋没有破碎,我们则选取第j层来测试,如果鸡蛋破碎了,则需要从第i+1层到j-1层测试,总共的测试次数是前面的一次加上j-(i+1)次,一共为j-i次,那么j-i<=M。我们一趟趟测试中,必须保证鸡蛋在任何一楼层,我们所测试的次数不超过M,则后一趟测试的楼层范围必须比前面一趟测试的楼层范围少1,例如第一次测试的楼层范围为1-10,则第二次测试的范围为11-19,依次类推。我们根据此规律可以得出公式。

i + (i-1) + (i-2) + (i-m+1) >= 100,其中m最少的测试次数,i为第一次测试的楼层范围数,由前面的分析知道 i = m,化简前面的公式可得, (m+1)*m / 2 >= 100,即,m^2 + m >= 200,可知M=14;

经过上面的分析,可以知道最少的次数为14。

推广

题目中假设楼层数为100,鸡蛋为2,我们将楼层数设为任意的N层,鸡蛋数为任意的M个,则最少需要的测试次数为多少?

从前面的分析知道,楼层数不重要,关键在于鸡蛋数,首先还是假设楼层为100,鸡蛋数为3的情况,还是向上面的分析过程,第一个鸡蛋首先选取第i层测试,如果鸡蛋破碎,则用余下的两个鸡蛋测试1-(i-1)层,这样问题变为两个鸡蛋来测试i-1层的情况了。如果鸡蛋没破,我们需要再选取第j层来测试,并且满足第i+1到j层最少的测试次数不超过从1到i层最少测试+1。然后下一趟,这样就化解为依赖于鸡蛋数为2的处理情况了,鸡蛋数为4则依赖于鸡蛋数为3的分析情况。

根据上面简短的分析,我们可以知道,使用F(n,m)来表示n层,m个鸡蛋使用的最少测试次数. > F(n,m) = 1 + max{F(i-1,m-1), F(n-i,m)} 其中 1<= i <= n, f(1,i) = 1; > 表达式可以理解为当从第i层开始第一次测试,如果蛋碎了,则需要用余下的m-1个蛋来测试余下的i-1个楼层,如果蛋没碎,则需要用余下的m-1个蛋> 来测试余下的n-i个楼层。

从上面的表达式可以看出,问题转换成动态规划了,但是根据前面的分析,貌似还是可以从纯数学的角度来处理,只是中间要确定每次减少的楼数稍有点复杂。

前一篇: 随机数的简单生成 后一篇: 定长线段最多覆盖点的个数