今日面试题:修理栅栏

为了修理栅栏,需要将很长的木板锯为N块,长度分别为L1,L2...LN。锯断一块儿木板,需要一定的开销,开销记为木板的长度。例如,长度为21的木板,锯为三块,长度分别为5,8,8。如下按照如下的顺序据断:

1. 首先锯断21为13和8两块儿,开销为21

2. 然后锯断13为8和5两块儿,开销为13

总的开销为34。但也可以按照如下的顺序:

1. 首先锯断21为16和5两块儿,开销为21

2. 然后锯断16为8和8两块儿,开销为16

总的开销为37。比34要大。

问题是,给定N,以及每一块儿的长度。如何保证最小的开销。尽量采用高效的方法。

=============

排列木桩

原题

有N个木桩,高度分别为1到N。你现在要将木桩排列为一行,当你从左边看的时候,只看到L个木桩(因为,一些高的木桩会挡住矮的木桩);从右边看时,只看到R个木桩。给定N、L、R,你该如何排列木桩呢?

例1:N=3,L=2,R=1,可行的排列方案只有{2,1,3}。

例2:N=3,L=2,R=2,可行的排列方案有{1,3,2}{2,3,1}

分析

开始排列木桩的时候,应该如何选取第一根木桩呢?一个很直接的选择就是先确定最高的木桩的位置,也就是N。因为,无论从左到右,还是从右到左看,都要到最高停下来。

确定了最高的木桩之后,无论从哪一边看,都至少有一个木桩。接下来,该如何处理?想必大家已经想到了,开始递归呗。左右两边,也同样是先确定最高的木桩的位置,依次递归下去。

构造的方法,是比较简单地。但,往往这个时候面试题并没有结束。面试官,会进一步问:给定NLR,有多少种排列木桩的方法呢?从一个构造问题,转变为一个计数的问题。该如何做呢?方法仍旧是递归,我们尝试写出递归表达式。

假设,b(N,L,R)表示排列方案的总数。f(N, L)表示N个木桩,排列得到从左边能够看到L个木桩的方案总数。我们从f的递归形式入手分析。

首先,f(N,N)=1。从左到右,从低到高排列,只有一个方案。

然后,f(N,M)=0,当N< M时。显而易见。

其次,f(N,1)=(N-1)!。当只看到一个木桩的时候,即最高的木桩排在最左边,其他的木桩无论怎么排列都可以。

再次,假设最高的木桩放在从左边开始的第k个位置,则,我们要在剩下的N-1个木桩里面,选取k-1个木桩放在最高木桩的左边,并且,找到能看到L-1个木桩的方案数(因为最高的木桩一定能看见,所以是L-1个),此时剩下的N-K个木桩,可以任意排列,得到递归表达式如下:

f(N, L) = sum_{L<=k<=N} (N-1 选择 k-1) * f(k-1, L-1) * (N-k)!

这个式子,是仅仅考虑了总左边看到L个柱子的情况,再需要考虑,从右边看,有R根柱子的方案呢?其实很简单了,剩下的N-k个柱子,不要任意排列,要保证从右边能够看到R-1个柱子即可。所得递归式如下:

b(N,L,R) = sum_{L<=k<=N-R+1} (N-1 选择 k-1) * f(k-1, L-1) * f(N-k,R-1)

如何?并不是很难的题目,只要抓住从哪根木桩开始即可。

其实,这个题目从最矮的木桩开始,也可以写出漂亮、而且更简单递归表达式的。简单提示:

* 何时能够看到最矮的木桩?

* 看到了如何?

* 看不到,又如何?

【分析完毕】

本文来自微信:待字闺中,2013-08-18发布,原创@陈利人 ,欢迎大家继续关注微信公众账号“待字闺中”。