大數乘法，利用字符串數組保持被乘數、乘數和商。
從左到右依次運算，兩個循環即可。
在內循環內有
result[i + j + 1] += (lhs[i] - '0') * (rhs[i] - '0');
最高位空著，因為有可能從次高位進過來位。
然后從左往右依次進位。
之后再檢測左邊的最高位是否為 0，若為 0，右移。
將結果轉存。
注意，這里高位一直在最左邊，沒有逆轉。
如果先逆轉，還是從左開始計算，即從最低位開始計算，有 result[i + j] += (lhs[i] - '0') * (rhs[i] - '0');
1 #include <iostream>
2 using namespace std;
3
4 char* bigMultiply(char ret[], char lhs[], char rhs[])
5 {
6 int llen = strlen(lhs), rlen = strlen(rhs);
7 int* result = new int[llen + rlen];
8 int i, j;
9 memset(result, 0, sizeof (int) * (llen + rlen));
10 //for (i = 0; i < llen + rlen; ++i)
11 //{
12 // result[i] = 0;
13 //}
14 for (i = 0; i < llen; ++i)
15 {
16 for (j = 0; j < rlen; ++j)
17 {
18 result[i + j + 1] += (lhs[i] - '0') * (rhs[j] - '0');
19 cout << result[i + j + 1] << endl;
20 }
21 }
22 for (i = llen + rlen - 1; i > 0; --i)
23 {
24 if (result[i] >= 10)
25 {
26 result[i - 1] += result[i] / 10;
27 result[i] %= 10;
28 }
29 }
30 i = 0;
31 while (result[i] == 0)
32 {
33 ++i;
34 }
35 for (j = 0; i < llen + rlen; ++i, ++j)
36 {
37 cout << result[i];
38 ret[j] = result[i] + '0';
39 }
40 cout << endl;
41 ret[j] = '\0';
42 delete [] result;
43 return ret;
44 }
45
46 int main()
47 {
48 char a[1000], b[1000], c[2000];
49 while (cin >> a >> b)
50 {
51 cout << a << " * " << b << " = " << endl;
52 cout << bigMultiply(c, a, b) << endl;
53 }
54 }
http://hi.baidu.com/unixfy/blog/item/d52eb6f600e57a03b17ec513.htmlhttp://hi.baidu.com/unixfy/blog/item/97b2e4e8fc96883263d09f69.html
posted on 2011-05-16 20:47
unixfy 閱讀(383)
評論(0) 編輯 收藏 引用