本文主要是介绍题目1390:矩形覆盖,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
- 题目描述:
-
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?
- 输入:
-
输入可能包含多个测试样例,对于每个测试案例,
输入包括一个整数n(1<=n<=70),其中n为偶数。
- 输出:
-
对应每个测试案例,
输出用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有的方法数。
递推关系:
f(1) = 1;
f(2) = 2;
f(n) = f(n - 1) + f(n - 2);
代码:
#include<stdio.h>
#include<stdlib.h>int main()
{int n;long long int a[71];a[1] = 1;a[2] = 2;for(int i = 3; i < 71; i++)a[i] = a[i - 1] + a[i - 2]; while(scanf("%d",&n) != EOF){printf("%lld\n",a[n]);}
}
这篇关于题目1390:矩形覆盖的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!