骨牌铺方格
time limit: 2000/1000 ms (java/others) memory limit: 65536/32768 k (java/others)total submission(s): 68313 accepted submission(s): 32884
problem description
在2×n的一个长方形方格中,用一个1× 2的骨牌铺满方格,输入n ,输出铺放方案的总数.
例如n=3时,为2× 3方格,骨牌的铺放方案有三种,如下图:
input
输入数据由多行组成,每行包含一个整数n,表示该测试实例的长方形方格的规格是2×n (0<n<=50)。
output
对于每个测试实例,请输出铺放方案的总数,每个实例的输出占一行。
sample input
1 3 2
sample output
1 3 2
典型斐波那契类递归问题(倒着看)
假设2 * n的长方形(除去n = 1;n = 2;的特殊情况,它实际就是2 * (n-1)再加上2 * 1的长方形,以此类推……
代码样例(注意类似斐波那契的数列增长很快,注意数据溢出。这里我留了递归的两种解决方法)
#include <bits/stdc++.h> using namespace std; #define n 50 long long nu[n]={1,2}; //long long arrange(int n) //{ // if(n == 1) // return 1; // if(n == 2) // return 2; // if(n > 2) // return arrange(n-1)+arrange(n-2); //} int main() { int n; while(scanf("%d",&n) != eof) { if(n > 2) { for(int i=2; i < n; i++) nu[i]=nu[i-1]+nu[i-2]; } printf("%lldn",nu[n-1]); // printf("%lldn",arrange(n)); } return 0; }
附:递归问题相关题目
1、 原题 hd2044 一只小蜜蜂…
2、 原题 hd2046 骨牌铺方格
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/605994.html