51Nod是个好地方啊
题意
51Nod基础题第二题,高精度加法,可能有负数。
解题
如果按照一般的高精度,我们发现要分情况讨论,还要写高精度加法和减法,代码实现有点烦。而初中数学里说,省略加号的和。也就是说,只有加法,没有减法。那么我们又没有办法在做高精度的时候也统一加减法?当然有咯,不然我写这博客干啥
那么到底怎么办呢?
我们还是以加法作为基准,统一加减法。我们知道,减去某个数,就是加上它的相反数。这对于高精度中每一位的操作也是同理。然后我们考虑进位的问题。同样的,我们最后输出每个数位上的数应当在\(0\)到\(9\)之间。这也就是说,我们进位应当是这样的:
a[ i + 1 ] += a[ i ] / 10;a[ i ] %= 10;if( a[ i ] < 0 ) {a[ i ] += 10;--a[ i + 1 ];}
结束了?当然没有!还有一个很大的问题。我们发现,如果结果是个负数,那么首位不论如何都不可能落在\(0\)到\(9\)。这在程序里的表现为是这样的(以\(-1\)举例,从高位到低位):\(-1\), \(9\), \(9\), \(9\), ……
都是进位的锅……
为什么会这样呢?我们了解一下这些数的具体意义。\(-1(-1\times 10^n)\), \(9(9\times 10^{n-1})\), \(9(9\times10^{n-2})\), \(9(9\times10^{n-3})\), …… 加起来确实是\(-1\)。而如果不加处理,直接输出,它的意义就变为了\(-1(-1\times 10^n)\), \(9(-9\times 10^{n-1})\), \(9(-9\times10^{n-2})\), \(9(-9\times10^{n-3})\), ……,也就是\(-19999...\)。
所以呢,我们只需要在负数的时候先输出负号,对每个数位取相反数,再重新进位一遍就好了。
参考程序
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;char ch[ 10010 ];
int a[ 10010 ], b[ 10010 ], la, lb;int main() {scanf( "%s", ch + 1 );if( ch[ 1 ] == '-' ) {la = strlen( ch + 1 ) - 1;for( int i = 2; i <= la + 1; ++i ) a[ la + 1 - i + 1 ] = -( ch[ i ] - '0' );} else {la = strlen( ch + 1 );for( int i = 1; i <= la; ++i ) a[ la - i + 1 ] = ch[ i ] - '0';}scanf( "%s", ch + 1 );if( ch[ 1 ] == '-' ) {lb = strlen( ch + 1 ) - 1;for( int i = 2; i <= lb + 1; ++i ) b[ lb + 1 - i + 1 ] = -( ch[ i ] - '0' );} else {lb = strlen( ch + 1 );for( int i = 1; i <= lb; ++i ) b[ lb - i + 1 ] = ch[ i ] - '0';}//以上是读入la = max( la, lb ) + 1;for( int i = 1; i < la; ++i ) a[ i ] += b[ i ];for( int i = 1; i < la; ++i ) { a[ i + 1 ] += a[ i ] / 10;a[ i ] %= 10;if( a[ i ] < 0 ) {a[ i ] += 10;--a[ i + 1 ];}}while( la > 1 && a[ la ] == 0 ) --la;if( a[ la ] < 0 ) {printf( "-" );for( int i = 1; i <= la; ++i ) a[ i ] = -a[ i ];for( int i = 1; i < la; ++i ) {if( a[ i ] < 0 ) {a[ i ] += 10;--a[ i + 1 ];}}while( la > 1 && a[ la ] == 0 ) --la;for( int i = la; i >= 1; --i ) printf( "%d", a[ i ] );} elsefor( int i = la; i >= 1; --i ) printf( "%d", a[ i ] );printf( "\n" );return 0;
}