[Resolvido] Soma e produto de números inteiros positivos de precisão ilimitada.

[jett]

Preciso fazer um programa que efetue a soma e produto de números inteiros positivos de precisão

ilimitada. Por exemplo:

45465435486515344444444444448888888888888888888888865465536543231451423314213423454342314132413

544354431423143421342314234132413243142341231432413421365231654564 +

2564618165313341341343414324132413324134314331433241641321861684654165

A entrada seria dois número grandes, codificados como uma sequência de caracteres, que devem ser lidos de um

arquivo. Cada linha do arquivo contém um número. A terceira linha contém a operação desejada, soma ou produto.

E a saída seria a saída padrão. O resultado não pode ser abreviado ou ser impresso em termos de potência como, por

exemplo, o resultado do enunciado, 4,546543549×10¹⁶⁰.

Pensei em usar vetores para resolver o problema. Mais alguma ideia?

[thoga31]

Para a soma, é relativamente fácil fazer com Strings. Estando nós em C, uma array de inteiros, em que cada elemento é um dígito do número, tornará as coisas mais fáceis.

O produto é um caso mais bicudo, mas exequível com a mesma solução.

Em vez de mandares somar ou multiplicar dois números enormes, simplesmente realizas as operações segundo o algoritmo daquilo a que chamávamos, na escola primária, "a conta em pé". 😉

Exemplo:

 92434
+  5345
-------
 97779

[HappyHippyHippo]

em c não existe "vectores", isso é C++ ... em C existe arrays, força ai e qua<lauer dúvida pergunta

[jett]

O arquivo de entrada será mais ou menos da seguinte forma:

219841984298617212198419842986172121984198429861721999999999999999999889589256265655198579817598532179173250971935791759759793175987153917357321957932175932175972139857321975932175981739519328579832175987321957132957193275983217597321957193275917295731298579321759832175973219857132987591827598127597321985111111111111111111111111111111111122222222222222222222222222222222222222222233333333333333333333333333333333333333334444444444444444400000000000000000099999999999999999777777777777774444444444448917246219847124921741724871928749821741298479821749827198479847981729847982174981742872198419842986172109867521429089537421685974210895320741075860975241058329714975862974108

soma

8174287219841984298617210986752142908953742168597421089532074107586081742872198419842986172109867521429089537421685974210895320741075860817428721984198429861721098675214290895374216859742108953207410758608174287219841984298617210986752142908953742168597421089532074107586081742872198419842986172109867521429089537421685974210895320741075860817428721984198429861721098675214290895374216859742108953207410758608174287219841984298617210986752142908953742168597421089532074107586081742872198419842986172109867521429089537421685974210895320741075860817428721984198429861721098675214290895374216859742108953207410758608174287219841984298617210986752142908953742168597421089532074107586081742872198419842986172109867521429089537421685974210895320741075860111111111111111111111111111111111122222222222222222222222222222222222222222233333333333333333333333333333333333333334444444444444444400000000000000000099999999999999999777777777777774444444444448917246219847124921741724871928749821741298479821749827198479847981729847982174981742872198419842986172109867521429089537421685974210895320741075860975241058329714975862974108

Então terei que diferenciar os números da operação desejada. Como faço essa comparação?

Até agora fiz o seguinte:

#include <stdio.h>
#include <stdlib.h>
int main(){
   int *numero1, numero2, resultado;
  
   numero1 =  malloc(sizeof(int)); //array para armazenar primeiro numero
   numero2 =  malloc(sizeof(int)); //array para armazenar segundo numero
   resultado =  malloc(sizeof(int)); //array para armazenar o resultado
  
   FILE *fp;
  
   fp = fopen("arquivo.in", "r"); //abre o arquivo IN para leitura
  
  
}

Como percorro o arquivo e armazeno o primeiro número, o segundo e faço a verificação da operação desejada?

Edited September 10, 2013 at 05:30 PM by brunoais
geshi

[HappyHippyHippo]

testa o segunite código:

#include <stdio.h>

int main(void) {
 printf("tamanho de um inteiro : %d\n", sizeof(int));
 return 0;
}

depois diz o que achas que acontece com :

malloc(sizeof(int))

segundo, se achas que o que "pretendes" fazer é boa ideia, ficas a saber que é o primero passo para a aplicação simplesmente estoirar à cabeça.

responde a estas três questões:

- quanta memória é necessária para guardar um dos arrays que pretendes criar ?

- quanta memória é necessári para guardar os três arrays

- quanta memória tem o teu computador ?

pois ....

para resolver o teu problema tens duas opções :

- tenta descubrir o tamanho mínimo necessário para os arrays e alocas a memória necessária

- usa streams temporários

[Rui Carlos]

Por acaso podes usar bibliotecas externas?

[polska]

Até agora fiz o seguinte:

#include <stdio.h>
#include <stdlib.h>
int main(){
  int *numero1, numero2, resultado;

  numero1 =  malloc(sizeof(int)); //array para armazenar primeiro numero
  numero2 =  malloc(sizeof(int)); //array para armazenar segundo numero
  resultado =  malloc(sizeof(int)); //array para armazenar o resultado

  FILE *fp;

  fp = fopen("arquivo.in", "r"); //abre o arquivo IN para leitura


}

E atenção numa coisa, apenas o teu numero1 foi declarado como ponteiro, logo vais ter erro ao alocar memória no numero2 e resultado.

Edited September 14, 2013 at 01:42 PM by polska

[monteiroxxi]

Boas,

Durante parte desta tarde debrucei-me sobre o problema aqui exposto e pelo que percebi do problema no ficheiro de texto ter-se-à, sempre, o primeiro número da operação, seguidamente, o tipo de operação a realizar (soma ou produto) e, por fim, o segundo número da operação. Como não foi exposto em nenhuma circunstância considerei que naquele ficheiro apenas se encontra uma única “conta”.

A ideia apresentada por thoga31 de utilizar um mecanismo semelhante aos aprendidos na escola primária é a mais fiável, mas a meu ver existe um pequeno problema que tem de ser resolvido à priori. Como se utilizaram arrays para “emular” os mecanismos referidos é necessário que seja semelhante ao do exemplo abaixo:

a1: [1][3][5][9][4]

a2: [0][0][0][2][1]

ou seja, ter-se-à de ver qual o número maior e preencher de zero as posições do array com índices mais baixos para que o algarismo da unidades de encontre na última posição do array, o das dezenas na antepenúltima posição e assim sucessivamente.

Ainda não tive tempo para concluir a resolução do problema, mas já resolvi o algoritmo para o cálculo da soma. Apresento, então, abaixo o código-fonte realizado.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int digit_to_int(char d)
{
char str[2];
str[0] = d;
str[1] = '\0';
return (int) strtol(str, NULL, 10);
}
void append(char* s, char c)
{
       int len = strlen(s);
       s[len] = c;
       s[len+1] = '\0';
}
int main(){
 char ch, op[10]="";
 int i, i1, i2, dif, dim;

 dif = 0;
 i1 = 0;
 i2 = 0;
 dim = 0;

 FILE *fp;

 fp = fopen("arquivo.in", "r"); //abre o arquivo IN para leitura

 if(fp==NULL) perror("Impossível abrir o ficheiro!!!");
 else {
   while((ch=fgetc(fp))!='\n') i1++;
   while((ch=fgetc(fp))!='\n');
   while((ch=fgetc(fp))!='\n') i2++;
 }

 printf("dif = %i \ti1 = %i \ti2 = %i\n",dif,i1,i2);

 dif = i1 - i2;
 dim = i1 + i2;
 if(i1<i2) i1=i2;
 else i2=i1;

 printf("dif = %i \ti1 = %i \ti2 = %i\n",dif,i1,i2);

 int n1[i1], n2[i2], sum[dim];

 for(i=0;i<i1;i++) {
   n1[i]=0;
   n2[i]=0;
 }

 for(i=0;i<dim;i++) sum[i] = 0;

 printf("n1  = ");
 for(i=0;i<i1;i++) printf("%i",n1[i]);
 printf("\n");

 printf("n2  = ");
 for(i=0;i<i2;i++) printf("%i",n2[i]);
 printf("\n");

 printf("sum = ");
 for(i=0;i<dim;i++) printf("%i",sum[i]);
 printf("\n");

 fseek(fp,0L,SEEK_SET);

 for(i=0;dif<0;i++) dif++;
 printf("i = %i\n",i);
 while((ch=fgetc(fp))!='\n') n1[i++]=digit_to_int(ch);
 while((ch=fgetc(fp))!='\n') append(op, ch);
 for(i=0;dif>0;i++) dif--;
 while((ch=fgetc(fp))!='\n') n2[i++]=digit_to_int(ch);

 if(strcmp(op,"soma")==0){
  printf("A operação é uma soma!!!\n");
  int aux=0, x=0, y=0, z=0;
  dif = abs(dif)+1;
  for(i=i1-1;i>=0;i--) {
   x = n1[i]+n2[i]+aux;
   if(x%10>0){
     y = x%10;
     aux = (x-y)/10;
   }
   else aux = 0;
   z=i+(dim-i1);
   sum[z]=y;
  }
  z=i+(dim-i1);
  if(aux>0) sum[z]=aux;
 }
 else if(strcmp(op,"produto")==0) printf("A operação é uma multiplicação!!!\n");
 else printf("Operação não reconhecida!!!\n");

 printf("n1  = ");
 for(i=0;i<i1;i++) printf("%i",n1[i]);
 printf("\n");

 printf("n2  = ");
 for(i=0;i<i2;i++) printf("%i",n2[i]);
 printf("\n");

 printf("sum = ");
 for(i=0;i<dim;i++) printf("%i",sum[i]);
 printf("\n");

 fclose(fp);
}

Desculpem o código não estar devidamente comentado.

Edited September 14, 2013 at 07:54 PM by thoga31
GeSHi

[thoga31]

A intenção não é resolver o problema pela pessoa, mas sim ajudá-la a encontrar a solução por si mesma!

A política do P@P não é resolver as coisas, é ajudar a resolver as coisas mostrando o caminho e os erros.

"Não dês o peixe, dá a cana e ensina a pescar"

Edited September 14, 2013 at 07:56 PM by thoga31

[monteiroxxi]

Não sabia desde de já peço as minhas mais sinceras desculpas. 😞

[thoga31]

Não faz mal, mas assim ficas a saber. Só assim os membros aprendem a resolver os seus problemas e a ultrapassar as suas dificuldades - mostrando o caminho. 🙂

Edited September 14, 2013 at 08:02 PM by thoga31

[HappyHippyHippo]

Desculpem o código não estar devidamente comentado.

não vou comentar o teu código, só digo que tem uma grande quantidade de coisas desnecessárias.

vou somente aproveitar o caso de que o código de leitura dos ficheiro já foi apresentado, logo também irei apresentar duas soluções.

a primeira é dentro do modelo usado pelo @meinteiroxxi, isto é, é feita uma leitura inicial do ficheiro para determinar o local dos elementos e depois é feita uma segunda leitura do ficheiro para os ler.

na segunda solução, o ficheiro é lido somente uma vez, onde o número é guardado com o uso inteligente das funções de alocação dinâmica de memória.

#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void) {
   char * n1 = NULL,
        * op = NULL,
        * n2 = NULL;
   size_t state = 0,
          newline1 = 0,
          newline2 = 0,
          newline3 = 0;
   FILE * fd = NULL;
   char c = 0;

   /* abrir o ficheiro */
   if ((fd = fopen("data.bin", "r")) == NULL) {
       fprintf(stderr, "Data file open error : %s\n", strerror(errno));
       return -1;
   }

   /* primeira passagem do ficheiro : determinar quando os elmenetos começam e acabam */
   do {
       if ((c = fgetc(fd)) != '\n') {
           switch (state) {
               case 0:
                   newline1++;
                   /* SIM, NÃO TEM BREAK */
               case 1:
                   newline2++;
                   /* SIM, NÃO TEM BREAK */
               case 2:
                   newline3++;
                   /* SIM, NÃO TEM BREAK */
               default:
                   break;
           }
       } else {
           state++;
       }
   } while (c != EOF && state < 3);

   /* alocar memória para guardar os elementos */
   if ((n1 = malloc(newline1 + 1)) == NULL ||
       (op = malloc(newline2 - newline1 + 1)) == NULL ||
       (n2 = malloc(newline3 - newline2 + 1)) == NULL) {
       free(n1);
       free(op);
       free(n2);
       fclose(fd);

       fprintf(stderr, "Error allocating memory : %s\n", strerror(errno));
       return -1;
   }

   /* guardar o primeiro número */
   fseek(fd, 0, SEEK_SET);
   fread(n1, newline1, 1, fd);

   /* guardar o operador */
   fseek(fd, 1, SEEK_CUR);
   fread(op, newline2 - newline1, 1, fd);

   /* guardar o segundo número */
   fseek(fd, 1, SEEK_CUR);
   fread(n2, newline3 - newline2, 1, fd);

   /* fechar o ficheiro */
   fclose(fd);

   /* output */
   printf("%s\n", n1);
   printf("%s\n", op);
   printf("%s\n", n2);

   /* libertar a memória previamente alocada */
   free(n1);
   free(op);
   free(n2);

   return 0;
}

#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZE 1024

int main(void) {
   char * n1 = NULL,
        * op = NULL,
        * n2 = NULL,
        * aux = NULL;
   size_t n1_size = SIZE,
          op_size = SIZE,
          n2_size = SIZE,
          n1_pos = 0,
          op_pos = 0,
          n2_pos = 0;
   size_t state = 0;
   FILE * fd = NULL;
   char c = 0;

   char ** p_n     = &n1;
   size_t * p_size = &n1_size;
   size_t * p_pos  = &n1_pos;

   /* alocar um bloco de memória inicial */
   if ((n1 = malloc(n1_size)) == NULL ||
       (op = malloc(op_size)) == NULL ||
       (n2 = malloc(n1_size)) == NULL) {
       free(n1);
       free(op);
       free(n2);

       fprintf(stderr, "Error allocating memory : %s\n", strerror(errno));
       return -1;
   }

   /* abrir o ficheiro */
   if ((fd = fopen("data.bin", "r")) == NULL) {
       fprintf(stderr, "Data file open error : %s\n", strerror(errno));
       return -1;
   }

   /* ciclo único de leitura do ficheiro */
   do {
       /* ler o caracter e verificar se não é uma alteração de elemento */
       if ((c = fgetc(fd)) != '\n') {
           /* verificar se a memória do elemento já se encontra totalmente cheia */
           if (*p_pos == *p_size) {
               /* duplicar a memória do elemento */
               if ((aux = realloc(*p_n, (*p_size) * 2)) == NULL) {
                   free(n1);
                   free(op);
                   free(n2);
                   fclose(fd);

                   fprintf(stderr, "Error allocating memory : %s\n", strerror(errno));
                   return -1;
               }

               *p_n = aux;
               (*p_size) <<= 1;
           }

           /* verificar se foi o fim do ficheiro */
           if (c != EOF) {
               /* guardar o caracter lido no elemento */
               (*p_n)[(*p_pos)] = c;
           } else {
               /* guardar um valor 0 final (fim da string) */
               (*p_n)[(*p_pos)] = 0;
           }

           (*p_pos)++;
       } else {
           /* no fim de cada elemento guardar o caracter 0 */
           (*p_n)[(*p_pos)] = 0;

           switch (state) {
               case 0:
                   /* passar a usar o elemento operador ao passar para o estado 1 */
                   p_n    = &op;
                   p_size = &op_size;
                   p_pos  = &op_pos;
                   break;
               case 1:
                   /* passar a usar o elemento segundo dígito ao passar para o estado 2 */
                   p_n    = &n2;
                   p_size = &n2_size;
                   p_pos  = &n2_pos;
                   break;
           }
           state++;
       }
   } while (c != EOF && state < 3);

   /* fechar o ficheiro */
   fclose(fd);

   /* output */
   printf("%s\n", n1);
   printf("%s\n", op);
   printf("%s\n", n2);

   /* libertar a memória previamente alocada */
   free(n1);
   free(op);
   free(n2);

   return 0;
}

--------

não vou apresentar o código de fazer as contas, porque sinceramente, não tenho muita consideração por quem não sabe fazer o que se aprende na primária

[monteiroxxi]

não vou apresentar o código de fazer as contas, porque sinceramente, não tenho muita consideração por quem não sabe fazer o que se aprende na primária

Não entendo o teu comentário em relação ao algoritmo para realizar as contas à "moda da primária", a única gaffe que encontrei neste procedimento após uma posteriormete análise encontra-se na condição else que onde se encontra:

else aux = 0;

deveria estar:

else {
 aux = 0;
 y = x;
}

de resto não encontrei mais nada assim de tão grave que merecessem as rudes palavras de @HappyHippyHippo.

No que diz respeito à parte de leitura do ficheiro de texto e alocação de memória dos arrays recolheceu a meo culpa, acrescentando que já não programava em C desde ... deixa cá ver ... junho de 2011 é normal, penso eu, de me ter esquecido de alguma coisas, uma vez que não tenho memória de elefante.

Cumprs 😉

[HappyHippyHippo]

Não entendo o teu comentário em relação ao algoritmo para realizar as contas à "moda da primária"

o comentário sobre a aplicação dos conhecimentos aprendidos na primária era direccionado ao criados do tópico, visto que foi ele que perguntou como se faz o exercício.

[polska]

@Happy, podes-me explicar o uso dos size_t ? (falando do primeiro exemplo)

É que quando fazes o malloc por exemplo para a variável que vai reter a operação, fazes newline2 - newline1 .. Isto deveria dar um número negativo, mas já vi que o size_t é um tipo sem sinal, por isso não estou bem a perceber que resultado vai dar esta operação..

E já agora, com os fseek's estás basicamente a colocar o apontador do ficheiro no local correcto para depois fazer a leitura com o fread certo?

Edited September 15, 2013 at 05:41 PM by polska

[HappyHippyHippo]

É que quando fazes o malloc por exemplo para a variável que vai reter a operação, fazes newline2 - newline1 .. Isto deveria dar um número negativo

porque dizes que vai ser negativo ?

(eu sei porque, mas quero ver se vais lá sozinho)

sim, size_t é um tipo de dados sem sinal, mas não é por isso que o código funciona.

eu uso o size_t para determinar tamanhos dos arrays por duas razões. sim, uma delas é por não ter sinal. a outra é porque o seu tamanho é dependente da máquina onde o códgo é compilado. numa máquina de 32bits, o size_t é equivalente a unsigned int, quando é 64bits, é equivalente a unsinged long long.

E já agora, com os fseek's estás basicamente a colocar o apontador do ficheiro no local correcto para depois fazer a leitura com o fread certo?

sim, correcto

[polska]

porque dizes que vai ser negativo ?

(eu sei porque, mas quero ver se vais lá sozinho)

Eu digo que vai ser negativo porque, neste caso, o número de dígitos do primeiro número é maior que o número de caracteres da operação a realizar, logo newline2 < newline1... Mas sei que pode ser menor ou igual. Estou um bocado confuso para ser sincero..

[HappyHippyHippo]

Eu digo que vai ser negativo porque, neste caso, o número de dígitos do primeiro número é maior que o número de caracteres da operação a realizar, logo newline2 < newline1... Mas sei que pode ser menor ou igual. Estou um bocado confuso para ser sincero..

isso é porque não estás a ver exactamente o que representa a variável newline1, newline2 e newline3.

essas variáveis representam o índice dos '\n' no ficheiro.

agora, como isso é calculado, é o seguinte código:

switch (state) {
 case 0:
   newline1++;
   /* SIM, NÃO TEM BREAK */
 case 1:
   newline2++;
   /* SIM, NÃO TEM BREAK */
 case 2:
   newline3++;
   /* SIM, NÃO TEM BREAK */
 default:
   break;
}

o "segredo" do código está no comentário

responde a esta pequena questão : porque razão colocar break numa consição do switch ?

[polska]

o "segredo" do código está no comentário

responde a esta pequena questão : porque razão colocar break numa consição do switch ?

Para não continuar a entrar nas restantes opções, pois a pretendida já foi encontrada..

Nem tinha reparado nisso, eu li esses comentários, mas o que pensei logo ao ler esse bloco de código foi que estavas a contar o número de dígitos de cada número e da operação e ao mesmo tempo a verificar se o ficheiro tinha os 3 estados que deve ter, nem reparei na falta de breaks, não foi isso que entendi, impressionante. E não sabia que mesmo sem o break em uma das condições o switch passava por todas as outras condições, eu pensava que ia directo para o default, mas afinal, já aprendi mais alguma coisa !

Pensava que o tipo de dados size_t estava a influenciar o cálculo newline2 - newline1 .. mas afinal.. 😄

Edit: Thanks @Happy 😉

Edited September 15, 2013 at 10:13 PM by polska