POJ 2506 Tiling(递归+高精度)

男娘i 2021-11-02 06:30 223阅读 0赞

Tiling

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;5935</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;2893</td> 
  </tr> 
 </tbody> 
</table>

Description

In how many ways can you tile a 2xn rectangle by 2x1 or 2x2 tiles?   
Here is a sample tiling of a 2x17 rectangle.   
![2506_1.jpg][]

Input

Input is a sequence of lines, each line containing an integer number 0 <= n <= 250.

Output

For each line of input, output one integer number in a separate line giving the number of possible tilings of a 2xn rectangle.

Sample Input

2
    8
    12
    100
    200

Sample Output

3
    171
    2731
    845100400152152934331135470251
    1071292029505993517027974728227441735014801995855195223534251

Source

[The UofA Local 2000.10.14][]

解题报告：此题就是求递推式，其实通过前几个的数，很容易推出递推式为F(n) = 2 \* F(n-2) + F(n - 1)；但是最重要的是对大数的处理，我是参考了一下网上的方法，开一个大的数组不断的更新数据，例如：F(6) = 43； F(7) = 85，求F(8)时；让ans\[8\]\[0\] = 2 \* 3 + 5；即 ans\[8\]\[0\] = 2 \* ans\[6\]\[0\] + ans\[7\]\[0\] = 11; 若超过十则用一个数记录超过的部分beyond =  = ans\[8\]\[0\]/10;而ans\[8\]\[0\] = ans\[8\]\[0\] %10;依此类推就可以得出F(8) = 171；注意的是n = 0时应该输出1；

代码如下：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    using namespace std;
    const int N = 260;
    int ans[N][N];//存储每位结果
    int main()
    {
         
    int n, i, j, count, beyond, p;
    while (scanf("%d", &n) != EOF)
        {
         
            memset(ans, 0, sizeof(ans));
            ans[0][0] = 1;//初始化
            ans[1][0] = 1;
            ans[2][0] = 3;
    if (n <= 2)
            {
         
                printf("%d\n", ans[n][0]);
            }
    else
            {
         
                count = 1;
    for (i = 3; i <= n; ++i)
                {
         
                    beyond = 0; //记录是否超过十
                    p = 0;
    for (j = 0; j < count; ++j)
                    {
         
                        p = ans[i - 2][j] * 2 + ans[i - 1][j] + beyond;
                        ans[i][j] = p % 10;
                        beyond = p / 10;
                    }
    if (beyond)//位数增加一位时的处理
                    {
         
                        ans[i][count] = beyond;
                        count ++;
                    }
                }
    for (i = count - 1; i >= 0; --i)
                {
         
                    printf("%d", ans[n][i]);
                }
                printf("\n");
            }
        }
    return 0;
    }

转载于:https://www.cnblogs.com/lidaojian/archive/2012/02/24/2367187.html

[2506_1.jpg]: /images/20211102/2f7c68d8516f4ee49158f84ccf45be22.png
[The UofA Local 2000.10.14]: http://poj.org/searchproblem?field=source&key=The+UofA+Local+2000.10.14