Essa é pros feras! (Desafio de programação)
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,
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.
[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,
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
Curtidas 0
Respostas
Beppe
31/03/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.
GOSTEI 0
Keitarosan
31/03/2004
Eu ateh kiria fazeh, mas nom intendi nada :cry: :cry: :cry:
GOSTEI 0
Lucas Silva
31/03/2004
na verdade o que é isso Beppe, tipo um trabalho de faculdade?
GOSTEI 0
Otto
31/03/2004
ow bipi, ce quer que a gente faça seu trabalho da faculdade, é? :evil:
:lol: :lol: :lol:
to zuando... no stress.. hehehe.. putz, nao entendi nadica de nada...
:lol: :lol: :lol:
to zuando... no stress.. hehehe.. putz, nao entendi nadica de nada...
GOSTEI 0
Fabio.hc
31/03/2004
só entendi até [size=24:441444d5b4]Tarefa[/size:441444d5b4],
daí para baixo num entendi mais nada ... :cry:
daí para baixo num entendi mais nada ... :cry:
GOSTEI 0
Beppe
31/03/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)
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)
GOSTEI 0
Keitarosan
31/03/2004
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
GOSTEI 0
Fabio.hc
31/03/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)
Não coloca a resposta ainda, deixa eu tentar resolver esta bagaça neste fim de semana.
GOSTEI 0
Nildo
31/03/2004
Não coloca a resposta ainda, deixa eu tentar resolver esta bagaça neste fim de semana.
É claro, só se a gente entender :oops:
GOSTEI 0
Paulo_amorim
31/03/2004
árvores são fundamentais em vários ramos
eu soh nao entendi essa parte :lol: :lol: :lol: :lol:
Nao entendi nada do que foiexplicado!!!
GOSTEI 0
Beppe
31/03/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?
Amanhã tô com tempo livre, então vou tentar explicar melhor, flw?
GOSTEI 0
Beppe
31/03/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: :)
- 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: :)
GOSTEI 0
Henry
31/03/2004
- Quem naum sabe (ainda) o que é uma árvore binária(AB), nem adianta tentar resolver
To fora.........
GOSTEI 0
Fabio.hc
31/03/2004
Up.
GOSTEI 0
Beppe
31/03/2004
Amanhã eu coloco a solução entaum, ou hj mais tarde, sei la...
GOSTEI 0
Beppe
31/03/2004
Pois bem, aqui está a solução:
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 [i:0d13be532a]chão(p / 2)[/i:0d13be532a], onde p é a posição do nó na árvore. Os filhos de um nó estarão, se algum, nas posições [i:0d13be532a]2p[/i:0d13be532a] e [i:0d13be532a]2p + 1[/i:0d13be532a].
A árvore linearizada, com o caminho do valor 2 até a raíz, em vermelho:
+-----------------------------------------------------+
| [color=red:0d13be532a]5[/color:0d13be532a] | [color=red:0d13be532a]4[/color:0d13be532a] | 8 | [color=red:0d13be532a]11[/color:0d13be532a] | | 13 | 4 | 7 | [color=red:0d13be532a]2[/color:0d13be532a] | | | | 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 [i:0d13be532a]array[0..N - 1] of Smallint[/i:0d13be532a], 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 [i:0d13be532a]r[/i:0d13be532a] é iniciada em 0, e recalculada como [i:0d13be532a]2r + 1[/i:0d13be532a] para nós esquerdos(-1), e como [i:0d13be532a]2r + 2[/i:0d13be532a] para nós direitos(1). O processo acaba ao chegar na indicação 0, onde o valor é inserido no vetor na posição [i:0d13be532a]r[/i:0d13be532a].
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.
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 [i:0d13be532a]chão(p / 2)[/i:0d13be532a], onde p é a posição do nó na árvore. Os filhos de um nó estarão, se algum, nas posições [i:0d13be532a]2p[/i:0d13be532a] e [i:0d13be532a]2p + 1[/i:0d13be532a].
A árvore linearizada, com o caminho do valor 2 até a raíz, em vermelho:
+-----------------------------------------------------+
| [color=red:0d13be532a]5[/color:0d13be532a] | [color=red:0d13be532a]4[/color:0d13be532a] | 8 | [color=red:0d13be532a]11[/color:0d13be532a] | | 13 | 4 | 7 | [color=red:0d13be532a]2[/color:0d13be532a] | | | | 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 [i:0d13be532a]array[0..N - 1] of Smallint[/i:0d13be532a], 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 [i:0d13be532a]r[/i:0d13be532a] é iniciada em 0, e recalculada como [i:0d13be532a]2r + 1[/i:0d13be532a] para nós esquerdos(-1), e como [i:0d13be532a]2r + 2[/i:0d13be532a] para nós direitos(1). O processo acaba ao chegar na indicação 0, onde o valor é inserido no vetor na posição [i:0d13be532a]r[/i:0d13be532a].
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.
GOSTEI 0
Henry
31/03/2004
mas nem de troco acertava...
GOSTEI 0
Pedroso
31/03/2004
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
GOSTEI 0
Euclides Cunha
31/03/2004
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..
GOSTEI 0
Nigro
31/03/2004
Qual a diferença entre árvore binária, árvore genalógica e pé de mamão?
GOSTEI 0