最近笔试遇到两道大数值相加的题目,一道声网的,一道趋势科技的,其中趋势科技的要更难一些,因为涉及了小数。在此总结一下。一般来说,我的做法是,将输入用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:
这一题比较繁琐,许多细节需要注意。