01 02

Algebra em C/C++ [RESOLVIDO]

1. Algebra em C/C++ [RESOLVIDO]

Nelson_Nunes
(usa Slackware)

Enviado em 18/10/2015 - 16:40h

Olá pessoal estou precisando de umas dicas Estou tentando desenvolver um algoritmo onde terei que somar dez números primos Exemplo: {p1+p2+p3...+p10} = n onde todos primos será inteiros positivos e depois verificar quais foram esses valores somados Exemplo: n= {p1-p2-p3...-p10}

Obs. Terá que ficar na mesma ordem do calculo inicial Exemplo 7+5+3+11...+p10=n

O que não consigo é manter esta Ordem pois sei que a ordem dos fatores não alteram o produto, como contorno esta situação?

1 0

Quote

2. Re: Algebra em C/C++ [RESOLVIDO]

saitam
(usa Slackware)

Enviado em 18/10/2015 - 18:23h

Nelson_Nunes escreveu:

Olá pessoal estou precisando de umas dicas Estou tentando desenvolver um algoritmo onde terei que somar dez números primos Exemplo: {p1+p2+p3...+p10} = n onde todos primos será inteiros positivos e depois verificar quais foram esses valores somados Exemplo: n= {p1-p2-p3...-p10}

Obs. Terá que ficar na mesma ordem do calculo inicial Exemplo 7+5+3+11...+p10=n

O que não consigo é manter esta Ordem pois sei que a ordem dos fatores não alteram o produto, como contorno esta situação?

Utilize um vetor de inteiros e como já tem o tamanho que são "dez números primos", então int primos[10];

Em um laço faz a soma de cada elemento do vetor armazenado.
Veja uma parte da solução abaixo, o resto é com você, OK ?



int soma = 0;

int primos[10];

for(i=0; i<10; i++)

   soma += primos[i];

http://mundodacomputacaointegral.blogspot.com.br/
Twitter: http://twitter.com/@blogcomputacao
Facebook: http://www.facebook.com/BlogComputacao

0 0

Quote

3. Re: Algebra em C/C++

Nelson_Nunes
(usa Slackware)

Enviado em 18/10/2015 - 22:40h

Eu já fiz assim mas não consigo fazer o passo inverso Exemplo:



   #include <stdio.h>

   #define MAX 10



   /*

   *Programa para Calcular a soma de dez primos

   */



int soma_valores(int vetor[]) {

      int soma=0;

      register int i;



       for (i=0;i<MAX;i++){

       soma +=vetor[i];

       }



       return soma;

}





int main(int argc, char *argv[]){



    int vetor[MAX];

    register int i;



    for(i=0;i<MAX; i++){

        printf("Entre com o %d° valor: ", i+1);

        scanf("%d", &vetor[i]);

      }



      printf("\n\nA soma %d", soma_valores(vetor));



    return 0;

}

Agora eu preciso de ajuda (idéia/orientação) em uma função que faca o calculo inverso
Obtendo todo os valores utilizados para o cálculo Exemplo:
Digamos que inseri estes dez valores exatamente nesta ordem abaixo:
1º valor: 5
2º valor: 3
3º valor: 7
4º valor: 17
5º valor: 11
6º valor: 23
7º valor: 29
8º valor: 19
9º valor: 31
10º valor: 41

A Soma e = 186

Como obtenho estes mesmos valores na mesma ordem inserida anteriormente {5, 3, 7, 17, 11, 23, 29, 19, 31, 41}?

0 0

Quote

4. Re: Algebra em C/C++

EnzoFerber
(usa FreeBSD)

Enviado em 19/10/2015 - 09:37h

Bom dia.

Você pode imprimir tais valores utilizando um loop.



for (i = 0; i < MAX; i++)

        printf("Valor %d: %d\n", i + 1, vetor[i]);

Output:



$ make draft

cc     draft.c   -o draft

[ enzo ~ ] $ ./draft

Entre com o 1° valor: 5

Entre com o 2° valor: 3

Entre com o 3° valor: 7

Entre com o 4° valor: 17

Entre com o 5° valor: 11

Entre com o 6° valor: 23

Entre com o 7° valor: 29

Entre com o 8° valor: 19

Entre com o 9° valor: 31

Entre com o 10° valor: 41





A soma 186



Valor 1: 5

Valor 2: 3

Valor 3: 7

Valor 4: 17

Valor 5: 11

Valor 6: 23

Valor 7: 29

Valor 8: 19

Valor 9: 31

Valor 10: 41

$

[]'s
Enzo Ferber



$ cat codigo.c | indent -kr -i8

$ man indent



"(...)all right-thinking people know that (a) K&R are _right_ and (b) K&R are right." - linux/Documentation/CodingStyle - TORVALDS, Linus.

0 0

Quote

5. Re: Algebra em C/C++ [RESOLVIDO]

Nelson_Nunes
(usa Slackware)

Enviado em 19/10/2015 - 10:06h

EnzoFerber escreveu:

Bom dia.

Você pode imprimir tais valores utilizando um loop.



for (i = 0; i < MAX; i++)

        printf("Valor %d: %d\n", i + 1, vetor[i]);

Output:



$ make draft

cc     draft.c   -o draft

[ enzo ~ ] $ ./draft

Entre com o 1° valor: 5

Entre com o 2° valor: 3

Entre com o 3° valor: 7

Entre com o 4° valor: 17

Entre com o 5° valor: 11

Entre com o 6° valor: 23

Entre com o 7° valor: 29

Entre com o 8° valor: 19

Entre com o 9° valor: 31

Entre com o 10° valor: 41





A soma 186



Valor 1: 5

Valor 2: 3

Valor 3: 7

Valor 4: 17

Valor 5: 11

Valor 6: 23

Valor 7: 29

Valor 8: 19

Valor 9: 31

Valor 10: 41

$

[]'s
Enzo Ferber



$ cat codigo.c | indent -kr -i8

$ man indent



"(...)all right-thinking people know that (a) K&R are _right_ and (b) K&R are right." - linux/Documentation/CodingStyle - TORVALDS, Linus.

Minha Dúvida não é como imprimo estes valores.

Minha Dúvida é como obtenho estes valores utilizando um algorítimo de calculo inverso.

0 0

Quote

6. Re: Algebra em C/C++

EnzoFerber
(usa FreeBSD)

Enviado em 19/10/2015 - 10:10h

Qual o algoritmo?

inv(x) = 1/x?

Você obtém os valores na mesma ordem que foram lidos utilizando o mesmo princípio do loop que demonstrei para impressão. Não sei qual o algoritmo você está querendo usar. Seja mais específico. Detalhe o que você precisa fazer.



$ cat codigo.c | indent -kr -i8

$ man indent



"(...)all right-thinking people know that (a) K&R are _right_ and (b) K&R are right." - linux/Documentation/CodingStyle - TORVALDS, Linus.

0 0

Quote

7. Re: Algebra em C/C++ [RESOLVIDO]

Nelson_Nunes
(usa Slackware)

Enviado em 19/10/2015 - 12:54h

EnzoFerber escreveu:

Qual o algoritmo?

inv(x) = 1/x?

Você obtém os valores na mesma ordem que foram lidos utilizando o mesmo princípio do loop que demonstrei para impressão. Não sei qual o algoritmo você está querendo usar. Seja mais específico. Detalhe o que você precisa fazer.



$ cat codigo.c | indent -kr -i8

$ man indent



"(...)all right-thinking people know that (a) K&R are _right_ and (b) K&R are right." - linux/Documentation/CodingStyle - TORVALDS, Linus.

Cara deixei bem claro acima no post que preciso de ideias/sugestões para este algorítimo eu não quero exibir os valores como já mencionei acima quero uma ajuda para chegar a uma formula onde eu com a soma de todos primos obtenho os 10 valores utilizados para chegar a se chegar a soma total

0 0

Quote

8. Re: Algebra em C/C++ [RESOLVIDO]

Nelson_Nunes
(usa Slackware)

Enviado em 19/10/2015 - 12:54h



$ cat codigo.c | indent -kr -i8

$ man indent



"(...)all right-thinking people know that (a) K&R are _right_ and (b) K&R are right." - linux/Documentation/CodingStyle - TORVALDS, Linus.

Cara deixei bem claro acima no post que preciso de ideias/sugestões para este algorítimo eu não quero exibir os valores como já mencionei acima quero uma ajuda para chegar a uma formula onde eu com a soma de todos primos obtenho os 10 valores utilizados para chegar a se chegar a soma total

0 0

Quote

9. Re: Algebra em C/C++

EnzoFerber
(usa FreeBSD)

Enviado em 19/10/2015 - 13:56h

Você quer um algoritmo que te dê 'n' números primos usados para chegar a um valor X?

Isso vai ser brute-force. O problema é que você não consegue "extrair informações" de números, visto que são unidades básicas. Existem n maneiras diferentes para se obter um número X com 'm' fatores.

Em matemática, isso é particionamento: https://en.wikipedia.org/wiki/Partition_(number_theory)
Veja também esta resposta no Math.StackExchange: http://math.stackexchange.com/a/217641/254720

O algortimo vai ser bem complicado, a performance bem lenta e você não vai conseguir exatamente os números que digitou, muito menos na ordem em que os digitou.

O método de Young (descrito no link da Wikipédia) parece ser interessante e mais fácil de implementar.

EDIT:

Soma de 5 números primos para chegar ao número 33.
Eu digitei: {3, 5, 7, 7, 11}.
O computador me diz que é possível fazer com: {7, 7, 7, 7, 5} ou {11, 7, 7, 7, 1}, etc...

EDIT2:

186 = {5, 3, 7, 17, 11, 23, 29, 19, 31, 41};
186 = {19, 19, 19, 19, 19, 19, 19, 19, 17, 17};
...
Usando um brute force numa pequena variação do diagrama de Young.



$ cat codigo.c | indent -kr -i8

$ man indent



"(...)all right-thinking people know that (a) K&R are _right_ and (b) K&R are right." - linux/Documentation/CodingStyle - TORVALDS, Linus.

1 0

Quote

10. Re: Algebra em C/C++ [RESOLVIDO]

Nelson_Nunes
(usa Slackware)

Enviado em 19/10/2015 - 14:39h

EnzoFerber escreveu:

Você quer um algoritmo que te dê 'n' números primos usados para chegar a um valor X?

Isso vai ser brute-force. O problema é que você não consegue "extrair informações" de números, visto que são unidades básicas. Existem n maneiras diferentes para se obter um número X com 'm' fatores.

Em matemática, isso é particionamento: https://en.wikipedia.org/wiki/Partition_(number_theory)
Veja também esta resposta no Math.StackExchange: http://math.stackexchange.com/a/217641/254720

O algortimo vai ser bem complicado, a performance bem lenta e você não vai conseguir exatamente os números que digitou, muito menos na ordem em que os digitou.

O método de Young (descrito no link da Wikipédia) parece ser interessante e mais fácil de implementar.

EDIT:

Soma de 5 números primos para chegar ao número 33.
Eu digitei: {3, 5, 7, 7, 11}.
O computador me diz que é possível fazer com: {7, 7, 7, 7, 5} ou {11, 7, 7, 7, 1}, etc...

EDIT2:

186 = {5, 3, 7, 17, 11, 23, 29, 19, 31, 41};
186 = {19, 19, 19, 19, 19, 19, 19, 19, 17, 17};
...
Usando um brute force numa pequena variação do diagrama de Young.



$ cat codigo.c | indent -kr -i8

$ man indent



"(...)all right-thinking people know that (a) K&R are _right_ and (b) K&R are right." - linux/Documentation/CodingStyle - TORVALDS, Linus.

Muito esclarecedor Ajudou bastante.

0 0

Quote

11. Re: Algebra em C/C++ [RESOLVIDO]

paulo1205
(usa Ubuntu)

Enviado em 19/10/2015 - 14:50h

O mesmo autor da pergunta inicial do tópico já postou um outro tópico sobre particionamento (mas com parcelas que eram meramente números ímpares, não primos).

Acho essa questão de “na mesma ordem” meio inútil. Só se pode saber com certeza a ordem original se ela tiver sido guardada em algum lugar, quer por meio do armazenamento de cada parcela, quer pelo das somas parciais -- o que acaba dando na mesma.

Seria interessante ter acesso ao enunciado original da questão, bem como ao contexto do que o autor do tópico está estudando no momento. Pela outra questão e por esta, ele parece estar mexendo com pilhas ou com recursividade. A resposta “certa” pode ter a ver com o tema sob estudo.

0 0

Quote

12. Re: Algebra em C/C++ [RESOLVIDO]

EnzoFerber
(usa FreeBSD)

Enviado em 19/10/2015 - 15:31h

Olhe o código a seguir. Utilizei um pouco do diagrama de Young como havia dito.
Entretando, possui um sério problema: não identifica quando é impossível fazer uma combinação.

Por exemplo, ele vai entrar em loop infinito se você passar os arguementos 33 e 1 (não há primo que seja 33).
33 e 2 (@paulo1205, há dois primos realmente, mas o programa não calcula - 31 + 2),
etc...

Fica pra você implementar.



/* prime_sum.c

 *

 * Enzo Ferber

 * 2015

 */

#include <stdio.h>

#include <stdlib.h>

#include <unistd.h>

#include <string.h>



#define __INLINE__	__inline__ __attribute__((__always_inline__))



int __INLINE__ is_prime(int n)

{

	int i;



	for (i = 2; i < n; i++)

		if (!(n % i)) return 0;



	return 1;

}



int __INLINE__ next_prime(int prime)

{

	while (!is_prime(++prime)) ;

	return prime;

}



int __INLINE__ prior_prime(int prime)

{

	while(!is_prime(--prime)) ;

	return prime;

}





int *new_array(int sum, int max)

{

	int *p = malloc(max * sizeof *p);

	int prime = 1;

	register int i;



	while ((prime * max) < sum)

		prime = next_prime(prime);



	for (i = 0; i < max; i++) 

		p[ i] = prime;



	return p;



}



int __INLINE__ compute(int *array, int max)

{

	int sum = 0;

	register int i;



	for (i = 0; i < max; i++)

		sum += array[ i];



	return sum;

}



void build_sum_vector(int *array, int sum, int max)

{

	int delta, pp, i, dp;





	delta = *array * max - sum;

	while (delta != 0) {

		for (i = 0; i < max; i++) {

			delta = compute(array, max) - sum;

			pp = prior_prime(array[ i]);

			dp = array[ i] - pp;



			if (dp == delta) {

				array[ i] = pp;

				return ;

			} else if (dp < delta) 

				array[ i] = pp;

			else 

				array[ i] = next_prime(array[ i]);



		}

		delta = compute(array, max) - sum;

	}

}



int main(int argc, char *argv[])

{

	if (argc < 3) return 0;



	int sum = atoi(argv[1]);

	int n = atoi(argv[2]);

	int *array = new_array(sum, n);

	register int i;



	build_sum_vector(array, sum, n);

	for (i = 0; i < n; i++)

		printf("%-5d ", array[ i]);



	putchar('\n');

	return 0;

}

1. A função new_array() cria um vetor com n elementos (definidos pelo usuário) primos cuja soma seja a menor possível menor que a soma total fornecida pelo usuário. Ou seja, caso seja fornecido uma soma 186 e um número total de parcelas 10, o vetor será inicializado com 10 elementos 19. 19 é o menor primo que multiplicado por 10 resultará em na menor soma possível maior que 186. Dessa maneira, construí um quadrado de Young. (bem abstrato, eu sei).

2. A função build_sum_vector() vai começar analisando a diferença entre a soma fornecida pelo usuário e a soma atual dos elementos. Essa diferença eu chamo de DELTA.

3. Enquanto DELTA for diferente de zero ele vai executar o bloco que tenta definir os primos.

4. O loop interno percorre todos os elementos do array. Primeiro, ele recaldula o DELTA, depois acha o primeiro primo abaixo do elemento atual com prior_prime() e calcula a diferença entre os dois. Essa diferença entre o elemento atual e o primo anterior a dele é DELTA_PRIMO.

5. Se o DELTA_PRIMOS for igual ao DELTA, OK!, encontrou uma combinação que satisfaz os critérios definidos pelo usuário.

6. Caso contrário, se DELTA_PRIMOS for menor que DELTA, precisamos reduzir ainda mais nossos elementos, portanto salva-se o resultado e realizamos essas operações denovo (4, 5).
7. Caso o DELTA_PRIMOS seja MAIOR QUE DELTA, precisamos aumentar o número primo atual, e fazemos isso usando next_prime().

--

is_prime, next_prime, prior_prime e compute são bem auto explicativas.

Tenha em mente que esse programa está *LONGE* de ser eficiente.
Apenas pra você ter uma idéia de como pode fazer.

Compilação:



$ CFLAGS=-O3 make prime_sum

$ ./prime_sum 186 10

17 17 19 19 19 19 19 19 19 19

$

Qualquer coisa posta denovo,
Enzo Ferber
[]'s

[]'s



$ cat codigo.c | indent -kr -i8

$ man indent



"(...)all right-thinking people know that (a) K&R are _right_ and (b) K&R are right." - linux/Documentation/CodingStyle - TORVALDS, Linus.

0 0

Quote