学步园

这题很水，但还是写一下。主要是写下怎么找规律

找规律的话，如果有耐心，可以拿只笔一个个的画下（但我不保证不会失误），

另外就是写程序模拟一下。这题用的是dfs

每次添加有3中情况

a) 添加一块2x1的

b) 添加一块2x2的

c) 添加两块2x1的，横放，与3块2x1的区别开

然后搜索，每得到一次结果记录一下。

下面是代码

这里找了前20组，本来想全部找出来的，课程序吃不消

#include <cstdio><br /> __int64 cnt;<br /> int i, j;<br /> void dfs(int sum){<br /> if(sum == i){<br /> cnt++;<br /> return ;<br /> }<br /> if(sum > i)<br /> return ;<br /> for(int k = 1; k <= 3; k++){<br /> if(k == 1)<br /> dfs(sum+1);<br /> else<br /> dfs(sum + 2);<br /> }<br /> }<br /> int main(){<br /> __int64 ans[31];<br /> for(i = 1; i < 20; i++){<br /> cnt = 0;<br /> for(j = 1; j <= 3; j++){<br /> if(j == 1)<br /> dfs(1);<br /> else<br /> dfs(2);<br /> }<br /> ans[i] = cnt;<br /> }<br /> for(i = 1; i < 20; i++)<br /> printf("%I64d/n",ans[i]);<br /> return 0;<br /> }

得出的结果很好判断，ans[i] = ans[i-1]*2 + flag  (flag在-1 和1 之间交替出现)

1<br /> 3<br /> 5<br /> 11<br /> 21<br /> 43<br /> 85<br /> 171<br /> 341<br /> 683<br /> 1365<br /> 2731<br /> 5461<br /> 10923<br /> 21845<br /> 43691<br /> 87381<br /> 174763<br /> 349525<br /> 699051<br /> 1398101<br /> 2796203