Você está aqui: Python ::: Estruturas de Dados ::: Árvore Binária e Árvore Binária de Busca |
||
Como percorrer uma árvore binária em Python usando o algorítmo depth-first search (DFS) de forma iterativaQuantidade de visualizações: 32 vezes |
||
Nesta dica mostrarei como podemos implementar o algorítmo da Busca em Profundidade (DFS, do inglês depth-first search) em Python de forma iterativa, ou seja, sem usar recursividade. 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:
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 List do Python, juntamente com seus métodos append() e pop() para simular a pilha. Usei também uma List para guardar os valores da árvore binária na ordem depth-first. Eis o código:
Ao executarmos este código Python 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 ::: Desafios e Lista de Exercícios Resolvidos ::: Strings e Caracteres |
Exercícios Resolvidos de Python - Como retornar o código ASCII associado a um caractere em Python - Ler um caractere e retornar o código ASCII correspondenteQuantidade de visualizações: 561 vezes |
Pergunta/Tarefa: Escreva um programa Python que pede para o usuário informar um caractere (letra ou número) e mostre o código ASCII correspondente. Sua saída deverá ser parecida com: Informe um caractere: A Você informou o caractere: A O código ASCII correspondente é: 65 Veja a resolução comentada deste exercício em 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 pedir para o usuário informar uma letra, símbolo ou pontuação caractere = input("Informe um caractere: ") # agora vamos obter o código ASCII correspondente codigo = ord(caractere) # e mostramos o resultado print("Você informou o caractere: {0}".format(caractere)) print("O código ASCII correspondente é: {0}".format(codigo)) if __name__== "__main__": main() O Código Padrão Americano para o Intercâmbio de Informação (do inglês American Standard Code for Information Interchange - ASCII, pronunciado [áski]) é um sistema de representação de letras, algarismos e sinais de pontuação e de controle, através de um sinal codificado em forma de código binário (cadeias de bits formada por vários 0 e 1), desenvolvido a partir de 1960, que representa um conjunto de 128 sinais: 95 sinais gráficos (letras do alfabeto latino, algarismos arábicos, sinais de pontuação e sinais matemáticos) e 33 sinais de controle, utilizando 7 bits para representar todos os seus símbolos. |
Python ::: Python para Engenharia ::: Geometria Analítica e Álgebra Linear |
Como converter Coordenadas Cartesianas para Coordenadas Polares usando PythonQuantidade de visualizações: 5438 vezes |
Nesta nossa série de Python para Geometria Analítica e Álgebra Linear, mostrarei um código 100% funcional para fazer a conversão entre coordenadas cartesianas e coordenadas polares. Esta operação é muito frequente em computação gráfica e é parte integrante das disciplinas dos cursos de Engenharia (com maior ênfase na Engenharia Civil). Na matemática, principalmente em Geometria e Trigonometria, o sistema de Coordenadas no Plano Cartesiano, ou Espaço Cartesiano, é um sistema que define cada ponto em um plano associando-o, unicamente, a um conjuntos de pontos numéricos. Dessa forma, no plano cartesiano, um ponto é representado pelas coordenadas (x, y), com o x indicando o eixo horizontal (eixo das abscissas) e o y indicando o eixo vertical (eixo das ordenadas). Quando saímos do plano (espaço 2D ou R2) para o espaço (espaço 3D ou R3), temos a inclusão do eixo z (que indica profundidade). Já o sistema de Coordenadas Polares é um sistema de coordenadas em duas dimensões no qual cada ponto no plano é determinado por sua distância a partir de um ponto de referência conhecido como raio (r) e um ângulo a partir de uma direção de referência. Este ângulo é normalmente chamado de theta (__$\theta__$). Assim, um ponto em Coordenadas Polares é conhecido por sua posição (r, __$\theta__$). Antes de prosseguirmos, veja uma imagem demonstrando os dois sistemas de coordenadas: A fórmula para conversão de Coordenadas Cartesianas para Coordenadas Polares é: __$r = \sqrt{x^2+y2}__$ __$\theta = \\arctan\left(\frac{y}{x}\right)__$ E aqui está o código Python completo que recebe as coordenadas cartesianas (x, y) e retorna as coordenadas polares (r, __$\theta__$): ---------------------------------------------------------------------- Se precisar de ajuda com o código abaixo, pode me chamar no WhatsApp +55 (62) 98553-6711 (Osmar) ---------------------------------------------------------------------- # importamos a bibliteca NumPy import numpy as np import math as math def main(): # vamos ler as coordenadas cartesianas x = float(input("Valor de x: ")) y = float(input("Valor de y: ")) # vamos calcular o raio raio = math.sqrt(math.pow(x, 2) + math.pow(y, 2)) # agora calculamos o theta (ângulo) em radianos theta = np.arctan2(y, x) # queremos o ângulo em graus também angulo_graus = 180 * (theta / math.pi) # e exibimos o resultado print("As Coordenadas Polares são:") print("raio = %0.4f, theta = %0.4f, ângulo em graus = %0.2f" % (raio, theta, angulo_graus)) if __name__== "__main__": main() Ao executar este código nós teremos o seguinte resultado: Valor de x: -1 Valor de y: 1 As Coordenadas Polares são: raio = 1.4142, theta = 2.3562, ângulo em graus = 135.00 Veja que as coordenadas polares equivalentes são (__$\sqrt{2}__$, __$\frac{3\pi}{4}__$), com o theta em radianos. Sim, os professores das disciplinas de Geometria Analítica e Álgebra Linear, Física e outras gostam de escrever os resultados usando raízes e frações em vez de valores reais. |
Python ::: Dicas & Truques ::: Data e Hora |
Como calcular a diferença de dias entre duas datas em PythonQuantidade de visualizações: 1348 vezes |
Nesta dica mostrarei como podemos usar retornar a diferença de dias entre duas datas na linguagem Python usando o objeto Date, do módulo DateTime. Note o uso do construtor date() para construir as duas datas e em seguida passamos estas duas datas para uma função personalizada numero_dias(), que retorna a quantidade de dias entre elas. Veja o código completo para o exemplo: ---------------------------------------------------------------------- Se precisar de ajuda com o código abaixo, pode me chamar no WhatsApp +55 (62) 98553-6711 (Osmar) ---------------------------------------------------------------------- # vamos importar o objeto Date from datetime import date def main(): # vamos criar a data inicial e a data final d1 = date(2022, 11, 10) d2 = date(2022, 12, 23) # vamos calcular a diferença de dias diferenca = numero_dias(d1, d2) # e mostramos o resultado print("A primeira data é: {0}".format(d1)) print("A segunda data é: {0}".format(d2)) print("A diferença de dias entre as duas datas é: {0} dias".format( diferenca)) # função que recebe duas datas e retorna a diferença # de dias entre elas def numero_dias(data1, data2): return (data2 - data1).days if __name__== "__main__": main() Ao executar este código Python nós teremos o seguinte resultado: A primeira data é: 2022-11-10 A segunda data é: 2022-12-23 A diferença de dias entre as duas datas é: 43 dias |
Desafios, Exercícios e Algoritmos Resolvidos de Python |
Veja mais Dicas e truques de Python |
Dicas e truques de outras linguagens |
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 |