51nod 1005 大数加法
前言:不知不觉就已经快要大三了,意识到自身的专业水平还有很大的不足,也该收收心把心思放在学习上了.这是我刷的第一道题,也是我第一次写博客,想通过记录博客的形式记录下自己学习的过程,并督促自己.我的代码还存在很多的问题,我的博客也写的很差,我相信会逐渐好起来的.
题目
我的代码
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
string A,B;
cin>>A>>B;
if(A.size()<=10001||B.size()<=10001) //由于可能存在'-',所以限制字符串A,B的长度小于10001,
{
if(A[0]!='-'&&B[0]!='-') //情况一:当A,B都为正数的时候
{
reverse(A.begin(),A.end()); //反转函数,将A,B反转过来,便于机器进行运算
reverse(B.begin(),B.end());
int n=max(A.size(),B.size()); //最大值函数,取A,B的长度最大值为n
string C(n+1,0); //字符串C用于输出 ,同时多给一位用于进位,且设置每一位为0用于计算
for(int i=0;i<n;i++)
{
int av=0; //av为当前A的值,当i大于 A的长度时为0
if(i<A.size())
{av=A[i]-'0';} //字符串中的数是由ASCII码表示,要减去'0'的ASCII码,在数值上才表示实际数大小
int bv=0;
if(i<B.size())
{bv=B[i]-'0';}
int sum=C[i]+av+bv; //sum用于储存总和,C[i]表示上一位运算中可能存在进位
C[i]=sum; //总和的余数为该位的值
C[i+1]=sum/10; //总和的商为下一位的进位
}
if(C[n]) //一开始字符串C就多给了一位,用以进位,如果该位有进位则输出,没进位则不输出
{
cout<<char(C[n]+'0');
}
for(int k=n-1;k>=0;k--) //将剩下字符串反向输出得到两数相加的和,要注意每一位要加上'0',转化为相应的ASCII码
{
cout<<char(C[k]+'0');
}
}
if(A[0]=='-'&&B[0]=='-') //情况二:当A,B都为负的时候 ,相当于A,B绝对值相加的值的相反数
{
A.erase(0,1); //删除负号
B.erase(0,1); //删除负号
reverse(A.begin(),A.end());
reverse(B.begin(),B.end());
int n=max(A.size(),B.size());
string C(n+1,0);
for(int i=0;i<n;i++)
{
int av=0;
if(i<A.size())
{av=A[i]-'0';}
int bv=0;
if(i<B.size())
{bv=B[i]-'0';}
int sum=C[i]+av+bv;
C[i]=sum;
C[i+1]=sum/10;
}
cout<<'-'; //输出负号
if(C[n])
{
cout<<char(C[n]+'0');
}
for(int k=n-1;k>=0;k--)
{
cout<<char(C[k]+'0');
}
}
if(A[0]=='-'&&B[0]!='-') //情况三:当A为负数,B为正数的时候
{
int flag=0,blag=1; //flag为借位标志位,blag符号标志位
A.erase(0,1); //删除A前面的负号
if(A.size()<B.size()) //当A的长度小于B的长度
{
blag=0; //由于正数大于负数,符号标志位为0,不输出负号
A.swap(B); //swap交换函数,将A和B交换,使位数长的字符串在前
}
if(A.size()==B.size()) //当A的长度等于B的长度
{
if(B>A) //比较A,B字符串的大小,当B大于A时,即正数大于负数时,string字符串比较运算符的比较规则是从低位到高位按ASCII码进行比较
{
B.swap(A); //将B和A交换 ,将大的数放在前面
blag=0; //正数大于负数,不输出负号
}
}
reverse(A.begin(),A.end());
reverse(B.begin(),B.end());
int n=max(A.size(),B.size());
string C(n+1,0);
for(int i=0;i<n;i++)
{
int av=0;
if(i<A.size())
{av=A[i]-'0';}
int bv=0;
if(i<B.size())
{bv=B[i]-'0';}
int sub=av-bv; //sub为A当前值减B当前值
if(sub<0) //如果sub为负数,既需要借位
{
sub+=10; //借位后,sub+10
}
C[i]=sub-flag; //输出字符串C的当前位为sub-上一位的借位
if(C[i]<0) //sub-借位小于0,既当sub=0,上一位有借位时,需要向上借位
{
C[i]+=10; //借位后当前值+10
flag=1; //向上借位,flag=1
continue; //退出本次循环
}
if(av-bv<0) //如果A当前值减B当前值小于0
{
flag=1; //则需要向上借位,flag=1
}
else
{
flag=0; //不需要向上借位,flag=0
}
}
if(blag) //如果标志符号位为1,输出负号
{
cout<<'-';
}
if(C[n]) //进位位,理论上该种情况下可删除
{
cout<<char(C[n]+'0');
}
int cflag=1; //0标志位,用于第一个有意义的数前面是否存在0的检查
for(int k=n-1;k>=0;k--)
{
if(cflag)
{
if(C[k]==0) //如果C当前位为0,跳过该位
{
continue;
}
else //如果检查到当前位不为0,则表示该位为第一位有意义的位,取消检查,进行输出
{
cflag=0; //取消检查
}
}
cout<<char(C[k]+'0'); //输出结果
}
}
if(A[0]!='-'&&B[0]=='-') //情况四:与A为负,B为正情况同理
{
int flag=0,blag=0;
B.erase(0,1);
if(A.size()<B.size()) //负数大于正数
{
blag=1; //输出负号
A.swap(B); //负数在前
}
if(A.size()==B.size()) //位数相同
{
if(B>A) //负数大于正数
{
B.swap(A); //负数在前
blag=1; //输出负号
}
}
reverse(A.begin(),A.end());
reverse(B.begin(),B.end());
int n=max(A.size(),B.size());
string C(n+1,0);
for(int i=0;i<n;i++)
{
int av=0;
if(i<A.size())
{av=A[i]-'0';}
int bv=0;
if(i<B.size())
{bv=B[i]-'0';}
int sub=av-bv;
if(sub<0)
{
sub+=10;
}
C[i]=sub-flag;
if(C[i]<0)
{
C[i]+=10;
flag=1;
continue;
}
if(av-bv<0)
{
flag=1;
}
else
{
flag=0;
}
}
if(blag)
{
cout<<'-';
}
if(C[n])
{
cout<<char(C[n]+'0');
}
int cflag=1;
for(int k=n-1;k>=0;k--)
{
if(cflag)
{
if(C[k]==0)
{
continue;
}
else
{
cflag=0;
}
}
cout<<char(C[k]+'0');
}
}
}
cout<<endl;
return 0;
}
总结
大数加法的实现并不难,难是难在数可能为负数,这其实就相当于大数加法和大数减法的混合,多出了很多情况,会负责很多,我的解题思路很简单粗暴,代码也很长,重复的部分很多,实在很糟糕,我相信经过不断的训练之后,会写出更好的解法.
知识点
#include< algorithm >algorithm意为"算法",是C++的标准模版库（STL）中最重要的头文件之一swap (A,B)algorithm头文件中定义的交换函数, 可以交换存储在两个对象中的值。reverse(first,last)algorithm头文件中定义的反转函数,用于反转在[first,last)范围内的顺序max(A,B)algorithm头文件中定义的最大值函数,A,B可以为整型或浮点型,返回值为A,B中的最大值#include< string >string是C++系统提供的一个类,封装了常用的字符串操作.使用string类型，我们必须包含头文件 < string >。begin()string头文件中定义的 begin()函数返回一个迭代器,指向字符串的第一个元素.end()string头文件中定义的end()函数返回一个迭代器，指向字符串的末尾(最后一个字符的下一个位置).比较运算符(<,=,>)用于string类型的比较运算符,比较规则按从最低位到最高位的ASCII码进行比较size()string头文件中定义的size(),用于string类型,返回string的长度,等同于length()erase(A,B)string头文件中定义的erase(),可以用来删除字符串中的字符,从位置A开始,删除长度B个字符
