大数相加问题

2,259 阅读4分钟

最近笔试遇到两道大数值相加的题目,一道声网的,一道趋势科技的,其中趋势科技的要更难一些,因为涉及了小数。在此总结一下。一般来说,我的做法是,将输入用string表示,将string的每一位相加。

声网题目

1.题目

输入:
1 5
输出:1+11+111+1111+11111的结果
即输入的第一个数字a在0到9之间,第二个数字n表示由a组成的数字的最高位数

2.思路

这一题最核心的部分是两个字符串相加部分的代码。

情况1:对于长度相等的字符串相加,分为两步:

(1)将两字符串从低位到高位每一位相加
(2)最后如果进位为1,需要将1添加到结果字符串首部

情况2:对于长度相等的字符串相加,分为三步:

(1)对于较短字符串长度的部分,结果的每一位需要由str1和str2以及进位相加获得
(2)对于长字符串比短字符串多出来的一部分,结果的每一位应该由str1(假设str1更长)和进位相加获得
(3)最后如果进位为1,需要将1添加到结果字符串首部

3.代码

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

string sumOfStr(string str1, string str2)
{
	string sum;
	int carry=0;

	int len1 = str1.size();
	int len2 = str2.size();
	int maxlen = max(len1,len2);
	int minlen = min(len1,len2);
	string maxstr = (len1 >= len2) ? str1 : str2;
	//从尾部开始,相加
	for (int i = 0; i < minlen; i++)
	{
		int num1 = str1[len1 - 1 - i]-'0';
		int num2 = str2[len2 - 1 - i]-'0';
		int temp = num1 + num2 + carry;
		if (temp >= 10)
		{
			int remain = temp % 10;
			carry = 1;
			sum.push_back((remain+'0'));
		}
		else
		{
			int remain = temp;
			carry = 0;
			sum.push_back((remain + '0'));
		}
	}
	for (int i = minlen; i < maxlen; i++)
	{
		int num = maxstr[maxlen - 1 - i] - '0';
		int temp = num + carry;
		if (temp >= 10)
		{
			int remain = temp % 10;
			carry = 1;
			sum.push_back((remain + '0'));
		}
		else
		{
			int remain = temp;
			carry = 0;
			sum.push_back((remain + '0'));
		}
	}
	if(carry==1)
		sum.push_back('1');

	reverse(sum.begin(), sum.end());

	return sum;
}

int main()
{
	int a, n;
	cin >> a >> n;
	string add = to_string(a);
	string temp;
	int i = n;
	string sum;
	while (i--)
	{
		temp = temp + add;
		sum = sumOfStr(sum,temp);
	}
	cout << sum << endl;
	return 0;
}

趋势科技题目

1.题目

要求实现两个超长非负数之和,要求:
不损失精度
首位均不出现无意义的0
不出现无意义小数点
不得使用除字符操作之外的函数
输入:
两个非负数,每个数满足:
仅包含0-9的数字,0或1个小数点
长度不大于200
不需判错
输出:
两数之和

2.思路

首先统计下两字符串各自小数部分有几位,如果是整数即为0
将小数部分较小的字符串尾部补0,补两数小数部分长度之差
剔除两个字符串中的小数点
调用上述的字符串相加函数
为结果添加小数点,使得结果的小数部分和之前最长的小数部分一样长
剔除尾部多余的0和小数点的情况

3.代码

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

void deleletTheZeroAndPoint(string & result, int pointLen)
{
	//删除多余的0
	for (int i = 0; i < pointLen; i++)
	{
		if (result[result.size() - 1] != '0')
			break;
		else if (result[result.size() - 1] == '0')
			result.erase(result.end()-1);
	}
	//删除多余的点
	if(result[result.size()-1]=='.')
		result.erase(result.end() - 1);
	return;
}

void renewTheStr(string & str1, string & str2, int pointLen1, int pointLen2)
{
	//添加0
	if (pointLen1 > pointLen2)
	{
		int i = pointLen1 - pointLen2;
		while (i--)
		{
			str2.push_back('0');
		}
	}
	else if (pointLen1 < pointLen2)
	{
		int i = pointLen2 - pointLen1;
		while (i--)
		{
			str1.push_back('0');
		}
	}
	else
		;
	//如果有小数点,去除小数点
	int maxLen = max(pointLen1, pointLen2);
	if (pointLen1 != 0)
		str1.erase(str1.end() - maxLen - 1);
	if (pointLen2 != 0)
		str2.erase(str2.end() - maxLen - 1);
	return;
}

int getThePointBit(string str)//获得两字符串小数部分长度
{
	int len = 0;
	bool signal = false;
	for (int i = 0; i < str.size(); i++)
	{
		if (signal)
			len++;
		if (str[i] == '.')
			signal = true;
	}
	return len;
}

string sumOfStr(string str1, string str2)
{
	string sum;
	int carry=0;

	int len1 = str1.size();
	int len2 = str2.size();
	int maxlen = max(len1,len2);
	int minlen = min(len1,len2);
	string maxstr = (len1 >= len2) ? str1 : str2;
	//从尾部开始,相加
	for (int i = 0; i < minlen; i++)
	{
		int num1 = str1[len1 - 1 - i]-'0';
		int num2 = str2[len2 - 1 - i]-'0';
		int temp = num1 + num2 + carry;
		if (temp >= 10)
		{
			int remain = temp % 10;
			carry = 1;
			sum.push_back((remain+'0'));
		}
		else
		{
			int remain = temp;
			carry = 0;
			sum.push_back((remain + '0'));
		}
	}
	for (int i = minlen; i < maxlen; i++)
	{
		int num = maxstr[maxlen - 1 - i] - '0';
		int temp = num + carry;
		if (temp >= 10)
		{
			int remain = temp % 10;
			carry = 1;
			sum.push_back((remain + '0'));
		}
		else
		{
			int remain = temp;
			carry = 0;
			sum.push_back((remain + '0'));
		}
	}
	if(carry==1)
		sum.push_back('1');

	reverse(sum.begin(), sum.end());

	return sum;
}

int main()
{
	string str1, str2;
	getline(cin, str1);
	getline(cin, str2);
	//获得两字符串小数部分长度
	int pointLen1, pointLen2;
	pointLen1 = getThePointBit(str1);
	pointLen2 = getThePointBit(str2);
	int maxPointLen = max(pointLen1, pointLen2);
	//将小数部分较短的字符尾部补0,并删除两字符串小数点
	renewTheStr(str1,str2,pointLen1,pointLen2);
	//字符串相加
	string result = sumOfStr(str1,str2);
	//添加小数点
	if(maxPointLen != 0)
		result.insert(result.end()-maxPointLen,'.');
	//删除尾部多余的'0'和小数点的情况
	if (maxPointLen != 0)
		deleletTheZeroAndPoint(result,maxPointLen);
	cout << result << endl;
	return 0;
}
测试输入
两个都是整数:

一个整数一个小数:

两个都是小数,尾部没有无用的0:

两个都是小数,尾部有无用的0和点:

两个都是小数,尾部有无用0:

这一题比较繁琐,许多细节需要注意。