写了一个大整数的乘法,使用最笨的算法,数不是十分大时能将就着用:

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;
}
Tags: ,,.
你好!除了代码,此处没有多少原创之物,皆为本人搜集、整理、总结之记录与心得,欢迎转载分享!转载时请尽量注明出处,将不胜感激。祝你健康、快乐!
»
Home

Be the first to comment on this entry.

Name(required)
Mail (required),(will not be published)

RFC: Request For Comments. Orz..

Website(recommended)