Jump to content

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


Recommended Posts

Posted

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?

Posted

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

Knowledge is free!

Posted (edited)

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 by brunoais
geshi
Posted

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

IRC : sim, é algo que ainda existe >> #p@p
Posted (edited)

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 by polska

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Posted (edited)

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 by thoga31
GeSHi
Posted (edited)

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 by thoga31

Knowledge is free!

Posted (edited)

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 by thoga31

Knowledge is free!

Posted

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

  • Vote 1
IRC : sim, é algo que ainda existe >> #p@p
Posted

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 😉

Posted

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.

IRC : sim, é algo que ainda existe >> #p@p
Posted (edited)

@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 by polska

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Posted

É 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

IRC : sim, é algo que ainda existe >> #p@p
Posted

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..

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Posted

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 ?

IRC : sim, é algo que ainda existe >> #p@p
Posted (edited)

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 by polska

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.