In how many ways can you tile a 2xn rectangle by 2x1 or 2x2 tiles? Here is a sample tiling of a 2x17 rectangle.
输入
Input is a sequence of lines, each line containing an integer number 0 <= n <= 250.
输出
For each line of input, output one integer number in a separate line giving the number of possible tilings of a 2xn rectangle.
示例输入
2
8
12
100
200
示例输出
3
171
2731
845100400152152934331135470251
1071292029505993517027974728227441735014801995855195223534251
01.#include<stdio.h>
02.#include<
string.h>
03.
int ans[
260][
300];
04.
int main ()
05.{
06.
int n,i,j;
07.
while(~scanf(
"%d",&
n))
08. {
09. memset(ans,
0,
sizeof(ans));
10. ans[
0][
0]=
1;
11. ans[
1][
0]=
1;
12. ans[
2][
0]=
3;
13.
if(n<=
2)
14. printf(
"%d",ans[n][
0]);
15.
else
16. {
17.
18.
int cnt=
1,s;
19.
for(i=
3;i<=n;i++
)
20. {
21.
int beyond=
0;
22.
for(j=
0;j<cnt;j++
)
23. {
24. s=ans[i-
2][j]*
2+ans[i-
1][j]+
beyond;
25. ans[i][j]=s%
10;
26. beyond=s/
10;
27. }
28.
if(beyond)
29. {
30. ans[i][cnt]=
beyond;
31. cnt++
;
32. }
33. }
34.
for(j=cnt-
1;j>=
0;j--
)
35. printf(
"%d",ans[n][j]);
36.
37. }
38. printf(
"\n");
39. }
40.
return 0;
41.}
42.
转载于:https://www.cnblogs.com/LK1994/archive/2013/04/10/3011536.html
