jett Posted September 10, 2013 at 12:12 PM Report #523973 Posted September 10, 2013 at 12:12 PM 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 Posted September 10, 2013 at 12:18 PM Report #523976 Posted September 10, 2013 at 12:18 PM 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!
HappyHippyHippo Posted September 10, 2013 at 01:16 PM Report #523978 Posted September 10, 2013 at 01:16 PM em c não existe "vectores", isso é C++ ... em C existe arrays, força ai e qua<lauer dúvida pergunta IRC : sim, é algo que ainda existe >> #p@p Portugol Plus
jett Posted September 10, 2013 at 01:32 PM Author Report #523982 Posted September 10, 2013 at 01:32 PM (edited) O arquivo de entrada será mais ou menos da seguinte forma: 219841984298617212198419842986172121984198429861721999999999999999999889589256265655198579817598532179173250971935791759759793175987153917357321957932175932175972139857321975932175981739519328579832175987321957132957193275983217597321957193275917295731298579321759832175973219857132987591827598127597321985111111111111111111111111111111111122222222222222222222222222222222222222222233333333333333333333333333333333333333334444444444444444400000000000000000099999999999999999777777777777774444444444448917246219847124921741724871928749821741298479821749827198479847981729847982174981742872198419842986172109867521429089537421685974210895320741075860975241058329714975862974108soma 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 Posted September 10, 2013 at 04:58 PM Report #524012 Posted September 10, 2013 at 04:58 PM 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 Portugol Plus
Rui Carlos Posted September 13, 2013 at 08:26 PM Report #524525 Posted September 13, 2013 at 08:26 PM Por acaso podes usar bibliotecas externas? Rui Carlos Gonçalves
polska Posted September 14, 2013 at 01:40 PM Report #524562 Posted September 14, 2013 at 01:40 PM (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 September 14, 2013 at 01:42 PM by polska Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.
monteiroxxi Posted September 14, 2013 at 07:49 PM Report #524577 Posted September 14, 2013 at 07:49 PM (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 September 14, 2013 at 07:54 PM by thoga31 GeSHi
thoga31 Posted September 14, 2013 at 07:55 PM Report #524578 Posted September 14, 2013 at 07:55 PM (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 September 14, 2013 at 07:56 PM by thoga31 Knowledge is free!
monteiroxxi Posted September 14, 2013 at 08:00 PM Report #524579 Posted September 14, 2013 at 08:00 PM Não sabia desde de já peço as minhas mais sinceras desculpas. 😞
thoga31 Posted September 14, 2013 at 08:02 PM Report #524580 Posted September 14, 2013 at 08:02 PM (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 September 14, 2013 at 08:02 PM by thoga31 Knowledge is free!
HappyHippyHippo Posted September 14, 2013 at 11:01 PM Report #524593 Posted September 14, 2013 at 11:01 PM 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 1 Report IRC : sim, é algo que ainda existe >> #p@p Portugol Plus
monteiroxxi Posted September 15, 2013 at 06:50 AM Report #524607 Posted September 15, 2013 at 06:50 AM 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 Posted September 15, 2013 at 09:10 AM Report #524608 Posted September 15, 2013 at 09:10 AM 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 Portugol Plus
polska Posted September 15, 2013 at 05:38 PM Report #524637 Posted September 15, 2013 at 05:38 PM (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 September 15, 2013 at 05:41 PM by polska Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.
HappyHippyHippo Posted September 15, 2013 at 08:23 PM Report #524648 Posted September 15, 2013 at 08:23 PM É 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 Portugol Plus
polska Posted September 15, 2013 at 09:22 PM Report #524653 Posted September 15, 2013 at 09:22 PM 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.
HappyHippyHippo Posted September 15, 2013 at 09:34 PM Report #524654 Posted September 15, 2013 at 09:34 PM 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 Portugol Plus
polska Posted September 15, 2013 at 10:08 PM Report #524658 Posted September 15, 2013 at 10:08 PM (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 September 15, 2013 at 10:13 PM by polska Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.
Recommended Posts
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 accountSign in
Already have an account? Sign in here.
Sign In Now