Obra: Resolução de problemas/Integer inquiry
problema problema requer elaboração de um programa que recebe como entrada no máximo inteiros muito grandes não negativos sendo que cada um desses números têm até caracteres gera como saída soma de todos esses números listados como resolver as restrições neste programa maior inteiro que pode ser um valor de entrada um número com caracteres porém nas linguagens de programação aceitas nas competições maior valor positivo que pode ser representado usando um tipo inteiro positivo tem caracteres uma forma de resolver esse problema trabalharmos com idéia de bignum que bignum 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 mais apropriado usar um vetor de caracteres ou no caso de 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 ensino fundamental seqüência de passos para relizar tais operações no nosso caso específico operação que nos interessa soma soma com bignum programa deverá ter como procedimento básico soma de dois números como se fosse feita mão soma se inicia da esquerda para direita algarismo por algarismo utilizando conceito de vai um ou em inglês carry iremos tomar como exemplo soma de com primeiro número estará na variável do tipo string string segundo na variável tipo string string além disso temos variável tipo string strresult que terá resultado variável do tipo char carry que guardará vai um carry string string strresult como vemos na figura variável strresult necessitará ter um tamanho maior do que string string detalhes de implementação uma opção interessante seria criar em uma função que recebe duas strings 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 string figura ilustra situacao de string string do nosso exemplo inicial string string uma forma de implementar adição com bignum tem como primeiro passo declarar string de retorno uma variável que irá armazenar vai um qual chamaremos de carry como carry nunca será um número muito grande podemos armazenar essa variável com char com 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 inverte ordem dos elementos dele include include string add_bignum string string string string string strresult char carry reverse begin end reverse begin end figura ilustra situacao de string string carry str_result carry string string strresult após isso teremos que encontrar qual número com maior tamanho qual esse número desta forma iremos saber quantas somas iremos relizar assim ao declar
maior tamanho qual esse número desta forma iremos saber quantas somas iremos relizar assim ao declararmos laço for podemos identificar ponto de parada armazenamos este tamanho numa variavel inteira que chamaremos de max include include string add_bignum string string string string string strresult char carry reverse string begin string end reverse string begin string end int max int string size string size string size string size agora iniciaremos soma em si carregamos carry com valor após isso realizamos um laço que vai de até valor de max dentro do laço criamos duas variaveis auxiliares que vão receber os valores reais dos caracteres obs no caso de laço ultrapassar limite de tamanho de uma string isso significa que um número tem mais dígitos do que outro portanto soma deve continuar considerando que valor deste dígito para fazermos isso dizemos que recebem caractere na string menos valor do caractere include include string add_bignum string string string string string strresult char carry reverse string begin string end reverse string begin string end int max int string size string size string size string size carry for int agora temos que colocar soma desses valores com carry em strresult essa soma será armazenada na variável soma depois podemos utilizar método push_back da classe string que armazena um caractere na primeira posição livre da string para colocar em strresult dígito mais direita da soma para isso podemos realizar com soma operação de módulo com numero que nos resultará no dígito mais direita quanto ao dígito da esquerda esse será armazenado em carry através de uma divisão do resultado de soma com include include string add_bignum string string string string string strresult char carry reverse string begin string end reverse string begin string end int max int string size string size string size string size carry for int figura ilustra situacao de string string carry str_result carry string string strresult 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 caso seja maior que zero ele também armazenado em strresult por fim invertemos ordem de strresult retornando ordem correta do número retornamos strresult include include string add_bignum string string string string string strresult char carry reverse string begin string end reverse string begin string end int max int string size string size string size string size carry for int 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