Resolução de problemas/Integer inquiry

1. O problema.

O problema requer a elaboração de um programa que recebe como entrada, no máximo 100 Inteiros Muito Grandes ("VeryLongIntegers") e não-negativos, sendo que cada um desses números têm até 100 caracteres, e gera como saída a soma de todos esses números listados.

2. Como resolver.

2.1 As restrições.

Neste programa, o maior inteiro que pode ser um valor de entrada é um número com 100 caracteres. Porém, nas linguagens de programação aceitas nas competições, o maior valor positivo que pode ser representado usando um tipo inteiro positivo tem 10 caracteres. Uma forma de resolver esse problema é trabalharmos com a idéia de bignum.

2.2 O que é Bignum.

A idéia de bignum consiste em trabalharmos com uma representação que aceite números tão grandes quanto nós quisermos. Fica óbvio porém, que para isso teremos de usar nas linguagem de programação uma estrutura que permita essa representação. O mais apropriado é usar um vetor de caracteres, ou no caso de C++ a classe string. Porém, isso traz uma consequência. Para relizarmos operações com essas estruturas, teremos que elaborar algoritmos que façam essas operações. Isso é relativamente simples, já que sabemos (desde o ensino fundamental) a seqüência de passos para relizar tais operações. No nosso caso específico, a operação que nos interessa é a soma.

2.3 Soma com bignum.

O programa deverá ter como procedimento básico a soma de dois números como se fosse feita à mão. A soma se inicia da esquerda para a direita, algarismo por algarismo e utilizando o conceito de "vai um" (ou em inglês "carry). Iremos tomar como exemplo a soma de 999999998888 com 999969998788. O primeiro número estará na variável do tipo string string1 e o segundo na variável tipo string string2. Além disso temos a variável tipo string strresult que terá o resultado, e a variável do tipo char carry, que guardará o "vai um".

carry	1	1	1	1	1	1	1	1	1	1	1	1	0
string 1		9	9	9	9	9	9	9	9	8	8	8	8
string 2		9	9	9	9	6	9	9	9	8	7	8	8
strresult	1	9	9	9	9	6	9	9	9	7	6	7	6

Como vemos na figura a variável strresult necessitará ter um tamanho maior do que string1 e string2.

2.4 Detalhes de implementação

Uma opção interessante seria criar em C++ uma função que recebe duas strings e devolve uma string como resultado. Podemos nos utilizar da classe string da stl para manipular mais facilmente os valores. Teríamos então como cabeçalho da função:

string add_bignum(string 1 , string 2);

A figura ilustra a situacao de string1 e string2 do nosso exemplo inicial:

string 1	_	9	9	9	9	9	9	9	9	8	8	8	8
string 2	_	9	9	9	9	6	9	9	9	8	7	8	8

Uma forma de implementar a adição com bignum, tem como primeiro passo declarar a string de retorno, e uma variável que irá armazenar o "vai um" a qual chamaremos de carry (como o carry nunca será um número muito grande, podemos armazenar essa variável com char, com o fim de economizarmos memória). Após isso, temos que inverter as strings. Uma forma de fazer isso, é utilizando um método da biblioteca algorithm da stl chamado reverse, que recebe dois iteradores de um vetor e inverte a ordem dos elementos dele.

 #include <algorithm>
 #include <string>
 string add_bignum(string string1 , string string2){
        string strresult;
        char carry;
        reverse(a.begin(),a.end());
        reverse(b.begin(),b.end());

A figura ilustra a situacao de string1,string2,carry e str_result:

carry	_	_	_	_	_	_	_	_	_	_	_	_	_
string 1		9	9	9	9	9	9	9	9	8	8	8	8
string 2		9	9	9	9	6	9	9	9	8	7	8	8
strresult	_	_	_	_	_	_	_	_	_	_	_	_	_

Após isso, teremos que encontrar qual o número com maior tamanho e qual é esse número. Desta forma iremos saber quantas somas iremos relizar. Assim, ao declararmos o laço for, podemos identificar o ponto de parada. Armazenamos este tamanho numa variavel inteira que chamaremos de max.

 #include <algorithm>
 #include <string>
 string add_bignum(string string1 , string string2){
        string strresult;
        char carry;
        reverse(string1.begin(),string1.end());
        reverse(string2.begin(),string2.end());
        int max = (int)(string1.size() > string2.size()) ? (string1.size()) : (string2.size());

Agora iniciaremos a soma em si. Carregamos carry com o valor 0. Após isso realizamos um laço que vai de 0 até o valor de max. Dentro do laço, criamos duas variaveis auxiliares n1 e n2 que vão receber os valores reais dos caracteres (OBS: No caso de o laço ultrapassar o limite de tamanho de uma string, isso significa que um número tem mais dígitos do que o outro, portanto a soma deve continuar considerando que o valor deste dígito é 0). Para fazermos isso, dizemos que n1 e n2 recebem o caractere na string menos o valor do caractere '0'.

 #include <algorithm>
 #include <string>
 string add_bignum(string string1 , string string2){
        string strresult;
        char carry;
        reverse(string1.begin(),string1.end());
        reverse(string2.begin(),string2.end());
        int max = (int)(string1.size() > string2.size()) ? (string1.size()) : (string2.size());
        carry = 0;
        for (int i = 0; i < max ; i++){
              char n1,n2;
              n1 = (i < (int)string1.size()) ? (string1[i] - '0') : 0;
              n2 = (i < (int)string2.size()) ? (string2[i] - '0') : 0;

Agora temos que colocar a soma desses valores com carry em strresult. Essa soma será armazenada na variável soma. Depois podemos utilizar o método push_back da classe string, que armazena um caractere na primeira posição livre da string, para colocar em strresult o dígito mais a direita da soma Para isso podemos realizar com soma a operação de módulo(%) com o numero 10, que nos resultará no dígito mais a direita. Quanto ao dígito da esquerda, esse será armazenado em carry através de uma divisão do resultado de soma com 10.

 #include <algorithm>
 #include <string>
 string add_bignum(string string1 , string string2){
        string strresult;
        char carry;
        reverse(string1.begin(),string1.end());
        reverse(string2.begin(),string2.end());
        int max = (int)(string1.size() > string2.size()) ? (string1.size()) : (string2.size());
        carry = 0;
        for (int i = 0; i < max ; i++){
              char n1,n2;
              n1 = (i < (int)string1.size()) ? (string1[i] - '0') : 0;
              n2 = (i < (int)string2.size()) ? (string2[i] - '0') : 0;
              strresult.push_back(((n1 + n2 + carry) % 10) + '0');
              carry = (n1 + n2 + carry) / 10;
        }

A figura ilustra a situacao de string1,string2,carry e str_result:

carry	1	1	1	1	1	1	1	1	1	1	1	1	0
string 1		9	9	9	9	9	9	9	9	8	8	8	8
string 2		9	9	9	9	6	9	9	9	8	7	8	8
strresult	1	9	9	9	9	6	9	9	9	7	6	7	6

Depois de realizarmos todas as iterações, pode ser que tenha sobrado algum valor maior do que zero em carry. Por isso, testamos se esse valor, e caso seja maior que zero, ele também é armazenado em strresult. Por fim, invertemos a ordem de strresult retornando a ordem correta do número, e retornamos strresult.

 #include <algorithm>
 #include <string>
 string add_bignum(string string1 , string string2){
        string strresult;
        char carry;
        reverse(string1.begin(),string1.end());
        reverse(string2.begin(),string2.end());
        int max = (int)(string1.size() > string2.size()) ? (string1.size()) : (string2.size());
        carry = 0;
        for (int i = 0; i < max ; i++){
              char n1,n2;
              n1 = (i < (int)string1.size()) ? (string1[i] - '0') : 0;
              n2 = (i < (int)string2.size()) ? (string2[i] - '0') : 0;
              strresult.push_back(((n1 + n2 + carry) % 10) + '0');
              carry = (n1 + n2 + carry) / 10;
        }
        if (carry) strresult.push_back(carry + '0');
        reverse(strresult.begin(),strresult.end());
        return strresult;
 }

A função está pronta.Basta agora aplicá-la no programa, que é relativamente simples.

Contribuído por Ricardo José Sales Júnior - Ciências da Computação - DIMAp - UFRN

Veja este problema em [1]