UC知道求递推公式
来源：百度知道 编辑：UC知道 时间：2024/05/24 18:32:34
The New Year’s Day is comming ! Every family want to make theiir house looks more beautiful , so does Teddy’s . To make his own house looks different from other's , he went to the shop to buy four kinds of tiles . each kind of tiles has different size : 1*1 , 2*2 , 3*3 and 4 * 4, respectively .
The problem is , how many ways there are to tile his floor which has a area of 4*N using these four kinds of tiles ? You can assume that the number of each kind of tiles is enough.
请写下递推公式
The problem is , how many ways there are to tile his floor which has a area of 4*N using these four kinds of tiles ? You can assume that the number of each kind of tiles is enough.
请写下递推公式
1*1x+2*2y+3*3z+4 * 4d=4*N
x+9z=4N-4y-16d
x+9z=4k则ok
x=1 z=3
x=2 z=2
y,d的值任取，所以选取最小值1，1
x=1,y=1,z=3,d=1
或x=2,y=1,z=2,d=1
只要这几种tile可以组成一个一边为4的长方形即可
So，the basic unit can be formed by six ways
first way: use four 1*1 tiles -> 4*1 rect
second way: use two 2*2 tiles -> 4*2 rect
third way: use one 4*4 tile -> 4*4 rect
forth way: use onw 2*2 and four 1*1 -> 4*2 rect, the 2*2 one right on the center
fifth way: use onw 2*2 and four 1*1 -> 4*2 rect, the 2*2 one on the one side
sixth way: use onw 2*2 and four 1*1 -> 4*2 rect, the 2*2 one on the the other side
If N could be divided by 4,
assume N = 4*m, m is a integer
for every m, there are (1+ 1+ 1+15) = 18 kinds
so for the whole room, there are 18^m kinds