logo DevMedia  
Home Entenda o site Revistas Canais Cursos Palestras Suporte Fórum +Serviços Assine Compre Créditos

Edição do Mês
  Fórum DevMedia
Fórum de Discussão
Conheça também o NOVO fórum da DevMedia, no endereço: www.devmedia.com.br/forum
O novo fórum possui diversas vantagens! Saiba mais em
www.devmedia.com.br/articles/viewcomp.asp?comp=14726
Estamos sempre trabalhando na melhora do site como um todo! Bons códigos!
Equipe DevMedia

 FAQFAQ   PesquisarPesquisar   MembrosMembros   GruposGrupos  RegistrarRegistrar   
 PerfilPerfil   Entrar e ver Mensagens ParticularesEntrar e ver Mensagens Particulares   EntrarEntrar 
Edição do Mês

Essa é pros feras! (Desafio de programação)
Ir à página Anterior  1, 2  
Novo Tópico   Responder Mensagem    Fórum DevMedia - Índice do Fórum -> Botequim do Debug
Exibir mensagem anterior :: Exibir próxima mensagem  
Autor Mensagem
Beppe
Membro Senior


Registrado em: Segunda-Feira, 6 de Outubro de 2003
Mensagens: 4219
Localiza?: São Leopoldo, RS

MensagemEnviada: Sáb Abr 03, 2004 6:53 pm    Assunto: Responder com Citação

Amanhã eu coloco a solução entaum, ou hj mais tarde, sei la...
_________________
Glória do Desporto Nacional, ó Internacional...Vamu, vamu Inteeeeeeer, Vamu, vamu Inteeeeeeer!!!!

O nonsense e o abstrato são geniais! (by Humberto Gessinger)

Meu blog: http://www.beppe.theblog.com.br/

You taka my space, I breka your face!
Voltar ao Topo
Ver o perfil de Usuários Enviar Mensagem Particular Visitar a homepage do Usuário
Beppe
Membro Senior


Registrado em: Segunda-Feira, 6 de Outubro de 2003
Mensagens: 4219
Localiza?: São Leopoldo, RS

MensagemEnviada: Sáb Abr 03, 2004 9:45 pm    Assunto: Responder com Citação

Pois bem, aqui está a solução:

C?o:
procedure TTreeTask.Solve;
const
  MaxN = 10000;
var
  TestNumber, N, I: Cardinal;
  ValuesByDepth: array[0..MaxN - 1] of Smallint;
  Value, InsertPos: Cardinal;
  Branch: Integer;
  First: Boolean;
begin
  TestNumber := 1;
  repeat
    // recebe o número de ítems
    N := GetUInt;
    if N = 0 then Exit;
    // inicializa o vetor com flags
    FillChar(ValuesByDepth, SizeOf(ValuesByDepth), -1);

    // para cada elemento
    for I := 1 to N do
    begin
      // lê o valor do ítem
      Value := GetUInt;
      // posição inicial, assume raíz
      InsertPos := 0;

      repeat
        // verifica qual de ramo faz parte
        Branch := GetInt;
        // calcula a próxima posição
        if Branch = -1 then
          // filho esquerdo
          InsertPos := InsertPos * 2 + 1
        else if Branch = 1 then
          // filho direito
          InsertPos := InsertPos * 2 + 2;
      until Branch = 0;

      // insere o item
      ValuesByDepth[InsertPos] := Value;
    end;

    // neste momento todos os nós já foram incluídos no array,
    // nós de um nível sempre aparecendo antes que os do próximo nível

    OutputLn(['Teste ', TestNumber]);
    First := True;
    for I := 0 to MaxN do
    begin
      // testa se o nó existe na árvore
      if ValuesByDepth[I] >= 0 then
      begin
        if First then
          First := False
        else
          OutputText(' ');
        // dá saída do valor
        Output([ValuesByDepth[I]]);
      end;
    end;
    OutputTextLn();
    OutputTextLn();

    Inc(TestNumber);
  until False;
end;


Vou tentar explicar:

O objetivo era ler os dados de entrada e gerar uma lista com os valores na ordem em que os níveis estão dispostos, isto é, o elemento raíz é o primeiro, seguido de seus dois filhos imediatos, os filhos do primeiro filho da raíz, os filhos do segundo, e assim por diante.

A árvore detalhada aqui não contém nada de especial, quando a ordenação e posicionamento de valores, é apenas uma estrutura formada por "nós", os quais contém de 0 a 2 filhos. Exibida, como de costume, com a raíz no topo(nível 0), e níveis posteriores abaixo.

A questão principal era escolher a representação da árvore. Árvores geralmente são implementadas via ponteiros de registros, mas dessa forma, os custos em espaço(na construção), e tempo(na ordenação) seriam maiores. A estrutura concreta em que o problema melhor se beneficiaria é um vetor(array, aqui indexados de 0 a N - 1), onde cada célula correponde a um nó na árvore. A raíz fica na posição zero, seus filhos esquerdo e direito nas posições 1 e 2, respectivamente. Cada nó, exceto a raíz, possui um nó pai, que está na posição chão(p / 2), onde p é a posição do nó na árvore. Os filhos de um nó estarão, se algum, nas posições 2p e 2p + 1.

A árvore linearizada, com o caminho do valor 2 até a raíz, em vermelho:

+-----------------------------------------------------+
| 5 | 4 | 8 | 11 | | 13 | 4 | 7 | 2 | | | | 1 |
+-----------------------------------------------------+
0 1 2 3 4 5 6 7 8 9 10 11 12


Veja que a árvore não está compactada, pois há células vazias, que significam que não há um valor nesta posição na árvore(o nó não possui este filho).

Na implementação, um array[0..N - 1] of Smallint, mantém a árvore, com o valor -1 sendo usado para sinalizar nós não-existentes.

A partir da descrição do caminho do nó até a raíz, é possível realizar a inserção na posição correta. O processo dá-se por calcular a posição relativa do nó, começando da base em direção ao topo(raíz). A posição relativa r é iniciada em 0, e recalculada como 2r + 1 para nós esquerdos(-1), e como 2r + 2 para nós direitos(1). O processo acaba ao chegar na indicação 0, onde o valor é inserido no vetor na posição r.

Por fim, para obter a solução da tarefa, basta percorrer o vetor de 0 a N - 1, escolhendo o valor sempre que for diferente de -1.
_________________
Glória do Desporto Nacional, ó Internacional...Vamu, vamu Inteeeeeeer, Vamu, vamu Inteeeeeeer!!!!

O nonsense e o abstrato são geniais! (by Humberto Gessinger)

Meu blog: http://www.beppe.theblog.com.br/

You taka my space, I breka your face!


Editado pela última vez por Beppe em Dom Abr 04, 2004 7:27 pm, num total de 1 vez
Voltar ao Topo
Ver o perfil de Usuários Enviar Mensagem Particular Visitar a homepage do Usuário
Henry
Membro Senior


Registrado em: Terça-Feira, 11 de Fevereiro de 2003
Mensagens: 2925
Localiza?: Curitiba-PR

MensagemEnviada: Dom Abr 04, 2004 7:20 pm    Assunto: Responder com Citação

mas nem de troco acertava...
_________________
Hora do Cafezinho:= www.horadocafezinho.com/forum/index.php

PBB-Player:= http://pbb-player.sf.net
Voltar ao Topo
Ver o perfil de Usuários Enviar Mensagem Particular Enviar Email Visitar a homepage do Usuário MSN Messenger
pedroso
Membro Junior


Registrado em: Segunda-Feira, 19 de Mai de 2008
Mensagens: 86

MensagemEnviada: Seg Jul 27, 2009 10:14 am    Assunto: Responder com Citação

Eu lembro disto vagamente na facul ...... vou uma daquelas provas acho q de banco de dados 1 .... algo parecido ..... so que na epoca era em assembler
Voltar ao Topo
Ver o perfil de Usuários Enviar Mensagem Particular Enviar Email
Mostrar os tópicos anteriores:   
Novo Tópico   Responder Mensagem    Fórum DevMedia - Índice do Fórum -> Botequim do Debug Todos os horários são GMT - 3 Hours
Ir à página Anterior  1, 2
Página 2 de 2

 
Ir para:  
Enviar Mensagens Novas: Proibído.
Responder Tópicos Proibído
Editar Mensagens: Proibído.
Excluir Mensagens: Proibído.
Votar em Enquetes: Proibído.


Powered by phpBB © 2001, 2005 phpBB Group
Traduzido por: Suporte phpBB