题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1023
解题思路:其实就是N个数的出栈入栈。
这道题的难点就是大数运算。跟另外一篇博客一样的思想。
链接:http://blog.csdn.net/kay_zhyu/article/details/8718576
#include <stdio.h> #include<string.h> #define N 101 char f[N + 1][N]; char str[N]; int L[N]; int Mutiply(char *str1, char *str2, char *str) { int i,j; int a,b; int Result[N]; memset(Result,0,sizeof(Result)); for(i = 0; str1[i] != '#'; ++i) { a = (int)(str1[i] - '0'); for(j = 0; str2[j] != '#'; ++j) { b = (int)(str2[j] - '0'); Result[i + j] += a * b; } } j += i - 1; i = 0; //到了最高位,如果不为零,就一直赋值。 for(i = 0; (i < j || Result[i] > 0); ++i) { str[i] = Result[i] % 10 + '0'; Result[i+1] += Result[i] / 10; } str[i] = '#';//加结束标志 return i; } int Add(char *str1, char *str2, char *str) { int i; int a,b; int temp,flag; flag = 0; for(i = 0; (str1[i] != '#' && str2[i] != '#'); ++i) { a = str1[i] - '0'; b = str2[i] - '0'; temp = a + b + flag; flag = temp / 10; str[i] = temp % 10 + '0'; } if(str1[i] != '#') { while(str1[i] != '#') { a = str1[i] - '0'; temp = a + flag; flag = temp / 10; str[i] = temp % 10 + '0'; ++i; } } else if(str2[i] != '#') { while(str2[i] != '#') { b = str2[i] - '0'; temp = b + flag; flag = temp / 10; str[i] = temp % 10 + '0'; ++i; } } if(flag > 0) { str[i++] = flag + '0'; } str[i] = '#'; return i; } //nLen表示所有字符的个数 void Invert(char *str, int nLen) { int i; char temp; for(i = 0; i < (nLen >> 1); ++i) { temp = str[i]; str[i] = str[nLen - i - 1]; str[nLen - i - 1] = temp; } } void Print(char *str, int nLen) { int i; for(i = 0; i < nLen; ++i) { putchar(str[i]); } printf("\n"); } void main() { int n; int nLen; memset(f,0,sizeof(f)); f[0][0] = '1'; f[0][1] = '#'; L[1] = 1; f[1][0] = '1'; f[1][1] = '#'; for(int i = 2; i < N; ++i) { f[i][0] = '#'; f[N][0] = '#'; for(int j = 0; j < i; ++j) { nLen = Mutiply(f[j],f[i - j - 1],str); nLen = Add(str, f[N],f[i]); memcpy(f[N],f[i],(nLen + 2) * sizeof(char)); } memset(f[N],0,(nLen + 2)*sizeof(char)); L[i] = nLen; } for(int i = 2; i < N; ++i) { Invert(f[i],L[i]); } while(scanf("%d",&n) != EOF) { Print(f[n],L[n]); } }