Usamos cookies para medir audiência e melhorar sua experiência. Você pode aceitar ou recusar a qualquer momento. Veja sobre o iMasters.
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
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 "-".
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
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!
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.
Realmente, neste caso podemos considerar a raiz como zeroE colocar os filhos 1 e - 1 pra elaAi fica certo :D
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
Realmente, neste caso podemos considerar a raiz como zeroE colocar os filhos 1 e - 1 pra elaAi fica certo :D
Ahh falou o magaiver
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"....
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; } }