boj-1002-A-B Problem 大数加减法

  • Post author:
  • Post category:其他


思路:

常规大数加减法,要考虑输入数字为负数情况。用字符串存储数字,处理时,逆序字符串补0对齐。主要考虑进位和借位。


Problem Id:


2




Submit time:


2012-10-01 17:20:42




User_id:


478




Memory:


144K


Time:


12MS




Language:


G++


Result:


Accepted

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
using namespace std;

char* reverseTolen(char* str, int len, int toLen)
{
	char ch;
	int i=0,j=len-1;
	while(i<j)
	{
		ch = str[i];
		str[i] = str[j];
		str[j] = ch;
		++i;
		--j;
	}

	while(len < toLen)
	{
		str[len] = '0';
		len++;
	}
	str[len] = '\0';
	return str;
}

void calculate(char* a, int aLen, char* b, int bLen, bool positive)
{
	//printf("%s\n%s\n", a,b);
	char* bb = reverseTolen(b, bLen, aLen);
	char* aa = reverseTolen(a,aLen, aLen);
	char cc[102];
	
	for(int i=0; i<aLen; ++i)
	{
		if(aa[i] - bb[i] >= 0)
			cc[i] = aa[i] - bb[i] + 48;
		else
		{
			int j = i+1;
			for(; aa[j]== '0'; ++j)
			{
				aa[j] = '9';
			}
			aa[j]--;
			cc[i] = aa[i] + 10 - bb[i] + 48;
		}
	}

	
	int i=aLen-1;
	for(; i>=0 && cc[i]=='0'; --i);
	if(i<0)
		cout<<'0'<<endl;
	else {
		if(!positive)
			printf("-");
		for(int j=i; j>=0; --j)
			cout<<cc[j];
		cout<<endl;
	}
}

void plusA(char* a, int aLen, char* b, int bLen)
{
	int bigLen = aLen;
	if(bLen > bigLen)
		bigLen = bLen;
	char* bb = reverseTolen(b, bLen, bigLen);
	char* aa = reverseTolen(a,aLen, bigLen);
	char cc[102];
	int carry = 0;
	for(int i=0; i<102;++i)
		cc[i] = '0';

	for(int i=0; i<bigLen; ++i)
	{
		if((aa[i] + bb[i] + carry - 96) <= 9) {
			cc[i] = aa[i] + bb[i] - 48 + carry;
			carry = 0;
		}
		else
		{
			cc[i] = carry + aa[i] + bb[i] - 48 - 10;
			carry = 1;
		}
	}
	if(carry)
	{
		bigLen++;
		cc[bigLen-1] = '1';
	}
	int i=bigLen-1;
	for(; i>=0 && cc[i]=='0'; --i);
	if(i<0)
		cout<<'0'<<endl;
	else {
		for(int j=i; j>=0; --j)
			cout<<cc[j];
		cout<<endl;
	}
}


int main()
{
	char a[102], b[102];
	scanf("%s %s", a, b);
	int alen = strlen(a);
	int blen = strlen(b);
	if(a[0] == '-'&&b[0]!='-')
	{
		printf("-");
		plusA(&a[1], alen-1, b, blen);
	}else if(a[0] != '-' && b[0] =='-')
	{
		plusA(a, alen, &b[1], blen-1);
	}else
	{
		char* bigger = a;
		if(alen < blen)
			bigger = b;
		else if(alen == blen)
		{
			for(int i=0; i<alen; ++i)
				if(a[i] < b[i])
				{
					bigger = b;
					break;
				}else if(a[i] > b[i])
					break;
		}
		if(b[0] == '-' && a[0]=='-') {
			if(bigger == b)
				calculate(&b[1],blen-1, &a[1], alen-1, true);
			else
				calculate(&a[1],alen-1, &b[1], blen-1, false);
		}else {
			if(bigger == b)
				calculate(b,blen, a, alen, false);
			else
				calculate(a,alen, b, blen, true);
		}
	}

	//system("pause");
	return 0;
}







版权声明:本文为NEOMc原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。