DESAFIO: Testar tdas as combinações de sinais de elem. de Array <=

[firemaniaco 0]

Saudações nobres amigos,

 

Vamos combinar: vida de programador não é moleza, né? Que bom que não! :)

 

Bem, criei esse tópico para apresentar-lhes o desafio o proposto pelo meu professor, completamente louco. É seguinte: dado uma Array que poderá conter até 400 elementos - esses serão inicialmente números inteiros positivos -, desenvolver um algoritmo que varre esse Vetor e testa todas as variações de sinais, negativos e positivos, possíveis.

 

Por exemplo, se tivessemos um Array de até 3 elementos, onde A[1] = 1, A[2] = 3 e A[3] = 6, teríamos essas variações de sinais:

A1 + A2 + A3 = 10

A1 + A2 − A3 = −2

A1 − A2 + A3 = 4

A1 − A2 − A3 = −8

−A1 + A2 + A3 = 8

−A1 + A2 − A3 = −4

−A1 − A2 + A3 = 2

−A1 − A2 − A3 = −10

 

Buenas, para 3 elementos é tranquilo até, né? :)

 

Eu tô tentando matar o desafio há cerca de 3 semanas. Até o momento não tenho uma versão final p/ o problema, embora o meu esforço.

 

Está dado o desafio p/ vcs tb, amigos! http://forum.imasters.com.br/public/style_emoticons/default/devil.gif

 

Abraços.

 

Att,

Evandro

[firemaniaco 0]

O meu atual algoritmo, ainda bastante ineficiente p/ um array grande:

 

//MÉTODO: Troca o sinal de todos os elementos p/ positivopublic void trocaSinal(int[] a){	for(int i = 0; i < a.length; i++){		if(a[i]<0){a[i] = a[i]*-1;}	}}	int resultado = 0;int cont = 0;int[] a = new int[400];		//insere valores p/ os elementosa[0] = 1;for(int i = 1; i <= a.length; i++){	a[i] = i; }		//Troca o sinal do primeiro elemento p/ negativoa[0] = a[0]*-1;		//Varia, de um em um, todos os elementos do array p/ negativo uma vezfor(int i = 1; i < a.length; i++){	a[i-1] = a[i-1]*-1;	a[i] = a[i]*-1;}		//Passa o último elemento p/ negativotrocaSinal(a);		//Troca, de um em um, todos os sinais p/ negativofor(int i = 0; i < a.length; i++){	a[i] = a[i]*-1;}		//Passa todos os elementos p/ positivotrocaSinal(a);		//Se o número de elementos for par, troca os sinais das metadesif(a.length%2 == 0){	for(int i = 0; i < a.length/2; i++){		a[i] = a[i]*-1;	}	for(int i = 0; i < a.length; i++){		a[i] = a[i]*-1;		}			}

[Kandrade 7]

Muito bom esse desafio.

Vou te passar a idéia que tive, estou sem tempo pra poder resolver todo ele.

 

Repare que o tamanho do array indica a quantidade de números a ser manipulados.

Imagine isso como um número binário, já que possui dois estados "+" ou "-".

 

- Faça um método que calcule a soma de um array.

- Faça um método que inverta o número, ou seja multiplique por -1.

 

Agora vem a parte mais difícil.

Veja como fica a variação com quatro números.

 

+ + + ++ + + -+ + - ++ + - -+ - + ++ - + -+ - - ++ - - -

O que se percebe é que para 4 número temos 2^4 de possibilidades.

O último bit varia a cada (2^0) interação.

O penultimo bit varia a cada (2 ^ 1) interações.

O anti-penultimo varia a cada (2 ^ 2) interações.

e assim vai.

 

Como podemos usar essa informação?

Bom, temos um método que calcula a soma de um array qualquer e temos um método que troca o sinal de um elemento do array.

Essa informação será usada para informar a esse método quais os sinais a serem modificados.

 

http://forum.imasters.com.br/public/style_emoticons/default/thumbsup.gif

[Rafael D 0]

Olá

Eu pensei em uma coisa diferente do Kandrade, mas acho que funciona.

 

Você já conhece estrutura de dados de árvore?

A ideia seria transformar seu vetor em uma Arvore Binária com a seguinte lógica.

 

Cada nível da árvore terá um elemento do vetor positivo e negativo

Por exemplo, vamos imaginar o vetor 1, 2, 3, 4

 

Sua árvore ficaria assim:

||||||||||||||||||||||||1

|||||||||||+2||||||||||||||||||||-2

|||||+3||||||||-3|||||||||+3|||||||||-3

+4|||-4|||+4|||-4|||+4|||-4|||+4 |||-4

 

Se você analisar a árvore, ela contém todas as variações que você precisa.

Agora, cada vez que você percorrer a árvore da raiz, até uma folha você terá um resultado. Fazendo isso para todas as folhas você terá todas as combinações distintas.

 

 

O problema é a implementação de uma estrutura de árvore do zero, mas acredito que com essa lógica também resolve o problema

Flws!

[Kandrade 7]

Boa Rafael D essa lógica é muito legal.

Ela tem só um problema.

o primeiro elemento sempre será 1 então voce terá as possibilidades / 2

Para funcionar perfeitamente precisa de duas árvores uma que comece com 1 e outra que comece com -1.

[Rafael D 0]

Realmente, neste caso podemos considerar a raiz como zeroE colocar os filhos 1 e - 1 pra elaAi fica certo :D

[Kandrade 7]

Perfeito,muito melhor do que criar duas árvores. :D

Realmente, neste caso podemos considerar a raiz como zeroE colocar os filhos 1 e - 1 pra elaAi fica certo :D

[Serginho Monteiro 0]

Realmente, neste caso podemos considerar a raiz como zeroE colocar os filhos 1 e - 1 pra elaAi fica certo :D

Ahh falou o magaiver

[Pantoja 5]

NOSSA!

 

isso sim é um desafio legal...

 

 

 

nunca usei a arvore apesar de ter ouvido falar dela...

 

 

realmente alguma técnica tem que ter além da "força bruta"....