大数运算之字符串模拟

（四）乘法

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，一再以上步调。

?

? 其他函数较为简朴，在这就纷歧一详述了，此刻一个字符串模仿大数运算就写好了，可以扬弃手中的科学计较器，让我们的代码跑起来。

（编辑：湖南网）

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