Você está aqui: 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: 714 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: ---------------------------------------------------------------------- Se precisar de ajuda com o código abaixo, pode me chamar no WhatsApp +55 (62) 98553-6711 (Osmar) ---------------------------------------------------------------------- // 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: ---------------------------------------------------------------------- Se precisar de ajuda com o código abaixo, pode me chamar no WhatsApp +55 (62) 98553-6711 (Osmar) ---------------------------------------------------------------------- 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. |
Link para compartilhar na Internet ou com seus amigos: |
Python ::: Tkinter GUI Toolkit ::: Círculos, Ovais e Elípses |
Como desenhar círculos no Tkinter usando a função create_oval() do componente CanvasQuantidade de visualizações: 829 vezes |
Em várias situações nós precisamos desenhar círculos não preenchidos e preenchidos em Tkinter. Para isso nós podemos usar a função create_oval() do componente Canvas. Em sua forma mais simples, a função create_oval() requer as coordenadas x e y a partir das quais o círculo ou elípse será desenhada e a largura e a altura do retângulo dentro do qual o círculo estará contido. Para desenhar uma oval ou elípse, basta manipular a largura ou altura desse retângulo. Veja um trecho de código no qual usamos a função create_oval() para desenhar um círculo com 5 pixels de largura da linha de desenho: ---------------------------------------------------------------------- Se precisar de ajuda com o código abaixo, pode me chamar no WhatsApp +55 (62) 98553-6711 (Osmar) ---------------------------------------------------------------------- # vamos importar o módulo Tkinter from tkinter import * from tkinter.ttk import * # método principal def main(): # cria a janela principal da aplicação janela_principal = Tk() # define as dimensões da janela janela_principal.geometry("400x350") # define o título da janela janela_principal.title("Uso do controle Canvas") # vamos criar o objeto Canvas canvas = Canvas(janela_principal, bg="white", width=400, height=350) # colocamos o Canvas na janela principal canvas.grid(row=0, column=0) # agora vamos desenhar um círculo no Canvas começando nas # coordenadas x=20 e y=30 centro de um retângulo de largura # 150 pixels por uma altura de 150 pixels e largura da linha # de 5 pixels canvas.create_oval(20, 30, 150, 150, width="5") # entramos no loop de eventos janela_principal.mainloop() if __name__== "__main__": main() Note que a largura da linha de desenho foi informada por meio do parâmetro width. Se quisermos definir também a cor da linha do desenho, basta usarmos o parâmetro outline e fornecer a cor desejada. |
Python ::: Dicas & Truques ::: Matemática e Estatística |
Como testar se um número é primo em PythonQuantidade de visualizações: 3356 vezes |
O Número Primo é o número maior que 1 e que só pode ser dividido por 1 e por ele mesmo, ou seja, números primos não podem ser divididos por outros números, a não ser por ele mesmo e pelo número 1. Dessa forma, 2, 3, 5, 7, 11, 13, 17, etc, são todos números primos. É importante observar que 0 e 1 não são números primos, e que o número 2 é o único número primo par. Veja agora um código Python completo que pede para o usuário informar um número inteiro positivo e mostra uma mensagem indicando se o número informado é primo ou não: ---------------------------------------------------------------------- Se precisar de ajuda com o código abaixo, pode me chamar no WhatsApp +55 (62) 98553-6711 (Osmar) ---------------------------------------------------------------------- def main(): primo = True # vamos assumir que o número é primo # vamos solicitar um número inteiro positivo numero = int(input("Informe um número inteiro positivo: ")) # o número é negativo? if numero < 0: print("Número inválido.") # é 0 ou 1? elif (numero == 0) or (numero == 1): print("Número válido, mas não é primo.") # passou até aqui. Vamos testar se o número é primo else: for i in range(2, int((numero / 2))): # se passar no teste, não é primo if numero % i == 0: primo = False # recebe false break if primo: print("O número informado é primo") else: print("O número informado não é primo") if __name__== "__main__": main() Ao executar este código Python nós teremos o seguinte resultado: Informe um número inteiro positivo: 9 O número informado não é primo |
Python ::: Desafios e Lista de Exercícios Resolvidos ::: Ordenação e Pesquisa (Busca) |
Exercícios Resolvidos de Python - Como usar a Ordenação da Bolha em Python para ordenar os valores de um vetor em ordem crescente ou decrescenteQuantidade de visualizações: 260 vezes |
Pergunta/Tarefa: A Ordenação da Bolha, ou ordenação por flutuação (literalmente "por bolha"), também chamada de Bubble Sort, é um algoritmo de ordenação dos mais simples. A ideia é percorrer o array diversas vezes, a cada passagem fazendo flutuar para o topo o maior elemento da sequência. Essa movimentação lembra a forma como as bolhas em um tanque de água procuram seu próprio nível, e disso vem o nome do algoritmo. No melhor caso, o algoritmo executa n operações relevantes, onde n representa o número de elementos do vetor. No pior caso, são feitas n2 operações. A complexidade desse algoritmo é de ordem quadrática. Por isso, ele não é recomendado para programas que precisem de velocidade e operem com quantidade elevada de dados. Escreva um programa Python que declara, constrói um vetor de 10 inteiros e peça para o usuário informar os valores de seus elementos. Em seguida use a ordenação da bolha para ordenar os elementos em ordem crescente. Sua saída deverá ser parecida com: Informe o valor para o índice 0: 84 Informe o valor para o índice 1: 23 Informe o valor para o índice 2: 9 Informe o valor para o índice 3: 5 Informe o valor para o índice 4: 11 Informe o valor para o índice 5: 3 Informe o valor para o índice 6: 50 Informe o valor para o índice 7: 7 Informe o valor para o índice 8: 2 Informe o valor para o índice 9: 73 O array informado foi: 84 23 9 5 11 3 50 7 2 73 O array ordenado é: 2 3 5 7 9 11 23 50 73 84 Veja a resolução comentada deste exercício usando Python: ---------------------------------------------------------------------- Se precisar de ajuda com o código abaixo, pode me chamar no WhatsApp +55 (62) 98553-6711 (Osmar) ---------------------------------------------------------------------- # função principal do programa def main(): # vamos declarar e construir um vetor de 10 elementos valores = [0 for x in range(10)] # vamos pedir que o usuário informe os valores for i in range(0, len(valores)): valores[i] = int(input("Informe o valor para o índice {0}: ".format(i))) # vamos mostrar o vetor informado print("\nO array informado foi:\n\n") for i in range(0, len(valores)): print(valores[i], end=" ") # vamos ordenar os elementos do vetor usando a ordenação da bolha # laço externo de trás para frente for i in range(len(valores) - 1, 0, -1): for j in range(0, i): # laço interno vai no fluxo normal if valores[j] > valores[j + 1]: # temos que trocá-los de lugar temp = valores[j] valores[j] = valores[j + 1] valores[j + 1] = temp # vamos exibir o vetor já ordenado print("\n\nO array ordenado é:\n\n") for i in range(0, len(valores)): print(valores[i], end=" ") print("\n") if __name__== "__main__": main() |
C++ ::: Dicas & Truques ::: Recursão (Recursividade) |
Como calcular fatorial em C++ usando recursividadeQuantidade de visualizações: 9330 vezes |
O fatorial de um determinado número, representado por n! equivale a multiplicar este número por seus antecessores. Assim, o fatorial de 4 (4!) pode ser calculado da seguinte forma: 4 x 3 x 2 x 1 = 24 Sempre que falamos de recursão, o cálculo de fatorial nos auxilia na exemplicação por ser relativamente fácil de se entender todas as etapas do processo. O código abaixo mostra uma função recursiva em C++ que calcula o fatorial de qualquer número. Tenha cuidado. Calcular o fatorial de um número maior que 10 pode tornar sua máquina extremamente lenta, além de, muitas vezes, não retornar os resultados esperados. ---------------------------------------------------------------------- Se precisar de ajuda com o código abaixo, pode me chamar no WhatsApp +55 (62) 98553-6711 (Osmar) ---------------------------------------------------------------------- #include <iostream> using namespace std; // função recursiva para calcular o fatorial // de um determinado número int fatorial(int n){ if(n == 0) return 1; else return n * fatorial(n - 1); } int main(int argc, char *argv[]){ // vamos calcular o fatorial de 5 int res = fatorial(5); // exibe o resultado cout << "O fatorial de 5 é: " << res << endl; system("PAUSE"); // pausa o programa return EXIT_SUCCESS; } |
Elixir ::: Dicas de Estudo e Anotações ::: Passos Iniciais |
Como instalar a linguagem de programação Elixir no WindowsQuantidade de visualizações: 354 vezes |
Está curioso(a) para aprender um pouco mais sobre a linguagem de programação Elixir? Nesta dica mostrarei como instalar, configurar e testar o ambiente de programação desta linguagem. O primeiro passo para instalar a Elixir no Windows é verificar se você já tem uma instalação do ambiente de programação Erlang. Se ainda não tiver, veja a nossa dica correspondente. Como baixar e instalar a Elixir Para baixar a Elixir e as ferramentas necessárias, acesse a URL https://elixir-lang.org/install.html#windows e baixe o instalador elixir-websetup.exe. Em seguida dê duplo-clique neste instalador e siga as instruções apresentadas. Não se preocupe. Basta aceitar as opções padrões que o instalador fará a instalação completa, inclusive incluindo o diretório bin na variável de ambiente PATH. Como testar a instalação da Elixir Para testar se sua instalação da linguagem de programação Elixir ocorreu sem problemas, abra uma nova janela de terminal e dispare o seguinte comando: ---------------------------------------------------------------------- Se precisar de ajuda com o código abaixo, pode me chamar no WhatsApp +55 (62) 98553-6711 (Osmar) ---------------------------------------------------------------------- C:\Users\Osmar>elixirc --version Se tudo correu bem você verá o seguinte resultado: Erlang/OTP 25 [erts-13.2] [source] [64-bit] [smp:4:4] [ds:4:4:10] [async-threads:1] [jit:ns] Elixir 1.14.3 (compiled with Erlang/OTP 25) Pronto! Agora é só seguir as nossas dicas e truques de Elixir e ficar fluente em mais essa linguagem de programação. Bons estudos! |
Veja mais Dicas e truques de Elixir |
Dicas e truques de outras linguagens |
PHP - Como obter o caminho da raiz do site usando a variável global $_SERVER['DOCUMENT_ROOT'] do PHP |
Códigos Fonte |
Software de Gestão Financeira com código fonte em PHP, MySQL, Bootstrap, jQuery - Inclui cadastro de clientes, fornecedores e ticket de atendimento Diga adeus às planilhas do Excel e tenha 100% de controle sobre suas contas a pagar e a receber, gestão de receitas e despesas, cadastro de clientes e fornecedores com fotos e histórico de atendimentos. Código fonte completo e funcional, com instruções para instalação e configuração do banco de dados MySQL. Fácil de modificar e adicionar novas funcionalidades. Clique aqui e saiba mais |
Controle de Estoque completo com código fonte em PHP, MySQL, Bootstrap, jQuery - 100% funcional e fácil de modificar e implementar novas funcionalidades Tenha o seu próprio sistema de controle de estoque web. com cadastro de produtos, categorias, fornecedores, entradas e saídas de produtos, com relatórios por data, margem de lucro e muito mais. Código simples e fácil de modificar. Acompanha instruções para instalação e criação do banco de dados MySQL. Clique aqui e saiba mais |
Linguagens Mais Populares |
1º lugar: Java |