写了一个大整数的乘法,使用最笨的算法,数不是十分大时能将就着用:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | #include<iostream> #include <string> #include <fstream> using namespace std; //~ type char To int inline int ctoi(char ch) { return ch - '0'; } //~ 接受两个string因子,返回string乘积 string multiply(const string &l, const string &r) { /* * 两长度分别为lenl,lenr的数相乘,结果长度最大为lenl+lenr, * 最小为lenl+lenr-1 */ size_t lenl = l.size(); size_t lenr = r.size(); unsigned *tmp = new unsigned[lenl + lenr]; memset(tmp, 0, (lenl+lenr)*sizeof(unsigned)); //~ 交叉相乘 for(size_t i = 0; i < lenl; ++i) for(size_t j = 0; j < lenr; ++j) { tmp[i + j + 1] += ctoi(l[i]) * ctoi(r[j]); } //~ 处理进位 for(size_t i = lenl + lenr-1 ; i > 0; --i) { tmp[i - 1] += tmp[i] / 10; tmp[i] = tmp[i] % 10 + '0'; } //~ 将结果转化成string,并返回 if(tmp[0] == 0) return string(tmp+1, tmp + lenl + lenr); //~ 长度为lenl+lenr-1 else tmp[0] += '0'; //~ 长度为lenl+lenr return string(tmp, tmp + lenl + lenr); } int main() { string l, r; while(cin>>l>>r) { cout<<multiply(l, r)<<endl; } return 0; } |
其实,我最初写的不是这样子滴,对比上面的程序,看看下面这个哪里会出问题?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | string multiply(const string &l, const string &r) { size_t lenl = l.size(); size_t lenr = r.size(); string result(lenl+lenr, '\0'); for(size_t i = 0; i < lenl; ++i) for(size_t j = 0; j < lenr; ++j) { result[i + j + 1] += ctoi(l[i]) * ctoi(r[j]); } for(size_t i = lenl + lenr-1 ; i > 0; --i) { result[i - 1] += (unsigned char)result[i] / 10; result[i] = (unsigned char)result[i] % 10 + '0'; } if(result[0] == 0) result.erase(0, 1); else result[0] += '0'; return result; } |
你好!除了代码,此处没有多少原创之物,皆为本人搜集、整理、总结之记录与心得,欢迎转载分享!转载时请尽量注明出处,将不胜感激。祝你健康、快乐!
Be the first to comment on this entry.