题目:

If we want to build a brick wall out of the usual size of brick which has a length twice as long as its height, and if our wall is to be two units tall, we can make our wall in a number of patterns, depending on how long we want it. From the figure one observe that:
- There is just one wall pattern which is 1 unit wide — made by putting the brick on its end.
- There are 2 patterns for a wall of length 2: two side-ways bricks laid on top of each other and two bricks long-ways up put next to each other.
- There are three patterns for walls of length 3.
How many patterns can you find for a wall of length 4? And, for a wall of length 5?
题意:
有长高宽为1:2的砖块,忽略其厚度,题目中单个砖块长=1,所以宽=2。用不同的堆叠形式组成墙,墙的横向视为长(length),竖向视为高(height),保持高度始终为2。
- 当要求砖块堆长度为1时,有一种堆叠形式;
- 当要求长度为2时,有两种堆叠形式;
- 当要求长度为3时,有三种堆叠形式;
问:当要求砖墙长度为4时,有多少种堆叠形式。如果长度为5,又有多少种?推广至长度n,又有多少种?
题解:
这是一道数学题,也是UVa OJ上的一道算法题,但是网上很多只给出代码,不讲证明过程。我在英国萨里大学 (University of Surrey) 数学学院的网站上找到了完整思路,将其整理如下:
将砖墙长度记为n,相应砖墙的堆叠形式的总数记位\(f(n)\)。根据题目给出的图样示例可以得知:
- \(f(1)=1\)
- \(f(2)=2\)
- \(f(3)=3\)
同时,也可以发现两种基本的堆叠形式:

所有的砖墙都可以被视为图1两种形式的排列组合。我们将图1左侧的砖块堆叠形式记为“基本形式1”,其长度为1;右侧记为“基本形式2”,长度为2。
根据题目中的图样示例可以看出,基本形式1和2分别存在于length=1和length=2的堆叠形式中。
我们进一步推广分析,当\(n>2\)时,我们可以发现\(f(n)\)的所有堆叠形式可以划分为下面两种情况:
- 在长度为\(n-1\)的所有堆叠形式的砖墙最右侧,追加基本形式1,然后得出砖墙形式总数仍为\(f(n-1)\):

- 在长度为\(n-2\)的所有堆叠形式的砖墙最右侧,追加基本形式2,得出砖墙形式总数仍为\(f(n-2)\):

当然,也可以选择在砖墙最左、或中间任何位置插入,本文选择最右侧仅仅是为了方便描述。
在分解成上面两种情况之后,应该就可以很容易地看出:当\(n>2\)时,\(f(n)\)可以视为这两种情况之和,即:$$f(n)=f(n-1)+f(n-2)\hspace{3mm}(n>2)$$
结合\(n=1\),\(n=2\)的情况得出最终结果:
$$f(1)=1, \\ f(2)=2, \\ f(n)=f(n-1)+f(n-2)\hspace{3mm}(n>2).$$
是不是特别像Fibonacci数列的递归定义(注意标准的Fibonacci数列是从0,1开始的)。