大数运算之字符串模拟

（四）乘法

string?Mul(string&?left,?string&?right)
{
	string?newstr;//创建一个临时sting存放相乘后的结果
	int?lsize?=?left.size();
	int?rsize?=?right.size();
	newstr.resize(lsize?+?rsize);
	int?newsize?=?newstr.size();
	while?(--newsize)//初始化string，如果不初始化，string里存的是‘’
	{
		newstr[newsize]?=?'0';
	}
	if?(left[0]?!=?right[0])//符号不等
	{
		newstr[0]?=?'-';
	}
	else
	{
		newstr[0]?=?'+';
	}
	int?flag?=?0;//标志每次积的最低位
	int?carry?=?0;
	if?(lsize?<=?rsize)
	{
		while?(--lsize)
		{
			newsize?=?newstr.size()?-?flag;
			rsize?=?right.size();
			while?(--rsize)
			{
				char?tmp?=?left[lsize];
				newstr[--newsize]?=?((left[lsize]?-?'0')?*?(right[rsize]?-?'0')
					+?newstr[newsize]-'0')?%?10?+?carry?+?'0';
				carry?=?((tmp?-?'0')?*?(right[rsize]?-?'0'))?/?10;
			}
			newstr[--newsize]?=?carry?+?'0';//把最后的进位存起来
			flag++;
		}
	}
	else
	{
		while?(--rsize)
		{
			newsize?=?newstr.size()?-?flag;
			lsize?=?left.size();
			while?(--lsize)
			{
				char?tmp?=?left[lsize];
				newstr[--newsize]?=?((left[lsize]?-?'0')?*?(right[rsize]?-?'0')
					+?newstr[newsize]?-?'0')?%?10?+?carry?+?'0';
				carry?=?((tmp?-?'0')?*?(right[rsize]?-?'0'))?/?10;
			}
			newstr[--newsize]?=?carry?+?'0';
			flag++;
		}
	}
	return?newstr;
}

? 乘法的话就略微抽象一点，只要把握住一点，保存进位就会非常简单。在写之前应该想清楚的是进位的最大值，乘法中进位的最大值为9，所以也不用考虑空间的问题。最长的字符串完全可以存下来。

?乘法中要注意的是不能破环两个乘数的值，如果修改了会产生意想不到的结果。所以定义一个newstr来存放结果而不像加减法那样直接在最长的串上操作。

（四）除法

string?Div(string&?left,?string&?right)
{
	string?newstr;//创建一个临时sting存放相除后的结果
	int?lsize?=?left.size();
	int?rsize?=?right.size();
	newstr.resize(lsize);
	if?(left[0]?!=?right[0])
	{
		newstr[0]?=?'-';
	}
	else
	{
		newstr[0]?=?'+';
	}
	if?(lsize?<?rsize)
	{
		newstr.push_back('0');
		return?newstr;
	}
	else
	{
		left[0]?=?'+';
		right[0]?=?'+';
		int?i?=?0;
		int?flag?=?rsize;
		int?j?=?0;
		string?tmp;
		tmp.resize(rsize);
		while?(j?<?flag)//将left的高位复制给临时变量
		{
			tmp[j]?=?left[j];
			j++;
		}
		j--;
		while?(j?<?lsize)
		{
			newstr[j]?=?'0';
			while?(Compare(tmp,?right))
			{
				newstr[j]++;
				tmp?=?Sub(tmp,?right);
			}
			tmp.push_back(left[++j]);
		}
		return?newstr;
	}
}

? 除法说难也难，说简单也简单。要想简单的话我们直接用一个循环就可以搞定，循环相减，直到被减数小于减数。但是程序员总是不会屑于写这种效率低到爆的代码的。现在限于个人的知识范围，能想到效率最高的算法就是从被除数字符串截下和除数字符串一样长的字符串相减，使用一个newstr来标记商，newstr长度和被除数长度一样，全部初始化为‘0’。每次在与被除数相同下标的值++。直到被除数小于除数，再将原字符串的下一位push_back()到newstr，重复以上步骤。

?

? 其他函数较为简单，在这就不一一详述了，现在一个字符串模拟大数运算就写好了，可以丢弃手中的科学计算器，让我们的代码跑起来。

（编辑：大连站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!