Jogos troca das bolas

Question

Pessoal preciso de ajuda com um problema, eu sei que se resolve usando arvore mas nesse assunto sou fraco e passei muito tempo sem mexer em java.
preciso ordedar um vetor 000_111, onde eu só posso mover os “0” para direita e os “1” para esquerda.

andangelo · Answer

Eu conseguiu resolver esse problema utilizando um vetor e fazendo pesquisas da esquerda para direita e da direita para esquerda.
Minha duvida é, como fazer a árvore, tipo tenho que fazer a arvote com 000_111, depois o nó esquerdo com 000_111 e verificar se existe 0_ ou 1_, se sim troca se nao ele faz outro nó com o resultado. fazendo isso até que a arvore fique ordenada.

WellingtonRamos · Answer

Por favor, poste o que já fez ou qual a dúvida na implementação.

WellingtonRamos · Answer

Entendi.

Pode-se implementar através de algum algorítmo de ordenação onde o 0 teria peso 1, 1 teria peso 3 e _ teria peso 2. Nesse caso a ordenação seria inversa considerando a entrada 000_111.

Posso até estar enganado mas parece-me um algorítmo de bubble-sort (com algumas diferenças).
Acho que pode considerar uma árvore organizada inicialmente assim:

_
        /   \
      0      1
     /         \
   0            1
  /               \
0                  1

3 Respostas

Topicos relacionados