Array
(
)

Essa é pros feras! (Desafio de programação)

Beppe
   - 31 mar 2004

Há um tempo atrás passava o tempo resolvendo problemas como este, se vcs se interessarem, eu posto mais...

[size=24:152145d54f]Árvores[/size:152145d54f]

Como todos vocês devem ter percebido durante o curso, árvores são fundamentais em vários ramos (!) da Computação. Este problema envolve a construção e percurso de árvores binárias.

[size=24:152145d54f]Tarefa[/size:152145d54f]

Dada uma árvore binária, você deve escrever um programa que produza um percurso ´em níveis´. Cada vértice de uma árvore contém um inteiro positivo que identifica o vértice unicamente. Em um percurso em níveis os vértices em um dado nível são visitados da esquerda para a direita, e todos os nós do nível k são visitados antes dos nós do nível k + 1. Por exemplo, para a árvore abaixo,
[img:152145d54f]http://www.afw.hpg.com.br/Contestos/ProvaOBI2000-Fase2-3.gif[/img:152145d54f]
um percurso em nível produz 5, 4, 8, 11, 13, 4, 7, 2, 1.

[size=24:152145d54f]Entrada[/size:152145d54f]

Na entrada uma árvore binária é especificada como uma seqüência de pares (v, p) onde v é o valor do vértice cujo caminho desde a raiz é descrito pelo vetor p. Os elementos de p têm valor 1 ou -1, representanto respectivamente um ramo direito ou um ramo esquerdo. O final do vetor p é indicado por um elemento de valor 0. Na árvore da figura acima, o vértice que contém 13 é especificado por (13, [1, -1, 0]) e o nó que contém 2 é especificado por (2, [-1, -1, 1, 0]). A raiz é especificada por (5, [0]), onde o vetor vazio representa o caminho da raiz até a própria raiz.
A entrada é composta de vários conjuntos de teste. A primeira linha de um conjunto de teste contém um número inteiro positivo N que indica o total de vértices da árvore. As N linhas seguintes contêm cada uma a descriçào de um vértice, no formato descrito acima. O final da entrada é indicado quando N = 0.

[size=24:152145d54f]Exemplo de Entrada[/size:152145d54f]
9
11 -1 -1 0
7 -1 -1 -1 0
8 1 0
5 0
4 -1 0
13 1 -1 0
2 -1 -1 1 0
1 1 1 1 0
4 1 1 0
3
10 0
20 -1 0
30 1 0
0

[size=24:152145d54f]Saída[/size:152145d54f]
Para cada conjunto de teste da entrada seu programa deve produzir três linhas. A primeira linha identifica o conjunto de teste, no formato ´Teste n´, onde n é numerado a partir de 1. A segunda linha deve conter os valores dos vértices na ordem do percurso em nível, conforme determinado pelo seu programa.
A terceira linha deve ser deixada em branco. A grafia mostrada no Exemplo de Saída, abaixo, deve ser seguida rigorosamente.

[size=24:152145d54f]Exemplo de Saída[/size:152145d54f]


Teste 1
5 4 8 11 13 4 7 2 1

Teste 2
10 20 30

(esta saída corresponde ao exemplo de entrada acima)

[size=24:152145d54f]Restrições[/size:152145d54f]

0 ≤ N &8804; 10000 (N = 0 apenas para indicar o fim da
entrada)
0 &8804; valor de um vértice &8804; 10000

Dica: Observem uma propriedade das ávores binárias.


Beppe
   - 31 mar 2004

Ia esquecendo, podem fazer isso na linguagem que quiserem, mas sinto que quem fizer vai fazer em Delphi... :roll: Neste caso pode ser usadas as rotinas Read e Write de System para arquivos TextFile. Pode-se ler e dar saída da tela ou arquivo, como preferir.


Keitarosan
   - 31 mar 2004

Eu ateh kiria fazeh, mas nom intendi nada


Lucas Silva
   - 31 mar 2004

na verdade o que é isso Beppe, tipo um trabalho de faculdade?


Otto
   - 31 mar 2004

ow bipi, ce quer que a gente faça seu trabalho da faculdade, é?









:lol: :lol: :lol:
to zuando... no stress.. hehehe.. putz, nao entendi nadica de nada...


Fabio.hc
   - 31 mar 2004

só entendi até [size=24:441444d5b4]Tarefa[/size:441444d5b4],
daí para baixo num entendi mais nada ...


Beppe
   - 31 mar 2004

AhueaHUAEhAheUAEHauehaUEHaUehAUEHUA xDDDD

ow, na faculdade as coisas são do tipo ´faça um catálogo de CDs´(ao menos no começo...)

Isso é uma tarefa, como, digamos, de gincana, ou olímpiada, só que com o auxílio do computador... :idea:

Mas caras, tá tão difícil assim? :o Com mais tempo eu posto a resposta, é beeeeeeeeeem simples... 8)


Keitarosan
   - 31 mar 2004


Citação:
Mas caras, tá tão difícil assim? :o Com mais tempo eu posto a resposta, é beeeeeeeeeem simples... 8)


Dificil? bom, si eh dificil eu nom sei, afinal nom consegui intendeh ainda T-T
Depois vou reler pela terceira veix pra ve si minha mente si ´alumia´ :P :P


Fabio.hc
   - 31 mar 2004


Citação:
AhueaHUAEhAheUAEHauehaUEHaUehAUEHUA xDDDD

ow, na faculdade as coisas são do tipo ´faça um catálogo de CDs´(ao menos no começo...)

Isso é uma tarefa, como, digamos, de gincana, ou olímpiada, só que com o auxílio do computador... :idea:

Mas caras, tá tão difícil assim? :o Com mais tempo eu posto a resposta, é beeeeeeeeeem simples... 8)


Não coloca a resposta ainda, deixa eu tentar resolver esta bagaça neste fim de semana.


Nildo
   - 31 mar 2004


Citação:
Não coloca a resposta ainda, deixa eu tentar resolver esta bagaça neste fim de semana.


É claro, só se a gente entender :oops:


Paulo_amorim
   - 31 mar 2004


Citação:
árvores são fundamentais em vários ramos


eu soh nao entendi essa parte :lol: :lol: :lol: :lol:

Nao entendi nada do que foiexplicado!!!


Beppe
   - 31 mar 2004

Pô! Vcs naum querem me ajudar com o dever de casa naum? :wink:

Amanhã tô com tempo livre, então vou tentar explicar melhor, flw?


Beppe
   - 01 abr 2004

Gente, os detalhes estão aí em número suficiente, mas em retribuição a disposição de vcs, vou dar mais umas dicas...

- Quem naum sabe (ainda) o que é uma árvore binária(AB), nem adianta tentar resolver :(
- O problema especifíca uma árvore binária apenas, sem nenhuma ordenação
- Escolha a estrutura de dados certa: essa escolha é fundamental, após isso, é sem mistério(a própria escolha é sem mistério)
- Observe as restrições finais, isso ajuda na hora de implementar

Quando a entrada de dados:
- é servido como entrada a descrição de uma AB: o número de nós, seguido da descrição(valor e caminho até a raíz) dos nós, um nó por linha
Por exemplo, o nó (13 1 -1 0), indica que o valor 13 é o filho esquerdo, do filho direito da raíz. (vide figura no topo)

Acho que agora ficou mais claro né? :wink: :)


Henry
   - 01 abr 2004


Citação:
- Quem naum sabe (ainda) o que é uma árvore binária(AB), nem adianta tentar resolver


To fora.........


Fabio.hc
   - 03 abr 2004

Up.


Beppe
   - 03 abr 2004

Amanhã eu coloco a solução entaum, ou hj mais tarde, sei la...


Beppe
   - 03 abr 2004

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

#Código

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.


Henry
   - 04 abr 2004

mas nem de troco acertava...


Pedroso
   - 27 jul 2009

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


Euclides_jc
|
MVP
Pontos: 300
    19 jan 2011

Pode-se tentar fazer este algoritmo de forma diferente, se utilizando do algoritmo de Colônia de Formigas, fazendo a orientação(interação) das formigas por meios dos vértices (coordenadas retangulares) e determinar uma melhor rota da raiz as folhas da árvore. Ficaria interessante tbm.. Para melhorar cada folha pode ser um destino distinto.. assim percorreria várias rotas dentro da mesma árvore..

Nigro
   - 07 jun 2011

Qual a diferença entre árvore binária, árvore genalógica e pé de mamão?