首页 > 代码库 > POJ 2506 Tiling(递推+大整数加法)

POJ 2506 Tiling(递推+大整数加法)

http://poj.org/problem?id=2506

题意:
技术分享

 

思路:
递推。a[i]=a[i-1]+2*a[i-2]。

计算的时候是大整数加法。错了好久,忘记考虑1了...晕倒。

 1 #include<iostream> 2 #include<string> 3 #include<cstring> 4 #include<cstdio> 5 using namespace std; 6  7 int n; 8 char s[255][255]; 9 10 void cacl(int i)11 {12     int k;13     int len1 = strlen(s[i - 1]);14     int len2 = strlen(s[i - 2]);15     int flag = 0;16     for (k = 0; k < len2; k++)17     {18         int x = s[i - 1][k] - 0 + 2 * (s[i - 2][k] - 0);19         if (flag)20         {21             x += flag;22             flag = 0;23         }24         if (x>9)25         {26             flag = x / 10;27             x = x % 10;28         }29         s[i][k] = x + 0;30     }31     while (k < len1)32     {33         int x = s[i - 1][k] - 0;34         if (flag)35         {36             x += flag;37             flag = 0;38         }39         if (x>9)40         {41             flag = x / 10;42             x = x % 10;43         }44         s[i][k] = x + 0;45         k++;46     }47     if (flag)  s[i][k] = flag + 0;48 }49 50 void init()51 {52     s[0][0] = 1;53     s[1][0] = 1;54     s[2][0] = 3;55     for (int i = 3; i <= 250; i++)56         cacl(i);57 }58 59 int main()60 {61     init();62     while (cin>>n)63     {64         int m = strlen(s[n]);65         for (int i = m-1; i >= 0; i--)66             cout << s[n][i];67         cout << endl;68     }69 }

 

POJ 2506 Tiling(递推+大整数加法)