LÓGICA DE PROGRAMAÇÃO E

ESTRUTURAS DE DADOS

Professor Marcelo Ferreira Zochio

Sumário
1 NOÇÕES BÁSICAS DE LÓGICA DE PROGRAMAÇÃO .................................................................... 3
2 INTRODUÇÃO À PROGRAMAÇÃO USANDO LINGUAGEM PYTHON ......................................... 14
3 PRINCIPAIS COMANDOS ........................................................................................................... 27
4 FUNÇÕES E RECURSOS ............................................................................................................. 36
5 ESTRUTURA DE DADOS ............................................................................................................ 43
6 ÁRVORES BINÁRIAS .................................................................................................................. 51

2
1 NOÇÕES BÁSICAS DE LÓGICA DE PROGRAMAÇÃO

Para que você possa desenvolver um programa de computador, é necessário que,

primeiro, seja desenvolvido em você um pensamento ordenado, lógico, que consiga
entender um problema, elaborar uma solução lógica para tal problema e passar isso
para uma linguagem de programação. Esse é o intuito deste módulo. Ele é composto
pelos seguintes subtemas:

 Noções de funcionamento de um computador

 Noções de algoritmo
 Algoritmos clássicos
 Fluxogramas e blocos
 Linguagem

Ao final deste bloco, você será capaz de identificar os componentes de um computador;

conhecer como atuam esses componentes no processamento da informação; entender
como eles contribuem para que o computador funcione eficientemente; identificar os
componentes de um algoritmo; conhecer como atuam esses componentes no
processamento da composição do algoritmo; entender como eles contribuem para que
o software funcione eficientemente; e elaborar algoritmos descritivos para a solução de
problemas.

1.1 Noções de funcionamento de um computador

A arquitetura básica de qualquer computador atual é formada por cinco componentes:

processador, memória RAM, disco rígido, dispositivos de entrada e saída e softwares.

O processador é a parte pensante do sistema; é onde são processadas as informações.

3
Na memória principal, também chamada memória RAM (Read and Access Memory), são
armazenados temporariamente os dados que estão sendo processados; é como se fosse
uma mesa de trabalho, onde o material é colocado, trabalhado e depois armazenado
em outro lugar: na memória secundária, ou disco rígido. Nele ficam guardados
programas e dados enquanto não estão em uso ou quando o micro é desligado.

Para o processador e os demais componentes do micro se comunicarem, existem os

dispositivos de entrada e saída. Estes são as porteiras do computador, por onde ele
recebe e transmite informações para o processador.

O computador é um completo mentecapto. Existe a inteligência artificial, mas é assunto

para outra disciplina. Ele só faz o que é programado para fazer. Quem “faz as coisas
acontecerem” são os softwares, que instruem os componentes físicos do computador,
executando tarefas.

Se você quer que ele faça projetos de engenharia, ou seja capaz de interpretar
programas escritos em linguagem Python, ou qualquer outra tarefa, basta instalar o
software adequado.

Quanto aos tipos de linguagem de programação, podemos classificá-las em linguagens

de programação de alto nível e baixo nível. As linguagens de alto nível facilitam a vida
do programador, pois sua sintaxe procura ser o mais próximo possível da linguagem
natural. Já as linguagens de baixo nível procuram trabalhar com aspectos mais
profundos do funcionamento da máquina, permitindo, por exemplo, trabalhar no nível
dos registradores do microprocessador. Logo, sua sintaxe não é amigável e precisam ser
mais analíticas para que o computador entenda o que ele tem que fazer.

Essa característica facilita o trabalho dos programadores, que podem se empenhar em

desenvolver softwares cada vez mais complexos em um espaço de tempo menor, sem
se preocupar com detalhes de hardware.

4
SAIBA MAIS

Como você viu, o funcionamento de um computador envolve a perfeita coordenação de

vários componentes. E o programa, como interage com eles? Acesse o link a seguir para
entender mais a respeito sobre o assunto:

Vídeo: Como funciona um programa de computador?

HERRMANN, T. Como funciona um programa de computador? 2017. Disponível em:

<https://www.youtube.com/watch?v=1JuOJCpigkQ>. Acesso em: 13 fev. 2019.

1.2 Noções de algoritmo

Algoritmo é um processo sistemático para a resolução de um problema, segundo

Szwarcfiter e Markenzon (1994 apud MANZANO; OLIVEIRA, 2016).

Você trabalha com algoritmos todos os dias e talvez não tenha se dado conta ainda.
Pense um pouco: quais as ações que você faz para sair de casa ao acordar e ir trabalhar?

 Despertar
 Abrir os olhos
 Levantar da cama
 Calçar os chinelos
 Ir ao banheiro
 Abrir o armário
 Pegar a escova
 Pegar a pasta de dentes
 Colocar pasta na escova
 Escovar os dentes
 Enxaguar a boca
 Lavar a escova
 Guardar a escova
 Guardar a pasta

5
  Ir à cozinha
 Fazer a refeição matinal
 Trocar de roupa
 Abrir a porta
 Sair de casa
 Fechar a porta
 Ir até o ponto de ônibus
 Pegar o ônibus
 Descer no ponto do trabalho
 Entrar na empresa

Esse é o algoritmo que resolve o problema que você precisa resolver de ir de casa ao
trabalho. Existem algumas formas de representar um algoritmo.

Entre as formas de representação de algoritmo mais conhecidas, destacam-se:

 A descrição narrativa;
 O fluxograma convencional;
 O pseudocódigo, também conhecido como linguagem estruturada ou Portugol.

Entretanto, para projetar um algoritmo precisamos primeiro dividir o problema em três

partes:

 Entrada: aqui são colocados os dados de entrada do algoritmo;

 Processamento: aqui são realizados os procedimentos para gerar o resultado
final;
 Saída: aqui são apresentados os resultados obtidos.

1.3 Algoritmos clássicos

Alguns problemas didáticos são usados para que o aluno adquira a capacidade de
desenvolver algoritmos bem estruturados. Veja alguns deles:

6
Torre de Hanói: você deve transferir três discos sobrepostos em ordem descendente do
menor para o maior encaixados em um pino para o terceiro pino, obedecendo a seguinte
regra: os discos maiores devem ficar embaixo dos menores durante a transferência.

Figura 1 – Torre de Hanói (fonte: o autor)

Sabe a resposta? Vejamos a solução:

• Mover o disco menor para a torre 3

• Mover o disco intermediário para a torre 2
• Mover o disco menor para a torre 2
• Mover o disco maior para a torre 3
• Mover o disco menor para a torre 1
• Mover o disco intermediário para a torre 3
• Mover o disco menor para a torre 3

O lobo, o cordeiro e as alfaces

Um homem tem que atravessar um rio com uma ovelha, um lobo e uma caixa de alfaces.
Eles devem ser atravessados um por vez, com o homem e um deles no barco, até a outra
margem. Se o lobo ficar sozinho com a ovelha em uma das margens, ele a atacará; se a
ovelha ficar sozinha com as alfaces, ela os comerá.

Sabe a resposta? Vejamos a solução:

• Colocar o cordeiro no barco;

• Navegar até a outra margem;

7
 • Desembarcar o cordeiro;
• Navegar até a outra margem;
• Colocar o lobo no barco;
• Navegar até a outra margem;
• Desembarcar o lobo;
• Embarcar o cordeiro;
• Navegar até a outra margem;
• Desembarcar o cordeiro;
• Embarcar a alface;
• Navegar até a outra margem;
• Desembarcar a alface;
• Navegar até a outra margem;
• Embarcar o cordeiro;
• Navegar até a outra margem;
• Desembarcar o cordeiro.

Os padres e os canibais

Três padres e três canibais precisam atravessar um rio em um barco que cabe apenas
duas pessoas. Não pode haver mais canibais que padres em qualquer uma das duas
margens do rio.

Sabe a resposta? Vejamos a solução:

 Desembarcar os dois padres;

 Embarcar um canibal;
 Navegar até a outra margem;
 Embarcar um canibal;
 Navegar até a outra margem;
 Desembarcar um canibal;
 Navegar até a outra margem;
 Embarcar um canibal;
 Navegar até a outra margem;

8
  Desembarcar os dois canibais.

A travessia da família

Uma família composta por um casal com duas filhas e dois filhos precisa atravessar um
rio com um policial e um delinquente juvenil. O barco só comporta duas pessoas. A mãe
não pode ser deixada sem a presença do pai quando os filhos estão com ela, senão ela
bate neles. O pai não pode ser deixado sem a presença da mãe quando as filhas estão
com ele, senão ele bate nelas. O delinquente juvenil deve estar sempre acompanhado
do policial, senão ele bate em quem estiver presente. Só adultos pilotam o barco.

Sabe a resposta? Vejamos a solução:

 Embarcar o policial;
 Embarcar o delinquente;
 Navegar até a outra margem;
 Desembarcar o delinquente;
 Navegar até a outra margem;
 Embarcar um dos filhos;
 Navegar até a outra margem;
 Desembarcar o filho;
 Embarcar o delinquente;
 Navegar até a outra margem;
 Desembarcar o policial;
 Desembarcar o delinquente;
 Embarcar o pai;
 Embarcar o filho;
 Navegar até a outra margem;
 Desembarcar o filho;
 Navegar até a outra margem;
 Embarcar a mãe;
 Navegar até a outra margem;

9
 Desembarcar o pai;
 Navegar até a outra margem;
 Desembarcar a mãe;
 Embarcar o policial;
 Embarcar o delinquente;
 Navegar até a outra margem;
 Desembarcar o policial;
 Desembarcar o delinquente;
 Embarcar o pai;
 Navegar até a outra margem;
 Embarcar a mãe;
 Navegar até a outra margem;
 Desembarcar o pai;
 Navegar até a outra margem;
 Embarcar uma filha;
 Navegar até a outra margem;
 Desembarcar uma filha;
 Desembarcar a mãe;
 Embarcar o policial;
 Embarcar o delinquente;
 Navegar até a outra margem;
 Desembarcar o delinquente;
 Embarcar a filha;
 Navegar até a outra margem;
 Desembarcar a filha;
 Navegar até a outra margem;
 Embarcar o delinquente;
 Navegar até a outra margem;
 Desembarcar o policial;
 Desembarcar o delinquente.

10
1.4 Fluxograma e blocos

SETA
Conecta outros símbolos indicando o sentido
do fluxo de dados.

TERMINAL
Indica começo ou término de processamento.

PROCESSAMENTO
Exemplo: cálculo de dois valores.

ENTRADA/SAÍDA (Genérica)
Indica entrada ou saída de dados. Exemplo:
armazenamento de valores em variáveis.

CONECTOR
Conecta um ponto qualquer do fluxograma.

ENTRADA MANUAL
Representa entrada de dados via
teclado. Exemplo: digitar a nota da prova
1.

SAÍDA – EXIBIR NA TELA

Exibe informações ou resultados. Exemplo:
mostrar o resultado do cálculo na tela.

11
 SAÍDA – IMPRIMIR
Mostra informações ou resultados via
impressão em papel. Exemplo: imprimir o
resultado do cálculo.

DECISÃO
Permite elaborar processos de decisão “se isto,
faça isto; senão, faça aquilo”

CONECTOR DE PÁGINA
Conecta uma página qualquer do fluxograma.

Outra maneira de representar algoritmos é usando blocos. Veja um exemplo a seguir:

1.5 Linguagem

Você notou que para um software existir, ele precisa ser desenvolvido. A outra etapa de
seu desenvolvimento é a escrita do algoritmo em uma linguagem de programação. Ela
pode ser de alto ou baixo nível, ou ainda interpretada ou compilada.

12
Linguagens de baixo nível conseguem operar diretamente no hardware dos
computadores; linguagens de alto nível têm a necessidade de fazer com que as
instruções e comandos feitos nela sejam transformados em instruções e comandos de
baixo nível. Surgem então os interpretadores e compiladores.

Nas linguagens interpretadas, o interpretador lê um programa escrito em linguagem de

alto nível e o executa, ou seja, faz o que o programa manda fazer.

Nas linguagens compiladas, o interpretador lê o programa e o compila antes de ser

executado, ou seja, ele cria um arquivo executável. Uma vez que um programa é
compilado, você pode executá-lo sempre que precisar.

Conclusão

Como vimos, construir um programa não consiste apenas em escrever códigos; há uma
lógica envolvida em sua construção, que é essencial para o seu correto funcionamento.
Antes de escrevermos o programa em si, é necessário estudarmos como abordaremos
o problema a ser resolvido, desenvolver os passos para sua solução e depois passar essa
solução escrita em uma linguagem que um computador está apto a entender.

Referências

MANZANO, J. A. N. G.; OLIVEIRA, J. F. Algoritmos: lógica para desenvolvimento de

programação de computadores. 28. ed. São Paulo: Érica, 2016.

PESQUISA FAPESP. O que é e como funciona os algoritmos? 2018. Disponível em:

<https://www.youtube.com/watch?v=Xo1V_JL1yAg>. Acesso em: 27 out. 2018.

13
2 INTRODUÇÃO À PROGRAMAÇÃO USANDO LINGUAGEM PYTHON

Neste tópico, você terá o primeiro contato com uma linguagem de programação, a
linguagem Python, e verá como ela trabalha. Verá também quais as vantagens de
aprender a programar nessa linguagem. Ao final deste bloco, você será capaz de
identificar constantes e variáveis; saber como trabalhar com operadores e operandos
em Python; identificar entradas e saídas de um programa Python e criar um programa
básico em Python.

2.1 Constantes e variáveis

Variável será o primeiro assunto que abordaremos. Como o próprio nome diz, ele
trabalha com valores que mudam de acordo com as circunstâncias. Variável é a
representação de uma região de memória utilizada para armazenar, acessar e modificar
certo valor por um determinado espaço de tempo. Podemos denominá-la como
quisermos, desde que não usemos palavras reservadas da linguagem usada para a
construção do programa, e seja um nome contido em uma string contínua, sem espaços.
Em muitas linguagens de programação, ela deve ser declarada; na linguagem Python,
não há necessidade, pois Python é dinamicamente tipada, não havendo a necessidade
de se declarar variáveis, pois intuitivamente o tipo de variável é identificado pelo
sistema. Veja na prática essa afirmação: imagine um programa que calcule a média entre
dois valores digitados pelo usuário. A seguir, tal informação escrita na linguagem C:

#include <stdio.h>

float x, y, media;

int main(void)

14
printf("Digite o primeiro valor: ");

scanf("%f", &x);

printf("\nDigite o segundo valor: ");

scanf("%f", &y);

media=(x+y)/2;

printf("\nResultado= %f", media);

return 0;

Na sequência, o mesmo programa escrito em Python:

a=float(input("Digite o primeiro valor: "))

b=float(input("Digite o segundo valor: "))

c=(a+b)/2

print "Resultado= ", c

Constante é um valor que será inalterado, independente das condições envolvidas na

operação a ser realizada. As regras para seu uso são as mesmas aplicadas à variável.
Pode ser uma string (conjunto de caracteres) ou um valor numérico.

SAIBA MAIS

Entenda melhor sobre o assunto no seguinte vídeo, que explica o uso de constantes e
variáveis em Python.

Vídeo: Constantes e variáveis

NETO, A. C. Constantes e variáveis. 2017. Disponível em:

<https://www.youtube.com/watch?v=uiGeQD_z2vs>. Acesso em: 13 fev. 2019.

15
2.2 Atribuição e operadores

Para atribuirmos valor a uma variável ou constante, ou ainda a outros elementos, como
listas, dicionários ou tuplas, usamos o caractere “=”. Veja exemplos a seguir:

# Exemplo 1:

a = 10

# Exemplo 2:

b = 7.4

# Exemplo 3:

c = ‘estou estudando Python’

# Exemplo 4:

d = [0, 1, 2]

No exemplo 1, a variável de nome “a” tem o valor 10, sendo do tipo “inteiro”; no
exemplo 2, a variável de nome “b” tem o valor 7.4, sendo do tipo “float”; no exemplo 3,
a variável de nome “c” contém uma string (sequência de caracteres), sendo do tipo
“string”. O exemplo 4 contém uma variável denominada “d” que inclui uma lista
(também chamada de “array” em outras linguagens de programação).

Note que não precisamos declarar o tipo de variável, pois como a linguagem Python é
dinamicamente tipada, o tipo de variável ou constante está implícito nos dados que ela
contém.

Operadores são símbolos especiais que representam cálculos como adição, subtração e
divisão. Os valores que são chamados pelo operador são denominados operandos. Em
Python, os símbolos + (adição), - (subtração), / (divisão), * (multiplicação), **
(potenciação) e demais símbolos, como os parênteses, têm a mesma função que em
uma expressão matemática.

Nas operações matemáticas em Python, quando todos os operandos são inteiros, o

resultado da operação é sempre um valor inteiro. Para expressar valores decimais, tanto

16
na entrada de dados como na saída, deve-se usar o ponto flutuante ao escrever o
número. Veja a sequência de operações a seguir (o símbolo >>> é do prompt da
linguagem Python):

>>> 1 + 1

>>> 1.0 + 2.0

3.0

>>> 3.1 + 4

7.1

>>> 4 * (3 + 9)

48

>>> 2/3

>>> 456.0 / (5 + (7*3)-15)

41.45454545454545

>>> -7+9

>>> -5**2

-25

>>> (-5)**2

25

Agora, um exemplo de soma de variáveis:

>>> a = 64

>>> b = 17

>>> a+b

81

17
Note que a divisão 2 / 3 em Python, citada nos exemplos acima, fornece 0 como
resultado porque a linguagem Python está considerando apenas a divisão inteira
(somente o número 0 do resultado real que é 0.66666...). A ordem de execução dos
operadores obedece à mesma regra da matemática.

Quando o operador + é usado em strings, ele faz uma operação chamada concatenação
de strings. O operador * também tem a mesma função, porém como multiplicador. Veja,
a seguir, alguns exemplos:

>>> 'goiaba' + 'goiaba'+ 'goiaba'

'goiabagoiabagoiaba'

>>> 'python' * 3

'pythonpythonpython'

Operações modulares em Python são realizadas pelo operador %; veja alguns exemplos:

>>> 15%7

>>> 17%3

O Python trabalha também com operações booleanas (“verdadeiro” ou “falso”). O

operador == faz a comparação de valores; veja alguns exemplos:

>>> 10 == 10

True

>>> 5 == 7

False

18
Caso você queira realizar operações lógicas (E, OU, OU EXCLUSIVO), poderá usar os
operadores:

& (operação lógica E)

| (operação lógica OU)

^ (operação lógica OU EXCLUSIVO)

Veja alguns exemplos:

>>> 5&6

>>> 5|6

>>> 5^6

Os outros operadores de comparação são (PERKOVIC, 2016):

x != y (x é diferente de y)

x > y (x é maior que y)

x < y (x é menor que y)

x >= y (x é maior ou igual a y)

x <= y (x é menor ou igual a y)

x in y (verifica se x está contido em y)

2.3 Entrada e saída

A linguagem Python trabalha com entrada de dados com o comando input. Na versão
atual da linguagem Python, o comando input considera como do tipo “string” todo valor

19
colocado em uma variável através dele. Se você quiser usar valores numéricos, deverá
convertê-los. Veja um exemplo:

a = float(input(“Digite o valor da prestação: “))

Nesse exemplo, a variável “a” recebe inicialmente um valor literal, ou seja, considerado
como caractere, que posteriormente é convertido em número real (que aceita valores
fracionados) através do comando float.

Falando em saídas, podemos ter como saídas os seguintes comandos:

print  exibição na tela

return  retorno de um resultado

Veja um exemplo de cada um deles:

Exemplo de print:

a = ‘mostrando na tela’

print a

Exemplo de return:

def media_unisa(a, b):

return (a*0.4)+(b*0.6)

Aparentemente podem parecer a mesma coisa, mas não são. O comando print, a partir
de qualquer parte de programa, exibe na tela uma informação, que pode ser o conteúdo
de uma variável, o resultado de uma operação, ou outro item; no caso do return, ele
“retorna” um valor. Geralmente é uma resposta a um chamado de alguma função ou
biblioteca.

20
SAIBA MAIS

Para saber mais sobre esse assunto, assista ao vídeo sugerido, que explica o conceito de
entradas e saídas em Python.

Vídeo: Entrada e saída de dados em Python

PYTHON CAFÉ. Entrada e saída de dados em Python. 2017. Disponível em:

<https://www.youtube.com/watch?v=7mr6ZKSBFsI>. Acesso em: 13 fev. 2019.

2.4 Programas sequenciais

Para construir um programa em Python, não é necessário nem uma IDE (Integrated
Development Environment, ou Ambiente Integrado de Desenvolvimento). Basta
escrever seu programa usando um editor de texto não formatado, como Notepad
(Windows) ou gedit (Linux), e salvar esse arquivo em formato .py.

Para que possamos acessar o programa pelo prompt do Windows, devemos indexar a
pasta que contém os arquivos da linguagem Python nas variáveis de ambiente do
Windows.

Para fazer isso, tomando por base o Windows 7, clique com o botão direito do mouse
em Meu Computador, e depois em Propriedades; abra a opção Configurações
Avançadas de Sistema, e aperte o botão Variáveis de Ambiente. Dentro de variáveis de
Sistema, selecione a opção Path; acrescente o caminho do executável da linguagem
Python (normalmente basta acrescentar C:\Python36-32;C:\Python36-32\Scripts;).
Aperte OK em todas as janelas abertas. Preste atenção, pois a pasta onde o Python foi
instalado no Windows pode variar. Aí você terá que colocar o caminho correto, não este
que está escrito.

Uma vez isso feito, é só digitar no prompt do Windows, estando na mesma pasta em
que o programa criado está:

python nome_do_programa.py

ou ainda executá-lo diretamente, em alguns casos. É mais garantido executá-lo pelo

prompt.

21
No caso do Linux, é só acessar o programa pelo prompt ou executá-lo diretamente,
como no Windows.

Embora não haja a necessidade de IDE para construir um programa em Python, há IDE
desenvolvidas para esta linguagem. Entre elas, podemos citar:

PythonWin

PyCharm

22
PyScripter

2.5 Por que Python?

Se você já estudou programação alguma vez, deve estar se perguntando por que a
escolha da linguagem Python como instrumento de ensino de programação, uma vez
que muitos professores usam Java ou C. Vamos explicar:

Um dos motivos é a sintaxe dessas linguagens, que é complexa. Veja um exemplo de um

programa que exibe a mensagem Hello world! na tela em Java, em C e em Python:

Hello world em Java:

public class HelloWorld {

public static void main(String[] args) {

System.out.println("Hello world!");
}
}

Hello world em C:
#include <stdio.h>

23
int main(void)
{
printf("Hello world!\n");
return (0);
}

Em Python, versão 3:

print(“Hello world!”)

Veja, a seguir, um exemplo de um programa escrito em Java que cria uma lista, ou array,
e conta quantas vezes aparece o valor “5” dentro dela (ENADE, 2014, p. 13):

public class CountConcurrence {

public boolean hasValue(int searchValue, int[] array, int i) {

if (i >= array.length)
return false;

if (array[i] == searchValue)
return true;
else
return hasValue(searchValue, array, i + 1);
}

public int count(int countValue, int[] array, int i) {

if (!hasValue(countValue, array, i) || i >= array.length)
return 0;

int c = 0;
if (array[i] == countValue)
c++;

c += count(countValue, array, i+1);

24
 return c;
}

public static void main(String[] args) {

int[] array = {2, 3, 5, 6, 9, 7, 8, 8, 9};
CountConcurrence co = new CountConcurrence();
System.out.println(co.count(5, array, 0));
}
}

Agora, o mesmo programa escrito em Python:

a = [2, 3, 5, 6, 9, 7, 8, 8, 9]
contador = 0
for x in a:
if x == 5:
contador +=1
print(contador)

Uma pergunta retórica: em qual dessas linguagens você gostaria de aprender a

programar?

Sobre a linguagem Python, outras vantagens são a sua versatilidade (podemos

programar em modo procedural ou com orientação a objetos), o seu poder (é usada em
programas científicos e outras aplicações que exigem grande poder de cálculo) e a
simplicidade de uso (é interpretada, não sendo necessário compilar os programas).

Conclusão

Neste bloco, você tomou o primeiro contato com uma linguagem de programação. No
próximo, continuaremos a falar sobre os principais comandos da linguagem Python.

25
Referências

ENADE. MINISTÉRIO DA EDUCAÇÃO E CULTURA. Exame Nacional do Ensino Superior.

Prova de Tecnologia em Análise e Desenvolvimento de Sistemas. 2014. Disponível em:
<http://download.inep.gov.br/educacao_superior/enade/provas/2014/40_tecnologia_
analise_desenv_sistemas.pdf>. Acesso em: 24 dez. 2018.

PERKOVIC, Ljubomir. Introdução à computação usando Python: um foco no

desenvolvimento de aplicações. Rio de Janeiro: LTC, 2016.

26
3 PRINCIPAIS COMANDOS
Neste bloco, você aprenderá como usar estruturas de repetição e laço na linguagem
Python, bem como montar estruturas de verificação de listas, dicionários e tuplas, e
outros comandos muito usados nessa linguagem. Também aprenderá como converter
tipos de variáveis e valores numéricos entre bases numéricas na linguagem Python.

3.1 Comandos if, elif e else

Esses comandos são usados quando o programa deve analisar uma situação e tomar
uma decisão baseada nas informações fornecidas.

As decisões tomadas são do tipo “se ocorrer condição x, faça tal coisa; senão, faça essa
outra coisa”. Outra situação é ter várias condições para serem analisadas: “se ocorrer
situação x, faça tal coisa; senão, se acontecer situação y, faça essa outra coisa; senão,
faça essa coisa que é diferente das outras coisas”. Veja um exemplo nesse programa que
diz qual a categoria do atleta em relação à sua idade:

# -*- coding: cp1252-*-

idade=float(input("Idade do atleta: "))

if idade<5:

print("Sem classificacao")

# A linha abaixo verifica se a idade do atleta está entre 5 e 10 anos

elif idade<11>5:

print("Infantil")

# A linha abaixo verifica se a idade do atleta está entre 11 e 15 anos

elif idade<16>10:

27
 print("Juvenil")

# A linha abaixo verifica se a idade do atleta está entre 16 e 20 anos

elif idade<21>15:

print("Junior")

# A linha abaixo verifica se a idade do atleta está entre 21 e 39 anos

elif idade<40>20:

print ("Profissional")

else:

print "Senior"

SAIBA MAIS

Neste vídeo, você poderá ver um pouco mais sobre comandos if, elif e else aplicados a
Python.

Vídeo: Aulas Python - 011 - Estrutura de Decisões II: if, elif e else

AULAS Python - 011 - Estrutura de Decisões II: if, elif e else. 2014. Disponível em:
<https://www.youtube.com/watch?v=kY47B3StnWg>. Acesso em: 14 fev. 2019.

3.2 Comandos while e for

O comando while faz com que o programa execute uma instrução enquanto uma
condição determinada existir.

Exemplo: suponhamos que o professor lhe mande escrever 500 vezes “Não posso fazer
bagunça na aula”. Dá para escrever um programa que automatize essa tarefa? Claro...

# -*- coding: cp1252 -*-

a=0

while a<500:

28
 print("Não posso fazer bagunça na aula")

a=a+1

Ao usar o comando while, cuidado com o loop infinito, que é uma condição na qual o
programa nunca para de funcionar, se não for interrompido manualmente:

a=0

while True:

print(a)

a=a+1

O comando for permite percorrer os itens de uma lista, tupla ou dicionário, e executar
o código escrito:

a = [1, 2, 3]

b = (4, 5, 6)

c = {1:'abacate', 2:'laranja', 3:'lima'}

for i in a:

if i == 1:

print('Existe o numeral 1')

for i in b:

if i == 5:

print('Existe o numeral 5')

for i in c:

print c[i]

A saída do programa acima será:

29
Existe o numeral 1

Existe o numeral 5

abacate

laranja

lima

3.3 Comandos print e input

O comando print, como você já deve ter notado, exibe na tela o valor solicitado. Na
versão atual do Python, a versão 3, a sintaxe de sua escrita é:

print(o que se quer exibir)

Na versão anterior, a versão 2, a sintaxe do comando print é:

print o que se quer imprimir

Como exemplo, tomemos a string “o professor vai aplicar prova”:

Versão 2:

print “o professor vai aplicar prova”

Versão 3:

print(‘o professor vai aplicar prova’)

Agora, em outro exemplo, suponhamos que queremos exibir na tela o valor de uma
variável de nome “controle”:

Versão 2:

print controle

30
Versão 3:

print(controle)

Exibimos as sintaxes nas duas versões da linguagem Python porque nos seus estudos
pessoais você pode se deparar com programas feitos na versão 2.

O comando input serve para criarmos um prompt de interação com o usuário, onde ele
preenche dados, que serão armazenados em uma variável:

a = input(“Digite seu nome: “)

b = float(input(“Digite sua idade: “))

No exemplo acima, escrito na versão 3 da linguagem Python, o comando input armazena

por padrão os dados digitados no formato string, ou seja, caracteres. Então, ele
considera “1” como caractere, não como número. Para que ele reconheça os caracteres
representando números como números de fato, é necessário convertê-los para o
formato desejado, com os comandos int (inteiro) ou float (real, aquele que aceita valores
decimais). Isso pode ser visto no input da variável b.

Na versão 2 da linguagem Python, o comando input armazena valores numéricos; para

armazenarmos valores literais devemos usar o comando raw_input. Veja o mesmo
trecho de programa escrito em Python versão 2:

a = raw_input(“Digite seu nome: “)

b = input(“Digite sua idade: “)

3.4 Outros comandos

A seguir, abordaremos mais alguns comandos importantes.

31
len: calcula o tamanho de uma string.

Exemplo:

a = ‘banana’

print(len(a))

Saída:

Fatiamento de strings: algumas vezes precisamos de um determinado trecho de um

valor literal armazenado em uma variável. Para tal procedimento, basta colocar entre
colchetes o índice inicial que queremos e o final.

Veja alguns exemplos na figura a seguir:

count: função embutida que conta quantas ocorrências há dentro de uma string, lista ou
tupla de uma determinada busca.

Veja exemplos na próxima figura:

32
find: função embutida que informa a 1ª posição onde se encontra determinada busca
dentro de uma string.

Veja um exemplo na próxima figura:

ljust: preenche uma string com espaços à esquerda.

rjust: preenche uma string com espaços à direita.

Veja exemplos na próxima figura:

33
3.5 Conversão de valores

Agora veremos como converter números inteiros de bases decimais, binárias e

hexadecimais entre si. Veja este exemplo, que converte números inteiros decimais em
seu valor respectivo em base hexadecimal:

a= int(input("Digite o valor decimal: "))

b = hex(a)

c = b.split('0x')

print ("Valor hexadecimal = ", c[1])

Agora, este outro exemplo, que converte números inteiros binários para seu respectivo
valor em base decimal, com prompt em inglês:

a= input("Digit your binary value: ")

i = int(a, 2)

print ("Decimal value = ", i)

O exemplo a seguir converte números inteiros binários para respectivo valor em base
hexadecimal, com prompt em inglês:

34
a=input('Digit your binary value: ')

b=hex(int(a,2))

c = b.split('0x')

print('Hexadecimal value: ', c[1])

Conclusão

Nesse tópico, você aprendeu mais comandos de uma linguagem de programação. No

próximo tópico, falaremos sobre funções e outros recursos da linguagem Python.

Referência

PERKOVIC, Ljubomir. Introdução à computação usando Python: um foco no

desenvolvimento de aplicações. Rio de Janeiro: LTC, 2016.

35
4 FUNÇÕES E RECURSOS
Nesse tópico, você irá conhecer para que servem as funções em Python, e como elas
facilitam a programação e auxiliam na tarefa de tornar programas menos complexos.
Também irá conhecer a função dos argumentos e parâmetros na linguagem Python,
como usar recursão nessa linguagem, trabalhar com bibliotecas e fazer comentários em
seus programas em Python.

4.1 Funções e procedimentos

Com frequência, há certos trechos em um programa que precisam ser executados várias
vezes, ou algumas vezes. Ao invés de escrevê-los várias vezes no programa, há como
registrá-lo uma só vez e chamá-los quando necessário. A esses "subprogramas" dentro
de um programa principal dá-se o nome de funções.

Há funções nativas no Python, ou seja, aquelas que vêm junto com a linguagem, por
exemplo, as funções type, pow (potenciação), len (medir comprimento de string), entre
outras.

Você pode criar sua própria função. Para fazer isso em Python, deve-se iniciar a função
com o comando def <nome_da_função>(): Exemplo:

def prompt_do_usuário():

a = input(“Digite seu nome: “)

b = input(“Digite sua idade: “)

prompt_do_usuário()

36
No script acima, tudo o que estiver indentado abaixo do nome da função pertence a ela,
e serão as instruções a serem executadas na função. A quarta linha nesse script chama
a função para ser executada, e já não pertence à função.

SAIBA MAIS

Neste livro da Minha Biblioteca, você aprenderá mais sobre funções aplicadas a Python.

PERKOVIC, Ljubomir. Introdução à computação usando Python: um foco no

desenvolvimento de aplicações. Rio de Janeiro: LTC, 2016. p. 70-72. (Minha Biblioteca)

4.2 Atribuição de parâmetros

Algumas funções nativas da linguagem Python requerem argumentos, que são valores
que controlam como essa função faz seu trabalho.

Por exemplo, se você quer achar o cosseno de um número, você deve usar a biblioteca
math, a função cos e indicar o número a que você se refere, por exemplo, math.cos(25).

Deste modo, a função cos recebe um valor numérico, no caso acima o valor é igual a 25,
como um argumento.

Há funções que requerem mais de um argumento; tudo dependerá de como ela foi
escrita.

Parâmetro é o nome da variável que recebe um valor, que é chamado de argumento.

Argumentos e parâmetros exercem uma importante função dentro da linguagem

Python, sendo muito úteis no conceito de orientação a objeto.

37
4.3 Recursão

Recursão é um método de solução de problemas que quebra um problema em

problemas menores até chegar a um ponto em que ele possa ser resolvido facilmente.
Normalmente, a recursão envolve uma função que chama a si mesma. Embora não
pareça, ela nos permite escrever soluções assertivas para problemas que, de outra
forma, seriam muito difíceis de escrever em um programa.

Como exemplo, considere uma função que soma os números de uma lista, escrito a
seguir:

lista = [1, 2, 3, 4, 5]

def somalista(lista):

if len(lista) == 1:

return lista[0]

else:

return lista[0] + somalista(lista[1:])

print('Resultado de somalista:', somalista(lista))

print('Resultado esperado:', sum(lista))

Na linha 3, o programa verifica se a lista possui somente um elemento. Na linha 6, a

função chama a si mesmo, razão pela qual ela é recursiva.

Um programa que calcula um fatorial de um número também usa função recursiva. Veja
um exemplo:

# -*- coding: cp1252 -*-

def fatorial(n):

if n ==1:

return n

else:

38
 return fatorial(n-1) * n

n = float(input("Coloque a número que você quer calcular o fatorial: "))

print(fatorial(n))

Note que a função chama a si mesma subtraindo 1 do argumento n, que é o valor que
você preencherá na variável ao executar o programa.

SAIBA MAIS

Neste vídeo, você aprenderá mais sobre funções recursivas aplicadas a Python.

Vídeo: Aulas Python - 039 - Funções VI: Recursividade

AULAS Python – 039 – Funções VI: recursividade. 2014. Disponível em:

<https://www.youtube.com/watch?v=WAziZkbo5Ss>. Acesso em: 14 fev. 2019.

4.4 Bibliotecas

Bibliotecas são coleções de módulos acessíveis a um programa feito na linguagem

Python (no caso de você usar essa linguagem), ou qualquer outra, criadas para
simplificar o processo de programação e não ter a necessidade de reescrever os
comandos e funções mais usados. As bibliotecas podem ser usadas importando-as no
início de um programa.

Na linguagem Python, o comando usado para importar bibliotecas é o import.

Veja um exemplo de trecho de código com importação de bibliotecas:

import Image

import sys

import os

39
from Crypto.Cipher import AES

IV_SIZE = 16

block_size = 16

As bibliotecas facilitam a programação de um sistema, pois possibilitam o

reaproveitamento de código para outros programas. Há bibliotecas para todo tipo de
desenvolvimento: bibliotecas para trabalhar com imagens; bibliotecas para criptografia;
bibliotecas para trabalhar com documentos do tipo DOCX, XLS, XML, DOC, PDF;
bibliotecas para trabalhar com comandos do seu sistema operacional, entre muitas
outras.

Você pode criar sua própria biblioteca. Veja um exemplo:

Criando uma biblioteca

def media_unisa(a, b):

return (a*0.4)+(b*0.6)

Salve esse script em formato .py; depois faça esse outro script, e salve-o no mesmo local
da biblioteca, também com extensão .py:

import media_unisa_lib

nota1 = float(input("Digite a nota da AVC: "))

nota2 = float(input("Digite a nota da AVG: "))

soma = media_unisa_lib.media_unisa(nota1, nota2)

print ("Resultado = ", soma)

40
Você usou uma biblioteca criada por você para executar um programa de cálculo de
média. Toda universidade que usar o mesmo método de cálculo contido nessa biblioteca
pode empregá-la para compor seus programas de cálculo de média.

4.5 Comentários

Quando temos a necessidade de explicar certas partes de um código, usamos os

comentários, que são trechos escritos no programa que não serão compilados ou
interpretados pelo compilador ou interpretador da linguagem.

Na linguagem Python, para escrevermos comentários, iniciamos esses comentários com

o caractere #.

Veja um exemplo:

print(“Qualquer coisa”) # Esse comando vai mostrar na tela a string “Qualquer coisa”

Tudo o que estiver escrito na linha depois do caractere # será considerado comentário.

Há comentários que são considerados pelo interpretador Python. São os comentários

funcionais. Eles iniciam e terminam com os caracteres -*-. Veja um exemplo muito
usado:

# -*- coding: UTF-8 -*-

Nesse caso, estamos dizendo ao programa que a codificação de teclado a ser usada é a
UTF-8.

Conclusão

Nesse tópico, você aprendeu sobre a importância da linguagem Python e como fazer
uso de suas funções e outros recursos. No próximo tópico você verá como representar
e trabalhar com estruturas de dados na linguagem Python.

41
Referência

PERKOVIC, Ljubomir. Introdução à computação usando Python: um foco no

desenvolvimento de aplicações. Rio de Janeiro: LTC, 2016.

42
5 ESTRUTURA DE DADOS
Neste bloco, você irá aprender como usar estruturas de dados dos tipos tuplas,
dicionários, listas, pilhas, filas e deques; também verá como aplicar o conceito de
matrizes na matemática em criptografia e aplicação prática de estruturas de dados.

5.1 Listas, dicionários e tuplas

Lista é uma sequência ordenada e armazenada de valores, que podem ser do tipo literal
ou numérico, armazenados dentro de colchetes, separados por vírgulas. Cada valor em
uma lista é localizado por um índice. Esses valores são chamados itens ou elementos de
uma lista. Listas também são conhecidas como arrays em outras linguagens de
programação. Exemplo: [1, 2, 3, 4].

Dicionários são valores também ordenados, mas concatenados entre si na estrutura

“chave:objeto”, armazenados dentro de chaves. Exemplo: {1: ‘Genilson’, 2: ‘Genoveva’,
3:’Sanderson’}

Uma tupla é uma sequência ordenada e armazenada de valores semelhante à lista.

Porém, tuplas são imutáveis. São representadas dentro de parênteses, diferente da lista,
que é representada entre colchetes. Exemplo: (‘Genilson’, ‘Sanderson’, ‘Genoveva’)

SAIBA MAIS

Neste vídeo, você aprenderá mais sobre listas, dicionários e tuplas aplicados a Python.

Vídeo: Python – 7 – Set, Tuplas, Dicionários

PYTHON – 7 – Set, Tuplas, Dicionários. Disponível em:

<https://www.youtube.com/watch?v=Rn5GlVSWW7E>. Acesso em: 14 fev. 2019.

43
5.2 Matrizes

São estruturas bidimensionais, semelhantes a tabelas, com colunas e linhas, que contém
valores numéricos. Veja um exemplo:

Em Python, uma matriz pode ser representada por uma lista composta por listas:

matriz = [[1, 5, 8], [6, 7, 4], [3, 9, 1]]

Para realizar operações matemáticas com matrizes, você pode usar a biblioteca numpy;
para tal, importe-a com o comando import numpy.

import numpy

a = [[1,2], [3,4]]

# Transformando a variável em matriz da biblioteca

a = numpy.array(a)

b = [[5, 6], [7, 8]]

b = numpy.array(b)

# Mostrando o resultado da multiplicação de matrizes

print(numpy.dot(a, b))

O seguinte programa no próximo slide mostrará na tela os valores de cada posição da

matriz:

matriz = [[1, 5, 8], [6, 7, 4], [3, 9, 1]]

print(matriz[0][0])

44
print(matriz[0][1])

print(matriz[0][2])

print(matriz[1][0])

print(matriz[1][1])

print(matriz[1][2])

print(matriz[2][0])

print(matriz[2][1])

print(matriz[2][2])

Mas, e se você quiser que o usuário escolha os valores da matriz, preenchendo-os

interativamente? Eis um exemplo de programa que preenche uma matriz 2x2:

# -*- coding: cp1252 -*-

matriz = [[0]*2]+[[0]*2]

print(matriz)

matriz[0][0] = int(input("Digite o valor da posição 0,0 da matriz: "))

matriz[0][1] = int(input("Digite o valor da posição 0,1 da matriz: "))

matriz[1][0] = int(input("Digite o valor da posição 1,0 da matriz: "))

matriz[1][1] = int(input("Digite o valor da posição 1,1 da matriz: "))

print(matriz)

Note que ao invés de usar a multiplicação para criar as linhas da matriz, usamos
concatenação; isso se dá porque se usarmos multiplicação, todas as posições da matriz
serão consideradas 0,0 e 0,1 no caso dessa matriz. Então, somente serão preenchidos
os dois últimos valores que preenchermos no input em todas as posições.

45
5.3 Aplicação prática de matrizes

Agora vamos ver uma aplicação prática de matrizes. Você sabia que dá para criptografar
mensagens usando matrizes? É nisso que se baseia a cifra de Hill. Vejamos:

Escolha uma matriz 2×2 cuja determinante seja diferente de zero. Usaremos esta:

Vamos cifrar a palavra “TOUPEIRA”; atribua um valor numérico de acordo com a posição
de cada letra no alfabeto, e separe as letras em pares:

T-O U-P E-I R-A

20-15 21-16 5-9 18-1

Para codificar o par T-O, efetuamos o produto matricial em modal 26:

Que fornece o valor cifrado H-G (valores 8 e 7, respectivamente).

Para codificar o par U-P, efetuamos o produto matricial:

Que fornece o valor cifrado S-L (valores 19 e 12, respectivamente).

Para codificar o par E-I, efetuamos o produto matricial:

Que fornece o valor cifrado A-K (valores 1 e 11, respectivamente).

Para codificar o par R-A, efetuamos o produto matricial:

46
Que fornece o valor cifrado R-M (valores 18 e 13, respectivamente).

Obtemos então a cifra:

HGSLAKRM.

Para decifrar as cifras de Hill, usamos a matriz inversa (mod 26) da matriz codificadora;
daí a razão da determinante ser diferente de 0, pois só assim uma matriz quadrada é
inversível.

Como estamos trabalhando em mod 26, vamos usar a tabela de inversos multiplicativos
nesse valor modal:

A fórmula para decifrar é:

Aplicando a fórmula:

Pelas equivalências numéricas, o equivalente numérico do texto cifrado HGSLAKRM é:

8-7-19-12-1-11-18-13

47
Para obter os pares de texto plano, multiplicamos cada vetor pela inversa da matriz A:

Que fornece o valor original T-O.

Para obter os pares de texto plano, multiplicamos cada vetor pela inversa da matriz A:

Que fornece o valor original U-P.

Para obter os pares de texto plano, multiplicamos cada vetor pela inversa da matriz A:

Que fornece o valor original E-I.

Para obter os pares de texto plano, multiplicamos cada vetor pela inversa da matriz A:

Que fornece o valor original R-A.

5.4 Pilhas, filas e deques

Pilha é uma lista que permite acesso em somente uma extremidade. Os dados inseridos
vão se “empilhando”, de modo que o último que entrou será o primeiro a sair. Um
exemplo de uso dessa estrutura são as calculadoras que usam notação polonesa inversa
(A HP é uma delas).

Filas são listas em sequências de espera; aumentam através do acréscimo de novos

elementos no final e diminuem com a saída dos elementos da dianteira. Em relação à
pilha, a principal diferença é que na fila o primeiro elemento que entra é o primeiro a
ser retirado. Um exemplo clássico de uso de filas são os softwares simuladores de filas,
para estudo de comportamento de filas em call centers.

48
Deques são listas que permitem remover elementos de qualquer lugar. São usados, por
exemplo, em gerenciamento de memória RAM e em construção de programas diversos.

SAIBA MAIS

Neste vídeo, você aprenderá mais sobre pilhas, filas e deques aplicados a Python.

Vídeo: Estrutura de dados - Pilhas, Filas e Deck

ESTRUTURA de dados - Pilhas, Filas e Deck. 2014. Disponível em:

<https://www.youtube.com/watch?v=Hn_0Jb2f7hY>. Acesso em: 14 fev. 2019.

5.5 Aplicação prática de pilhas, filas e deques

Veja um exemplo de como usar pilhas na vida real: imagine uma calculadora HP. Como
ela processa as informações da expressão matemática a seguir?

((1 + 1) * 4) + 3

Veja na tabela:

1 entra operando 1
1 entra operando 1, 1
+ adicionar 2
4 entra operando 2, 4
* multiplicar 8
3 entra operando 8, 3
+ adicionar 11

Um exemplo prático do uso de filas em computação é a fila de impressão de uma

impressora. Um documento é enviado a uma impressora; se ela estiver imprimindo tal
documento e outro é enviado para impressão, este último fica na fila aguardando a saída
do primeiro para começar a sua.

49
Deques possuem várias aplicações. Quando você termina um processo em um
computador, o espaço da memória RAM que ele estava ocupando é disponibilizado para
uso, podendo ter antes e depois do seu endereçamento outros processos alocados. Essa
é uma operação típica de deques, que permitem adição e remoção de elementos.

Conclusão

Nesse tópico, você aprendeu sobre como trabalhar com estruturas de dados na
linguagem Python. No próximo tópico, você verá como representar e trabalhar com
árvores binárias na linguagem Python.

Referências

PERKOVIC, Ljubomir. Introdução à computação usando Python: um foco no

desenvolvimento de aplicações. Rio de Janeiro: LTC, 2016.

50
6 ÁRVORES BINÁRIAS
Neste bloco, você irá aprender os principais conceitos e aplicações de árvores binárias,
saberá como uma máquina decide qual o menor caminho entre um ponto e outro, e
também como representar árvores binárias em Python.

6.1 Árvores de busca

Quando queremos representar hierarquicamente uma estrutura de dados com mais de

uma dimensão, usamos um tipo de estrutura chamada árvore, que consiste em nós e
arcos.

Veja alguns exemplos de árvores na figura a seguir:

Nota que uma árvore é composta pelo nó raiz, do qual saem todos os outros nós e/ou
folhas.

51
Essa outra figura contém um exemplo de uma árvore que representa a hierarquia de
uma empresa:

Podemos representar valores através da estrutura em árvore. Quando uma árvore

possui em todos os nós da subárvore esquerda valores numéricos inferiores ao nó raiz
e todos os nós da subárvore direita, valores superiores ao nó raiz, e os nós possuem no
máximo duas folhas, ela é definida como árvore binária de busca. Veja um exemplo:

A busca em árvore binária normalmente é feita usando um processo recursivo.

Essa busca começa examinando-se o nó raiz. Se o valor é igual ao valor armazenado na

raiz, a busca se encerra. Se o valor é menor do que a raiz, a busca segue pela ramificação
esquerda. Caso o valor seja maior do que a raiz, a busca segue pela ramificação direita.

52
Esse processo é repetido até que o valor seja encontrado. Se o valor não for encontrado,
então o valor não deve estar presente na árvore.

Uma árvore binária de busca aceita outras operações além de busca. Na inserção, a raiz
é verificada e introduz-se um nó novo na subárvore da esquerda, se o novo valor for
menor do que a raiz, ou na subárvore da direita, se o valor novo for maior do que a raiz.

Na operação remoção, você deve considerar algumas regras:

 Se for para remover apenas uma folha, basta removê-la simplesmente;

 Se for para remover um nó com apenas uma folha, a folha passa a ocupar o lugar
desse nó removido;
 Se for para remover um nó com duas folhas, pode-se substituir o nó a ser retirado
pelo nó sucessor (o nó mais à esquerda da ramificação direita) ou pelo nó antecessor
(o nó mais à direita da ramificação esquerda).

Veja exemplos nas figuras a seguir:

Removendo uma folha

53
Removendo um nó com uma folha

Removendo um nó com duas folhas

SAIBA MAIS

Neste vídeo, você aprenderá mais sobre árvores de busca.

Vídeo: Árvore Binária de Busca

GUERRA, Rodrigo. Árvore binária de busca. 2014. Disponível em:

<https://www.youtube.com/watch?v=XZ0MEDhb4oE>. Acesso em: 15 fev. 2019.

54
6.2 Balanceamento de árvores binárias

Dizemos que uma árvore está balanceada quando a altura das duas subárvores da raiz
for igual a 1, -1 ou 0. Veja um exemplo de uma árvore desbalanceada:

Árvore desbalanceada

Note que a profundidade dessa árvore é desigual, medindo 2 na subárvore direita em

relação à esquerda. Veja agora um exemplo de uma árvore balanceada:

Árvore balanceada

Quando uma árvore está desbalanceada, é preciso balanceá-la. Como? Através de

rotações. Podemos definir rotação como operação que influencia no balanceamento de
uma árvore, sem alterar a sequência de percurso.

Há os seguintes tipos de rotações: esquerda simples, direita simples, esquerda dupla e

direita dupla. Vejamos cada um deles:

55
Rotação à esquerda simples

Rotação à esquerda dupla

Rotação à direita simples

56
Rotação à direita dupla

6.3 Algoritmo de Dijkstra

O algoritmo de Dijkstra, desenvolvido pelo cientista da computação E.W. Dijkstra, é um

algoritmo que calcula o caminho mais econômico em questão de custo entre vértices de
um grafo. Escolhido um vértice como ponto de origem, o algoritmo calcula o custo desse
vértice para todos os vértices do grafo, e escolhe o caminho mais curto e com menor
custo.

Veja os grafos a seguir expondo um problema a ser resolvido com esse algoritmo. Qual
o caminho mais curto em ter os pontos A e F?

57
 Vértice Passo 1 Passo 2 Passo 3 Passo 4 Passo 5 Passo 6
A 0, A - - - - -
B 5, A 5, B 5, B - - -
C 3, A 3, A - - - -
D ∞ 12, C 11, B 11, B - -
E ∞ 14, C 14, C 14, D 14, D -
F ∞ ∞ ∞ 17, D 17, E 17, E

O melhor caminho, partindo de A para chegar até F, é C, B, D, E, F.

6.4 Aplicações práticas de árvores binárias

Podemos citar duas entre várias: jogos de xadrez e futebol de robôs.

No xadrez, a estrutura em árvore permite analisar as possibilidades de movimentos e

posições do tabuleiro em níveis de profundidade. Quando você escolhe os níveis de
dificuldade para vencer seu adversário, jogando contra o computador, quanto mais
elevado o nível, mais profunda é a análise das jogadas feitas pela máquina, ou seja, ela
consegue prever seus próximos lances com mais precisão. Por isso, é mais difícil vencer
a máquina em níveis mais altos, e mais ela demora para jogar, pois precisa analisar mais
possibilidades.

No futebol de robôs, veja a seguinte situação: a partir da figura apresentada a seguir,

qual a melhor rota que o robô deve seguir para pegar a bola?

58
Transformaremos o cenário em um sistema de grafos:

Para mapear o cenário, traçaremos uma reta entre o ponto inicial (robô) e o ponto final
(bola) e também traçaremos retas perpendiculares à essa reta nos outros grafos:

Traçaremos um círculo em torno de cada grafo com distância de 2r (2 vezes seu raio)
para evitar colisões ao estabelecer a rota do robô. Os pontos de intersecção das retas
perpendiculares e os círculos serão considerados grafos do nosso sistema.

59
Então ligamos os grafos uns com os outros a partir do ponto de origem:

Os pontos que cruzarem a zona de segurança (os círculos) serão desconsiderados:

Então ligamos os outros pontos sem passar pelos círculos:

Este é nosso grafo, já com o cálculo dos custos de percurso entre os pontos,
considerando a distância entre eles:

60
Aplicando o algoritmo de Dijkstra, chega-se a esta solução de percurso:

Mostrando no cenário:

6.5 Exemplos de árvores binárias em Python

Como representar e montar uma árvore binária em Python? Veja a seguir.

Nesse programa, usaremos conceito de orientação a objetos para representar a

seguinte árvore binária:

61
Os valores estão em branco, pois iremos escolhê-los durante a execução do programa.
Eis o código:

# -*- coding: cp1252 -*-

class Tree:
def __init__(self, cargo, left=None, right=None):

self.cargo = cargo

self.left = left

self.right = right

def printTreeIndented(tree, level=0):

if tree == None: return

printTreeIndented(tree.right, level+1)

print ' '*level + str(tree.cargo)

printTreeIndented(tree.left, level+1)

def abertura():

a = input("Digite o valor da raiz da árvore: ")

b = input("Digite o valor de uma das folhas: ")

c = input("Digite o valor da outra folha: ")

if b > a and c < a:

tree = Tree(a, Tree(c), Tree(b))

printTreeIndented(tree, level=0)

62
 elif b < a and c > a:

tree = Tree(a, Tree(b), Tree(c))

printTreeIndented(tree, level=0)

else:

print "Os valores devem ser maiores ou menores que a raiz!"

abertura()

abertura()

A saída é mostrada na figura a seguir:

O número mais à esquerda é a raiz; as folhas e nós da ramificação esquerda estão abaixo
do número mais à esquerda; as folhas e nós da ramificação direita estão acima do
número mais à esquerda.

Para criarmos uma árvore com mais ramificações, é só alterarmos o código. Vejamos o
trecho alterado para criarmos uma árvore com uma raiz e quatro elementos, com os
seguintes formatos:

63
(…)

def printTreeIndented(tree, level=0):

if tree == None: return

printTreeIndented(tree.right, level+1)

print ' '*level + str(tree.cargo)

printTreeIndented(tree.left, level+1)

def printTreeIndented1(tree, level=0):

if tree == None: return

printTreeIndented1(tree.left, level+1)

print ' '*level + str(tree.cargo)

printTreeIndented1(tree.right, level+1)

def abertura():

a = input("Digite o valor da raiz da árvore: ")

b = input("Digite o valor de um nó: ")

c = input("Digite o valor de um nó: ")

64
d = input("Digite o valor de uma das folhas: ")

e = input("Digite o valor de uma das folhas: ")

if b > a and c > b > a and d > c > a and e > d > a:

tree = Tree(a, Tree(b, Tree(c, Tree(d, Tree(e)))))

#tree = Tree(a, Tree(c), Tree(b))

printTreeIndented(tree, level=0)

elif b < a and c < b < a and d < c < a and e < d < a:

tree = Tree(e, Tree(d, Tree(c, Tree(b, Tree(a)))))

printTreeIndented1(tree, level=0)

elif b < a and c < b < a and d < c < e and e > c < b and e > c > d and e > d:

tree = Tree(a, Tree(b, Tree(c, Tree(d), Tree(e))))

printTreeIndented(tree, level=0)

elif b > a and c > b > a and d < c < e and e > c > b and e > c > d and e > d:

tree = Tree(a, Tree(b, Tree(c, Tree(d), Tree(e))))

printTreeIndented1(tree, level=0)

elif a > b > d and b > d and a < c < e and c < e:

tree = Tree(a, Tree(c, Tree(e)), Tree(b, Tree(d)))

printTreeIndented1(tree, level=0)

else:

print "Os valores devem ser maiores ou menores que a raiz!"

65
 abertura()

abertura()

Conclusão

Neste bloco, você aprendeu sobre como trabalhar com árvores binárias, seus principais
conceitos e aplicações práticas e também como representá-las na linguagem Python.
Por aqui terminamos esta disciplina. Nos vemos nas avaliações!

Referências

CAPUTO, Rodrigo. Algoritmo de Dijkstra. 2012. Disponível em:

<https://www.youtube.com/watch?v=J4TZgD 1As0Q>. Acesso em: 20 dez. 2018.

DROZDEK, Adam. Estrutura de Dados e Algoritmos em C++. Tradução de Roberto

Enrique Romero Torrejon. São Paulo: CENGAGE, 2017.

PERKOVIC, Ljubomir. Introdução à computação usando Python: um foco no

desenvolvimento de aplicações. Rio de Janeiro: LTC, 2016.

66