Você está aqui: Cards de Engenharia Civil - Construção Civil |
||
|
||
|
|
||
Java ::: Estruturas de Dados ::: Árvore Binária e Árvore Binária de Busca |
Como percorrer uma árvore binária em Java usando o algorítmo depth-first search (DFS) de forma iterativaQuantidade de visualizações: 1201 vezes |
|
Nesta dica mostrarei como podemos implementar o algorítmo da Busca em Profundidade (DFS, do inglês depth-first search) em Java de forma iterativa, ou seja, sem usar recursão. Não farei a busca, mas sim o percurso, para que você entenda como a lógica dessa busca funciona. Antes de iniciarmos, veja a árvore binária que vamos usar no exemplo: ![]() Note que esta árvore possui seis nós. O nó 5 é o nó raiz, e possui como filhos os nós 4 e 9. O nó 4, por sua vez, possui apenas um filho, o nó 2, ou seja, o filho da esquerda. O nó 9 possui dois filhos: o nó 3 é o filho da esquerda e o nó 12 é o filho da direita. Os filhos da árvore binária que não possuem outros filhos são chamados de folhas. Com a abordagem da busca em profundidade, começamos com o nó raiz e viajamos para baixo em uma única ramificação. Se o nó desejado for encontrado naquela ramificação, ótimo. Do contrário, continuamos subindo e pesquisando por nós não visitados. Esse tipo de busca também tem uma notação big O de O(n). Vamos à implementação? Veja o código para a classe No, que representa um nó na árvore binária:
// implementação da classe No
class No{
public int valor; // o valor do nó
public No esquerdo; // o filho da esquerda
public No direito; // o filho da direita
public No(int valor){
this.valor = valor;
this.esquerdo = null;
this.direito = null;
}
}
Veja agora o código completo para o exemplo. Note que usei uma implementação não-recursiva, na qual todos os nós expandidos recentemente são adicionados a uma pilha, para realizar a exploração. O uso da pilha permite o retrocesso (backtracking) de forma a reiniciarmos o percurso ou busca no próximo nó. Para manter o código o mais simples possível, eu usei a classe Stack do Java, juntamente com seus métodos push() e pop() para simular a pilha. Usei também uma ArrayList para guardar os valores da árvore binária na ordem depth-first. Eis o código:
package estudos;
import java.util.ArrayList;
import java.util.Stack;
// implementação da classe No
class No{
public int valor; // o valor do nó
public No esquerdo; // o filho da esquerda
public No direito; // o filho da direita
public No(int valor){
this.valor = valor;
this.esquerdo = null;
this.direito = null;
}
}
public class Estudos{
public static void main(String[] args){
// vamos criar os nós da árvore
No cinco = new No(5); // será a raiz da árvore
No quatro = new No(4);
No nove = new No(9);
No dois = new No(2);
No tres = new No(3);
No doze = new No(12);
// vamos fazer a ligação entre os nós
cinco.esquerdo = quatro;
cinco.direito = nove;
quatro.esquerdo = dois;
nove.esquerdo = tres;
nove.direito = doze;
// agora já podemos efetuar o percurso depth-first
ArrayList<Integer> valores = percursoDepthFirst(cinco);
System.out.println("Os valores na ordem Depth-First são: " + valores);
}
public static ArrayList<Integer> percursoDepthFirst(No no){
// vamos usar uma ArrayList para retornar os elementos
// na ordem Depth-First
ArrayList<Integer> valores = new ArrayList<>();
// vamos criar uma nova instância de uma pilha
Stack<No> pilha = new Stack<>();
// já vamos adicionar o primeiro nó recebido, que é a raiz
pilha.push(no);
// enquanto a pilha não estiver vazia
while(pilha.size() > 0){
// vamos obter o elemento no topo da pilha
No atual = pilha.pop();
// adicionamos este valor no ArrayList
valores.add(atual.valor);
// vamos colocar o filho direito na pilha
if(atual.direito != null){
pilha.push(atual.direito);
}
// vamos colocar o filho esquerdo na pilha
if(atual.esquerdo != null){
pilha.push(atual.esquerdo);
}
}
return valores; // retorna os valores da árvore
}
}
Ao executarmos este código Java nós teremos o seguinte resultado: Os valores na ordem Depth-First são: [5, 4, 2, 9, 3, 12] Compare estes valores com a imagem vista anteriormente para entender ainda melhor o percurso ou busca Depth-First. |
Ruby ::: Dicas & Truques ::: Arrays e Matrix (Vetores e Matrizes) |
Como retornar o tamanho de um array em Ruby usando a função sizeQuantidade de visualizações: 7393 vezes |
|
Em algumas situações nós precisamos saber como retornar a quantidade de itens em um array Ruby. Para isso nós podemos usar a função size do objeto Array. Veja o exemplo:
# vamos declarar um array com 5 elementos
valores = [3, 6, 78, 32, 1]
# vamos obter o seu tamanho
tamanho = valores.size
# e mostramos o resultado
puts "O array contém #{tamanho} elementos"
Ao executar este código Ruby nós teremos o seguinte resultado: O array contém 5 elementos |
Java ::: Desafios e Lista de Exercícios Resolvidos ::: Java Básico |
Exercício Resolvido de Java - Faça um algoritmo que leia a idade de uma pessoa expressa em anos, meses e dias e mostre-a expressa em diasQuantidade de visualizações: 6830 vezes |
|
Pergunta/Tarefa: Faça um algoritmo que leia a idade de uma pessoa expressa em anos, meses e dias e mostre-a expressa em dias. Leve em consideração o ano com 365 dias e o mês com 30. (Ex: 3 anos, 2 meses e 15 dias = 1170 dias.) Resposta/Solução: Para a entrada do usuário, nós vamos usar um objeto da classe Scanner. Veja a resolução comentada:
package arquivodecodigos;
import java.util.Scanner;
public class Estudos{
public static void main(String args[]){
// vamos usar um objeto Scanner para ler a entrada
// do usuário
Scanner entrada = new Scanner(System.in);
// vamos ler a quantidade de anos
System.out.print("Quantidade de anos: ");
int anos = Integer.parseInt(entrada.nextLine());
// vamos ler a quantidade de meses
System.out.print("Quantidade de meses: ");
int meses = Integer.parseInt(entrada.nextLine());
// vamos ler a quantidade de dias
System.out.print("Quantidade de dias: ");
int dias = Integer.parseInt(entrada.nextLine());
// vamos calcular a quantidade de dias
int quant_dias = (anos * 365) + (meses * 30) + dias;
// e mostramos o resultado
System.out.println("Idade em dias: " + quant_dias);
}
}
Ao executar este código Java nós teremos o seguinte resultado: Quantidade de anos: 3 Quantidade de meses: 2 Quantidade de dias: 15 Idade em dias: 1170 |
VisuAlg ::: Desafios e Lista de Exercícios Resolvidos ::: Arrays e Matrix (Vetores e Matrizes) |
Exercícios Resolvidos de VisuAlg - Como verificar quantas vezes um valor é encontrado em um vetor - Como usar vetores e matrizes em VisuAlgQuantidade de visualizações: 465 vezes |
|
Pergunta/Tarefa: Escreva um programa VisuAlg que declara, constrói e inicializa um vetor de 10 inteiros. Em seguida peça para que o usuário informe um valor a ser pesquisado. Faça uma varredura no vetor e informe quantas vezes o valor pesquisado é encontrado: // declara um vetor de 10 inteiros valores: vetor[1..10] de inteiro Informe um valor: 4 O valor foi encontrado: 3 vezes Informe um valor: 8 O valor foi encontrado: 1 vezes Informe um valor: 3 O valor foi encontrado: 0 vezes Veja a resolução comentada deste exercício usando VisuAlg:
algoritmo "Contar quantas vezes um elemento repete em um vetor"
var
// variáveis usadas na resolução do problema
valores: vetor[1..10] de inteiro
pesquisa, repeticoes, i: inteiro
inicio
// inicializa um vetor de 10 inteiros
valores[1] <- 4
valores[2] <- 21
valores[3] <- 9
valores[4] <- 8
valores[5] <- 12
valores[6] <- 21
valores[7] <- 4
valores[8] <- 4
valores[9] <- 1
valores[10] <- 10
// vamos ler um valor inteiro
escreva("Informe um valor: ")
leia(pesquisa)
// vamos verificar quantas vezes o valor informado está
// contido no vetor
repeticoes <- 0
para i de 1 ate 10 faca
se valores[i] = pesquisa entao
// encontrou? vamos contar esta ocorrência
repeticoes <- repeticoes + 1
fimse
fimpara
// vamos mostrar o resultado
escreva("O valor foi encontrado: ", repeticoes, " vezes")
fimalgoritmo
|
Python ::: Dicas & Truques ::: Lista (List) |
Como excluir e retornar o primeiro item de uma lista Python usando a função pop()Quantidade de visualizações: 7632 vezes |
|
Em algumas situações nós precisamos remover e retornar um determinado elemento de uma list em Python. Para isso nós podemos usar o método pop(), já embutida na linguagem. A função pop(), quando usada sem argumentos, exclui e retorna o último elemento de uma lista. Se fornecido um argumento, a função remove e retorna o elemento no índice indicado. Se o índice informado estiver fora da faixa permitida, um erro do tipo IndexError será retornado. Veja um trecho de código Python no qual removemos e retornamos o primeiro elemento da lista:
def main():
# cria uma lista de inteiros
valores = [4, 23, 7, 1, 0, 54]
# imprime a lista
print(valores)
# remove o primeiro item
valor = valores.pop(0)
print("Item removido:", valor)
# exibe a lista novamente
print(valores)
if __name__== "__main__":
main()
Ao executar este código Python nós teremos o seguinte resultado: [4, 23, 7, 1, 0, 54] Item removido: 4 [23, 7, 1, 0, 54] Experimente rodar esse código e fornecer, por exemplo, o valor 50 para o índice. Você verá o seguinte erro:
Exception has occurred: IndexError
pop index out of range
File "C:\estudos_python\estudos.py",
line 9, in main
valor = valores.pop(90)
File "C:\estudos_python\estudos.py", line
16, in <module>
main()
|
Desafios, Exercícios e Algoritmos Resolvidos de Python |
Veja mais Dicas e truques de Python |
Dicas e truques de outras linguagens |
E-Books em PDF |
||||
|
||||
|
||||
Linguagens Mais Populares |
||||
|
1º lugar: Java |





