Personal nest in the information age

Fibonacci numbers and Brick Wall Patterns

题目:

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”,其长度为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开始的)。

Bibliography

Leave a comment

Your email address will not be published. Required fields are marked *