A39814. 铺砖
填空题
中等
知识点
题目描述
铺砖
题目描述
对于一个2行N列的走道。现在用1 * 2,2 * 2的砖去铺满。问有多少种不同的铺法？
输入格式
整个测试有多组数据，请做到文件结束。每行给出一个数字N，0≤N≤250
输出格式
输入多少行，输出就多少行
每行对应2*n的总铺法
样例输入
2
8
12
100
200
样例输出
3
171
2731
845100400152152934331135470251
1071292029505993517027974728227441735014801995855195223534251
参考答案
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int M = 1005;
const int N = 255;
int a[M][N] = {{0, 0}, {0, 1}, {0, 3}, {0, 5}};
int t[M], cj[M], len[N] = {0, 1, 1, 1}, n;
int main() {
for (int l = 4; l <= N; l++) {
memset(t, 0, sizeof(t));
memset(cj, 0, sizeof(cj)); //数组清空
for (int i = len[l - 2]; i >= 1; i--) {
t[i] = a[l - 2][i];
}
int x;
for (int i = 1; i <= len[l - 2]; i++) {
x = 0;
for (int j = 1; j <= 1; j++) {
cj[i + j - 1] += t[i] * 2 + x;
x = cj[i + j - 1] / 10;
cj[i + j - 1] %= 10;
}
cj[1 + i] = x;
}
int len_s3 = len[l - 2] + 1;
while (cj[len_s3] == 0 and len_s3 > 1) len_s3--;
//有点麻烦，高精度将f(n - 2) * 2;
int len3 = 1;
x = 0;
while (len3 <= len[l - 1] or len3 <= len_s3) {
a[l][len3] = a[l - 1][len3] + cj[len3] + x;
x = a[l][len3] / 10;
a[l][len3] %= 10;
len3++;
}
a[l][len3] = x;
while (a[l][len3] == 0 and len3 > 1)
len3--;
len[l] = len3;//将他们加起来
} //将所有情况储存
while (scanf("%d", &n) != EOF) {
if (n == 0) {
printf("1\n");
continue;
}//特判没有填的--1种
for (int i = len[n]; i >= 1; i--)
printf("%d", a[n][i]);//直接调用
puts("");
}
return 0;
}
上一题
下一题