# 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时，有两种堆叠形式；
• 当要求长度为3时，有三种堆叠形式；

## 题解：

• $$f(1)=1$$
• $$f(2)=2$$
• $$f(3)=3$$

• 在长度为$$n-1$$的所有堆叠形式的砖墙最右侧，追加基本形式1，然后得出砖墙形式总数仍为$$f(n-1)$$：
• 在长度为$$n-2$$的所有堆叠形式的砖墙最右侧，追加基本形式2，得出砖墙形式总数仍为$$f(n-2)$$：

$$f(1)=1, \\ f(2)=2, \\ f(n)=f(n-1)+f(n-2)\hspace{3mm}(n>2).$$