posts - 183,  comments - 10,  trackbacks - 0

大数乘法,利用字符串数组保持被乘数、乘数和商。
从左到右依次运算,两个循环即可。
在内循环内有
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, 0sizeof (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.html
http://hi.baidu.com/unixfy/blog/item/97b2e4e8fc96883263d09f69.html
posted on 2011-05-16 20:47 unixfy 阅读(372) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理