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 iterativa

Quantidade 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:

Este trecho de código ou resolução de exercício faz parte do Super Pack 12.000 Dicas e Truques de Programação e 1.500 Exercícios Resolvidos em Java, Python, VisuAlg, Portugol, Delphi, C#, C, C++, VB.NET, Golang, Pascal, Ruby, PHP, e várias outras linguagens.

Aprenda a programar resolvendo problemas do mundo real. Tudo em português, com comentários em português.

Quero Ser Apoiador(a)


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:

Este trecho de código ou resolução de exercício faz parte do Super Pack 12.000 Dicas e Truques de Programação e 1.500 Exercícios Resolvidos em Java, Python, VisuAlg, Portugol, Delphi, C#, C, C++, VB.NET, Golang, Pascal, Ruby, PHP, e várias outras linguagens.

Aprenda a programar resolvendo problemas do mundo real. Tudo em português, com comentários em português.

Quero Ser Apoiador(a)


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 correspondente

Quantidade 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
Resposta/Solução:

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 Python

Quantidade 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 Python

Quantidade 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

Programa de Gestão Financeira Controle de Contas a Pagar e a Receber com Cadastro de Clientes e FornecedoresSoftware 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 funcionalidadesControle 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
2º lugar: Python
3º lugar: C#
4º lugar: PHP
5º lugar: Delphi
6º lugar: C
7º lugar: JavaScript
8º lugar: C++
9º lugar: VB.NET
10º lugar: Ruby



© 2024 Arquivo de Códigos - Todos os direitos reservados
Neste momento há 23 usuários muito felizes estudando em nosso site.