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 1, 2  Próximo  
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: Qua Mar 31, 2004 12:25 am    Assunto: Essa é pros feras! (Desafio de programação) Responder com Citação

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

Árvores

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.

Tarefa

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.

Entrada

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.

Exemplo de Entrada

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


Saída
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.

Exemplo de Saída


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)

Restrições

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

Dica: Observem uma propriedade das ávores binárias.
_________________
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: Qua Mar 31, 2004 12:30 am    Assunto: Responder com Citação

Ia esquecendo, podem fazer isso na linguagem que quiserem, mas sinto que quem fizer vai fazer em Delphi... Rolling Eyes 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.
_________________
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
KeitaroSan
Membro Pleno


Registrado em: Domingo, 15 de Fevereiro de 2004
Mensagens: 289
Localiza?: Rio de Janeiro

MensagemEnviada: Qua Mar 31, 2004 11:33 am    Assunto: Responder com Citação

Eu ateh kiria fazeh, mas nom intendi nada Crying or Very sad Crying or Very sad Crying or Very sad
_________________
Cita?:
char* KeitaroSan::GetIcq()
{
return "92197405";
}
Voltar ao Topo
Ver o perfil de Usuários Enviar Mensagem Particular Enviar Email Endereço de AIM MSN Messenger
Lucas Alves Silva
Membro Senior


Registrado em: Segunda-Feira, 21 de Julho de 2003
Mensagens: 2972
Localiza?: Belo Horizonte - MG

MensagemEnviada: Qua Mar 31, 2004 11:38 am    Assunto: Responder com Citação

na verdade o que é isso Beppe, tipo um trabalho de faculdade?
Voltar ao Topo
Ver o perfil de Usuários Enviar Mensagem Particular
oTTo
Membro Senior


Registrado em: Quarta-Feira, 15 de Outubro de 2003
Mensagens: 3094
Localiza?: Olinda-PE

MensagemEnviada: Qua Mar 31, 2004 12:03 pm    Assunto: Responder com Citação

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









Laughing Laughing Laughing
to zuando... no stress.. hehehe.. putz, nao entendi nadica de nada...
_________________
oTTo Mostaert escreveu:
Se o google é por mim, quem será contra mim?
O Google é meu buscador, nada me faltará.

Arrow Blog
Voltar ao Topo
Ver o perfil de Usuários Enviar Mensagem Particular Visitar a homepage do Usuário
Fabio.HC
Membro Senior


Registrado em: Quarta-Feira, 27 de Agosto de 2003
Mensagens: 1143

MensagemEnviada: Qua Mar 31, 2004 12:18 pm    Assunto: Responder com Citação

só entendi até Tarefa,
daí para baixo num entendi mais nada ... Crying or Very sad
_________________
Voltar ao Topo
Ver o perfil de Usuários Enviar Mensagem Particular
Beppe
Membro Senior


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

MensagemEnviada: Qua Mar 31, 2004 12:37 pm    Assunto: Responder com 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? Surprised Com mais tempo eu posto a resposta, é beeeeeeeeeem simples... Cool
_________________
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
KeitaroSan
Membro Pleno


Registrado em: Domingo, 15 de Fevereiro de 2004
Mensagens: 289
Localiza?: Rio de Janeiro

MensagemEnviada: Qua Mar 31, 2004 12:46 pm    Assunto: Responder com Citação

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


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" Razz Razz
_________________
Cita?:
char* KeitaroSan::GetIcq()
{
return "92197405";
}
Voltar ao Topo
Ver o perfil de Usuários Enviar Mensagem Particular Enviar Email Endereço de AIM MSN Messenger
Fabio.HC
Membro Senior


Registrado em: Quarta-Feira, 27 de Agosto de 2003
Mensagens: 1143

MensagemEnviada: Qua Mar 31, 2004 12:51 pm    Assunto: Responder com Citação

Beppe escreveu:
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? Surprised Com mais tempo eu posto a resposta, é beeeeeeeeeem simples... Cool


Não coloca a resposta ainda, deixa eu tentar resolver esta bagaça neste fim de semana.
_________________
Voltar ao Topo
Ver o perfil de Usuários Enviar Mensagem Particular
nildo
Administrador


Registrado em: Segunda-Feira, 3 de Fevereiro de 2003
Mensagens: 3771
Localiza?: Santo André - SP

MensagemEnviada: Qua Mar 31, 2004 1:29 pm    Assunto: Responder com Citação

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


É claro, só se a gente entender Embarassed
_________________
Admin
Biblioteca BmsApiHook - http://www.ProjetoBMS.net/ - 100% Brasileiro, desenvolvido para Borland Delphi.
Voltar ao Topo
Ver o perfil de Usuários Enviar Mensagem Particular Enviar Email Visitar a homepage do Usuário
Paulo_Amorim
Membro Senior


Registrado em: Quarta-Feira, 14 de Janeiro de 2004
Mensagens: 2024
Localiza?: São José dos Campos- SP

MensagemEnviada: Qua Mar 31, 2004 1:42 pm    Assunto: Responder com Citação

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


eu soh nao entendi essa parte Laughing Laughing Laughing Laughing

Nao entendi nada do que foiexplicado!!!
_________________
[]'s
Paulo Amorim
Voltar ao Topo
Ver o perfil de Usuários Enviar Mensagem Particular Enviar Email
Beppe
Membro Senior


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

MensagemEnviada: Qua Mar 31, 2004 5:20 pm    Assunto: Responder com Citação

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?
_________________
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: Qui Abr 01, 2004 1:09 am    Assunto: Responder com Citação

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 Sad
- 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 Smile
_________________
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
Henry
Membro Senior


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

MensagemEnviada: Qui Abr 01, 2004 6:13 pm    Assunto: Responder com Citação

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


To fora.........
_________________
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
Fabio.HC
Membro Senior


Registrado em: Quarta-Feira, 27 de Agosto de 2003
Mensagens: 1143

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

Up.
_________________
Voltar ao Topo
Ver o perfil de Usuários Enviar Mensagem Particular
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 1, 2  Próximo
Página 1 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