首页 > 代码库 > 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(递推+大整数加法)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。