欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

B - Tiling_easy version

程序员文章站 2024-03-17 08:52:28
...

B - Tiling_easy version
这是个递推问题哇~可以得到a[1]=1,a[2]=3。
然后对于i>3来说的话,a[i]可以分成两部分~
第一部分:a[i-1]的情况数量x1(为什么乘1嘞,是因为a[i]比a[i-1]只多了一列,只能竖着放一个2x1的板。)
第二部分:a[i-2]的情况数量x2(为什么乘2嘞,是因为a[i]比a[i-2]多了两列呢,可以竖放2个2x1,横放2个2x1,丢一个2x2。其中竖放2个2x1和第一部分情况重叠了,所以舍弃~)

所以可以得到关系式:a[i]=a[i-1]+a[i-2]x2。

代码部分:

 #include <stdio.h>

int main() {
	int a[31];
	a[1] = 1;
	a[2] = 3;
	for (int i = 3; i <= 30; i++) {
		a[i] = a[i - 1] + 2 * a[i - 2];
	}
	int t;
	scanf("%d", &t);
	while (t--) {
		int n;
		scanf("%d", &n);
		printf("%d\n", a[n]);
	}
	return 0;
}
相关标签: 杂记 c语言