悼念512汶川大地震遇难同胞——重建希望小学

题目

悼念512汶川大地震遇难同胞——重建希望小学

题目大意

学校教室的长度为n米,宽度为3米,现在我们有2种地砖,规格分别是1米*1米,2米*2米,如果要为该教室铺设地砖,请问有几种铺设方式呢?

输入格式

输入数据首先包含一个正整数C,表示包含C组测试用例,然后是C行数据,每行包含一个正整数n(1<=n<=30),表示教室的长度。

输出格式

对于每组测试数据,请输出铺设地砖的方案数目,每个输出占一行。

样例输入

2
2
3

样例输出

3
5

解题思路

排列组合

$$C_{k}^{0}\times{2}^{0}+C_{k-1}^{1}\times{2}^{1}+C_{k-2}^{2}\times{2}^{2}+\cdots+C_{k-k\mid{2}}^{k\mid{2}}\times{2}^{k\mid{2}}$$

在k*3的格子中放n个2*2块有 $C_{k-n}^{n}\times{2}^{n}$ 种方法。对于k*3的格子,至少放0个2*2块,至多放k/2个2*2块。

其中关于 $C_{k-n}^{n}$ 是在1*k的方块中选择n个不相交的1*2方块,可理解为在k-n个1*1方块中选择n个变为1*2方块。

递推一

$${F}_{n}={F}_{n-1}+2\times{F}_{n-2}$$

对于n*3的格子,其铺设方案要么是在(n-1)*3的格子的基础上加1*3个格子(在1*3的格子上铺设方案有1种),要么是在(n-2)*3的格子基础上加2*3个格子(在2*3个格子上铺设方案有3种,但因为用6个1*1块铺设所构成的整体方案其实已经算在(n-1)*3的格子上加1*3格子的方案中了,因此有效方案只有2种)。

递推二

$${F}_{n}=2\times{F}_{n-1}+{\left(-1\right)}^{n}$$

由上式可得

$$
{F}_{n}=2\times{F}_{n-1}+{\left(-1\right)}^{n} \\
{F}_{n-1}=2\times{F}_{n-2}+{\left(-1\right)}^{n-1}
$$

两式相加

$${F}_{n}={F}_{n-1}+2\times{F}_{n-2}+0$$

这回来证明了递推一。

我的代码–排列组合版本

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

unsigned long long J2[30] = {0};

/*V中选N个*/
unsigned long long C(int v,int n)
{

unsigned long long res = 1;
if(n==0) return 1;
for(int i=0; i<n; ++i)
{
res *= v-i;
}
for(int i=2; i<=n; ++i)
{
res /= i;
}
return res;
}
void calc2()
{

J2[0] = 1;
for(int i=1; i<30; ++i)
{
J2[i] = J2[i-1] * 2;
}
}

int main()
{

int k,T;
calc2();
cin >> T;
while(T--)
{
unsigned long long res = 1;
cin >> k;
for(int i=1; i<=k/2; ++i)
res += C(k-i,i)*J2[i];
cout << res << endl;
}
return 0;
}

我的代码–递推版本

#include <iostream>
using namespace std;

int main(void)
{

int n;
int m;
int a[31];
a[1] = 1;
a[2] = 3;
for(n=3; n<31; ++n)
a[n] = a[n-1] + 2*a[n-2];
cin >> n;
while(n--)
{
cin >> m;
cout << a[m] << endl;
}
return 0;
}