hdu1041

#include <iostream> #include <string> using namespace std; const int SIZE = 1001; const int BASE = 10; string result[SIZE]; string two("2"); void initial() { int mcarry, temp, carry; int k; string tempResult; result[1] = "0"; result[2] = "1"; result[3] = "1"; result[4] = "3"; for (int i = 5; i < SIZE; ++i) { mcarry = 0; for (int j = 0; j < two.length(); ++j) /*先做乘法,求出2^(n-3)*/ { temp = 2 * (two[j] - '0') + mcarry; mcarry = temp / BASE; /*乘法进位*/ temp = temp % BASE; tempResult += (temp + '0'); } if (mcarry != 0) /*进位不为0*/ { tempResult += (mcarry + '0'); } two = tempResult; /*存储计算结果*/ tempResult.clear(); int minLength = two.length() > result[i - 2].length() ? result[i - 2].length() : two.length(); carry = 0; for (k = 0; k < minLength; ++k) /*然后做加法f(n) = f(n -2) + 2^(n - 3)*/ { temp = (two[k] - '0') + (result[i - 2][k] - '0') + carry; carry = temp / BASE; /*加法进位*/ temp = temp % BASE; result[i] += (temp + '0'); } /*两个数可能长短不一,所以要比较再相加*/ if (minLength < two.length()) { for(; k < two.length(); k++) { temp = (two[k] - '0') + carry; carry = temp / BASE; temp = temp % BASE; result[i] += (temp + '0'); } } if(minLength < result[i - 2].length()) { for(; k < result[i - 2].length(); ++k) { temp = (result[i - 2][k] - '0') + carry; carry = temp / BASE; temp = temp % BASE; result[i] += (temp + '0'); } } if (carry != 0) /*进位不为0*/ { result[i] += (carry + '0'); } tempResult.clear(); } } int main() { int n; initial(); /*先打表*/ while (scanf ("%d", &n) != EOF) { for(int i = result[n].length(); i > 0; --i) cout << result[n][i - 1]; /*这一步很关键，由于数据是倒着存的,所以要反着输出*/ cout << endl; } system ("pause"); return 0; }