自己太笨了,两个大整数相乘也纠结这么久,看了别人的思路才明白过来。
有两个大整数:
an an-1 ... a1 a0和
bm bm-1 ... b1 b0相乘。
则对应结果的第k位就应该是a[i] * a[j] (i + j = k, 0 <= i,j <= k)
不考虑进位的情况下。
所以最后只要从低位往高位进位就解决了。
#include <iostream> #include <string> #include <cstring> #include <algorithm> #include <cstdio> #include <cstdlib> #define N 550 using namespace std; int ans[N]; string s1, s2; int main() { int i, j, n, ls1, ls2, len; while (cin>>s1>>s2) { ls1 = s1.length() - 1; ls2 = s2.length() - 1; len = ls1 + ls2; memset(ans, 0, sizeof(ans)); for (i = ls1; i >= 0; i--) for (j = ls2; j >= 0; j--) { ans[len - (i + j)] += (s1[i] - ‘0‘) * (s2[j] - ‘0‘);//字符串最后一位对应的是个位数 } len++;//结果的位数不超过ls1+ls2-1,从0开始数 for (i = 0; i < len; i++) { ans[i + 1] += ans[i] / 10; ans[i] = ans[i] % 10; } while (!ans[len] && len > 0)//结果最少有ls1+ls2-2位数 len--; for (; len >= 0; len--) cout<<ans[len]; cout<<endl; } return 0; }
原文:http://www.cnblogs.com/jecyhw/p/3669823.html