思路: 明显我们要寻找 边长为 n 和边长为 n-1,n-2,n-3..... 的规律, 这样得出一个递推公式就能方便的得出 f(n)(边长为 n 的值)
由于只有两种类型的地板砖, 2*2 1*1, 所以最后加入的一行, 可能是 1*1 的砖块, 也可能是 2*2 砖块的一部分, 所以 f(n) 就和 f(n-1) 和 f(2) 有关
接下来推导:
由数学概论论可知:
两种个情况, 不同情况之间用加号
同一情况下, 的下一步操作的方法数 之间用乘法
1 第 n 行放的是 1*1 的砖块
所以只需要在 f(n-1) 的基础上放即可, 且 1*1 砖块的方法只有一种
2 第 n 行放的是 2*2 砖块的一部分
所以在 f(n-2) 的基础上放即可, 本来有三种的, 但是舍弃 1*1 的情况, 因为和上述情况重复, 2*2 放左边或右边, 两种情况
结论: f(n)=f(n-1)*1+f(n-2)*2
代码:
- #include<iostream>
- #include<cstdio>
- using namespace std;
- int main()
- {
- int c;
- int sch[32];
- sch[1]=1;
- sch[2]=3;
- sch[3]=5;
- for(int i=4;i<31;i++)
- sch[i]=sch[i-1]+sch[i-2]*2;
- cin>>c;
- while(c--)
- {
- int n;
- cin>>n;
- cout<<sch[n]<<endl;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2769391.html