Neste texto apresentamos uma visão geral da linguagem Python para professores que vão ministrar algoritmos ou estruturas de dados em Python e que têm experiência com o ensino usando C. O objetivo é esclarecer alguns pontos e mostrar como as construções algorítmicas de C podem ser expressas em Python. Note que o objetivo não é apresentar todas as construções do Python e nem descrever uma metodologia de ensino de algoritmos e estruturas de dados.
Começamos com algumas diferenças entre as duas linguagens, depois discutimos as principais construções do Python, em seguida mostramos a implementação de alguns algoritmos e estruturas de dados e por fim apresentamos algumas convenções de código para Python e indicamos algumas referências.
As linguagens Python e C têm muitos aspectos distintos, pois são comumente usadas em situações distintas. Nessa seção discutimos algumas dessas diferenças. Usamos os seguintes exemplos para ilustrar algumas dessas diferenças.
Código em C
#include <stdio.h>
/*
* Devolve a quantidade de items em valores que estão no intervalo [min, max].
*
* n é quantidade de items em valores que é analisada.
*/
int conta_no_intervalo(int* valores, int n, int min, int max)
{
// O correto seria declarar n, i, quant e o retorno da função como size_t.
// Veja https://stackoverflow.com/q/66527638/5189607
int quant = 0;
for (int i = 0; i < n; i++) { // as chaves poderiam ser omitidas nesse caso
if (min <= valores[i] && valores[i] <= max)
quant++;
}
return quant;
}
int main(int argc, char* argv[])
{
printf("Este programa conta a quantidade de valores em um determinado intervalo.\n");
int n;
printf("Digite a quantidade de valores: ");
if (scanf("%d", &n) != 1 || n <= 0) {
printf("Valor inválido.\n");
return 1;
}
// Alocação dinâmica implícita na pilha
int valores[n];
// Ou alocação explícita no heap
// int* valores = (int *) malloc(n * sizeof(int));
// O retorno de scanf não é verificado nas
// próximas chamadas para simplificar o código.
printf("Digite %d número(s) separados por espaço.\n", n);
for (int i = 0; i < n; i++) {
scanf("%d", &valores[i]);
}
int min;
printf("Digite o limite inferior do intervalo: ");
scanf("%d", &min);
int max;
printf("Digite o limite superior do intervalo: ");
scanf("%d", &max);
printf("Existe(m) %d valor(es) no intervalo.\n", conta_no_intervalo(valores, n, min, max));
// Desalocação explícita no caso de alocação no heap
// free(valores);
}Código em Python
def conta_no_intervalo(valores: list[int], min: int, max: int) -> int:
'''
Devolve a quantidade de items em *valores* que estão no intervalo [min, max].
Exemplo
>>> conta_no_intervalo([2, 5, 1, 4, 6, 8], 2, 6)
4
'''
quant = 0
# Com tipo explícito
# quant: int = 0
for valor in valores:
if min <= valor and valor <= max:
# Com comparações encadeadas
# min <= valor <= max
quant = quant + 1
# Com atribuição com incremento
# quant += 1
return quant
def main():
print('Este programa conta a quantidade de valores em um determinado intervalo.')
s = input('Digite os valores separados por espaço: ')
valores = []
for valor in s.split():
valores.append(int(valor))
min = int(input('Digite o limite inferior do intervalo: '))
max = int(input('Digite o limite superior do intervalo: '))
print('Existe(m)', conta_no_intervalo(valores, min, max), 'valor(es) no intervalo.')
if __name__ == "__main__":
main()A sintaxe do C é baseada em blocos delimitados por chaves ({}), a indentação do
código não influencia a semântica. As chaves são opcionais nas
instruções de controle quando apenas uma sentença é especificada. Na
definição de estruturas e funções as chaves são sempre necessárias. As
expressões/sentenças das instruções de controle devem ser especificadas
entre parênteses. Os operadores lógicos são especificados com símbolos
(!, ||, &&).
Os blocos em Python inciam com “:” e são delimitados pela indentação.
As expressões/sentenças das instruções de controle não precisam ser
especificadas entre parênteses. Os operados lógicos são especificados
com as palavras chaves not, or e and.
Em Python os operadores relacionais pode ser encadeados, dessa forma
é possível escrever a < b < c
ao invés de a < b and b < c.
Em C os tipos das variáveis são especificadas antes do nome da
variável. Já em Python, os tipos são especificados após o nome da
variável, pela sintaxe : tipo. As
especificação do tipo em C é obrigatória, em Python é opcional. Aspectos
da semântica de tipos são discutidas na seção .
Python utiliza a palavra chave def para
definições de funções e o tipo de retorna da função é especificado com
-> tipo
Em Python não existe operadores de pós e pré incremento/decremento, mas existem os operadores de atribuição com incremento/decremento (entre outros).
Strings em Python podem ser especificadas com aspas (") ou
apóstrofo ('). Strings
com múltiplas linhas são especificadas com três aspas ou apóstrofos.
Em C existem dois tipos de comentário, o de linha (//) e o de bloco
(/* */).
Python também tem dois tipos de comentário, o de linha (#) e o de
documentação (''' '''),
que deve aparecer apenas como primeiro item de uma definição.
C é usado comumente como um linguagem compilada. Isso implica que
para testar qualquer trecho de código em C é necessário escrever um
programa completo (com função main), compilar e depois
executar o programa. Além disso, para exibir o valor de uma variável é
necessário chamar uma função como printf explicitamente
(também é possível consultar os valores das variáveis usando um
depurador).
Já o Python é usado comumente como uma linguagem interpretada de duas
maneira, a primeira é especificando o nome de um arquivo
.py, nesse caso o código do arquivo é executado diretamente
(compilado para código de uma máquina virtual e depois executado).
A segunda maneira é sem especificar um arquivo, nesse caso é iniciado
um modo interativo para avaliação de trechos de código (REPL - Read,
Eval, Print and Loop). O prompt padrão é identificado com
>>>. O usuário digita um trecho de código, que é
executado e o resultado é exibido em seguida. Por exemplo
>>> 'Resposta ' + str(2 + 10 * 4)
'Resposta 42'O modo interativo é uma ferramente muito valioso, pois permite a rápida exploração do funcionamento de trechos de código, mas é importante instruir o aluno a usar esse modo apenas para exploração e não desenvolvimento do código final (a escrita do programa deve ser feita seguindo o processo de projeto de programas).
Não é necessário uma função main em Python, mas é uma
boa prática criar uma e chamá-la explicitamente (como no exemplo do
início dessa seção – documentação).
O Python tem alguns mecanismos para escrita e execução de testes, o
mais simples é o doctest. Os exemplos escritos na
documentação podem ser executados e verificados de forma automática. Por
exemplo, se a função conta_no_intervalo está em um arquivo
chamado x.py, os exemplos podem ser verificados com o
comando python -m doctest -v x.py.
C é comumente classificada como estaticamente tipada, isto é, os
tipos são vinculados as variáveis em tempo de compilação (note que void*
é um escape para essa regra que é amplamente utilizado pelas funções da
biblioteca padrão, entre elas malloc/free). Os
compiladores de C detectam muitos erros de tipo durante a compilação, no
entanto, C permite a conversão implícita entre muitos tipos de dados, o
que diminui a confiabilidade e pode ser confuso para o aluno iniciante
(por exemplo, double e float para int, arranjos para
ponteiros, etc).
Historicamente Python tem sido classificada como dinamicamente
tipada, isto é, os tipos são vinculados em tempo de execução aos valores
e não as variáveis. Isso implica, por exemplo, que uma mesma variável
pode em momentos distintos armazenar valores de tipos distintos. Python
tem algumas conversões implícitas de valores (como int para float), mas
menos do que C, por esse e outro motivos, o Python é considerado mais
fortemente tipada do que C.
Atualmente o Python suporta a especificação de tipos tanto de variáveis como funções. Essa característica foi adicionada inicialmente no Python 3.5 (lançado em 2015) e têm sido aprimorado a cada versão (o Python 2 não suporta especificação de tipos).
O interpretador padrão do Python
ignora todas as anotações de tipos, mas existem ferramentes que podem
utilizar essas anotações para fazer verificações estáticas no código.
Uma dessas ferramentes é o mypy. O
mypy faz uma verificação estática dos tipos e indica os
erros se forem encontrados. Por exemplo, no código a seguir, declaramos
n como inteiro mas estamos atribuindo um ponto flutuante, o
quê o mypy identifica como erro.
n: int = 10.2Dessa forma, usando o mypy, podemos desenvolver os
programas em Python como se eles fossem estaticamente tipados, mesmo que
de fato as anotações de tipo não alterem a forma como o programa é
executado. O sistema de tipos do mypy é muito poderoso e
permite expressar muitas restrições estaticamente. A seção apresenta
mais informações sobres essas questões.
Outro aspecto diferente entre as duas linguagem é que em C todos os tipos são “tipos valores”, enquanto que em Python os tipos são “tipos referências”.
O principal efeito dessa diferença é visto na atribuição e na passagem de parâmetros. Discutimos essa questão na próxima seção.
Como em C “tudo é um valor”, todas as atribuições e passagem de parâmetros são feitas por cópia (não tem referência!). No entanto, o uso de ponteiros permite contornar essa limitação, pois a cópia de um ponteiro em uma atribuição ou passagem de parâmetro acaba tendo o mesmo efeito de referências múltiplas para o mesmo valor.
Já em Python como “tudo
é uma referência”, todas as atribuições e passagem de parâmetros são
feitas por referência. Os operadores is e is not
são usados para verificar se duas referências são iguais (referenciam o
mesmo objeto). O exemplo a seguir mostra como as atribuições de
referências funcionam e a diferença entre igualdade de referências e
igualdade de valores.
>>> x = [1, 4]
>>> # y passa a referenciar o mesmo valor referenciado por x
>>> y = x
>>> # is produz True se as referências referenciam o mesmo valor
>>> x is y
True
>>> # == produz True se os dois valores referenciados são iguais
>>> x == y
True
>>> # Alteração da lista referenciada por x, que também é referenciada por y
>>> x.append(6)
>>> x
[1, 4, 6]
>>> y
[1, 4, 6]
>>> x is y
True
>>> x == y
True
>>> # x passa a referenciar uma nova lista, y não é alterado
>>> x = [1, 4, 6]
>>> y
[1, 4, 6]
>>> # Os valores referenciados por x e y são iguais
>>> x == y
True
>>> # As referências não são iguais
>>> x is y
False
>>> x is not y
TrueOs tipos em Python podem ser mutáveis ou imutáveis. Os tipos numéricos, strings, tuplas, entre outros, são imutáveis, ou seja, dado uma referência para um número, não é possível alterar esse número. Já as listas, conjuntos, dicionários e outros tipos são mutáveis. Uma consequência disso é que se um valor de tipo imutável é passado como parâmetro, não é possível devolver um resultado alterando esse valor (pois o tipo é imutável). Outra consequência é que para passar parâmetros de tipos mutáveis por cópia, é preciso fazer a cópia explicitamente.
Considere por exemplo a implementação de uma função de busca em um
TAD de dicionário (string para inteiro). Os argumentos de entrada seriam
o dicionário e a chave e a saída uma indicação se existe um elemento
associado com a chave e qual é o elemento. Em C poderíamos definir uma
função que devolve bool indicando o
resultado da busca e utilizar um argumento do tipo ponteiro para inteiro
para indicar o elemento encontrado. A assinatura da função seria algo
como
/* Devolve true se chave está presente em dic, false caso contrário.
* Se a chave estiver presente, o valor associado com a chave é
* armazenado em valor.
*/
bool busca_chave(Dicionario *dic, char* chave, int* valor);Em Python não é possível fazer dessa forma. Considere uma função com a assinatura
def busca_chave(dic: Dicionario, chave: str, valor: int) -> boolSe um inteiro é atribuído para valor no corpo de
busca_chave, valor passa a referenciar um novo
valor, o valor referenciado anteriormente permanece inalterado (números
são imutáveis). Discutimos uma forma de resolver essa situação na seção
.
Os objetos em C podem ser alocados na pilha ou no heap. A alocação/desalocação dos objetos na pilha é feita automaticamente pelo ambiente de execução. Já a alocação/desalocação de objetos no heap deve ser feita de forma explícita pelo programador.
Em Python todos os objetos são alocados implicitamente no heap. A desalocação é feita de forma automática usando uma combinação de contagem de referências e coleta de lixo. Dessa forma, dois dos erros mais comuns em C, a tentativa de desalocação de memória já desalocada e a tentativa de uso de memória já desalocada, não podem acontecer em Python. (Um outro erro comum em C, acesso de arranjo fora do intervalo válido, é detectado e reportado com uma exceção em Python, conforme discutido na seção ).
A biblioteca padrão de C é pequena quando comparada com outras linguagens. Ela inclui diversas funções para comunicação com o sistema operacional, alguns funções para strings e números e poucas funções algorítmicas e de estruturas de dados.
Por outro lado, o Python tem uma biblioteca padrão bastante extensa, que é um dos motivos pelos quais o Python é bastante utilizado. No entanto, também pode ser motivo de preocupação para alguns professores, pois existe a possibilidade dos alunos usarem as funcionalidade prontas e deixarem de implementar coisas que são importante para o aprendizado. Mas isso não precisa ser dessa forma, o professor pode deixar claro o que pode ou não ser usado e o que é importante implementar.
Nas próximas duas seção mostramos um subconjunto do Python e como esse subconjunto pode ser usado na implementação de alguns algoritmos e estruturas de dados.
O Python é uma linguagem extensa e tem uma biblioteca padrão extensa.
O sistema de tipos do mypy é bastante poderoso e também
extenso. Dessa forma, para evitar que os alunos se percam na linguagem e
deixem de focar nos fundamentos, é importante delimitar um subconjunto
das construções da linguagem para ser utilizado pelos alunos.
Apresentamos a seguir um subconjunto suficiente para escrever qualquer algoritmo e estruturas de dados. Note que o código escrito nesse subconjunto pode ficar um pouco mais extenso e não ser considerado idiomático (pythônico) pela comunidade.
Nesta seção apresentamos alguns dos principais tipos pré-definidos em Python e algumas operações sobre esses tipos.
Os principais tipos
numéricos em Python são int e float. O tipo
int
representa inteiros de tamanho arbitrário enquanto float números
de pontos flutuantes no padrão IEEE 754 binary64 (mesmo que o double em C).
Além das quatro operações básicas, outras operações comuns em Python
com números são a de módulo (%),
exponenciação (**) e piso da
divisão (//). O operador
/ sempre
gera um float como
resposta, mesmo que os operandos sejam inteiros. Outras operações
matemáticas estão disponíveis no módulo math.
Em operações aritméticas que envolvem inteiros e floats, os inteiros são convertidos para floats antes da execução das operações.
A seguir mostramos alguns exemplos com valores numéricos.
>>> # Soma
>>> 4 + 2
6
>>> 4 + 2.0
6.0
>>> # Divisão
>>> 7 / 2
3.5
>>> # Piso da divisão
>>> 14 // 3
4
>>> 5 // 1.3
3.0
>>> # Módulo
>>> 14 % 3
2
>>> 5 % 1.3
1.0999999999999999
>>> -7 % 5
3
>>> # Exponenciação
>>> 2 ** 80
1208925819614629174706176
>>> # Arredondamento, piso e teto
>>> round(3.4)
3
>>> round(3.5)
4
>>> round(3.5134, 2)
3.51
>>> import math
>>> math.floor(4.2)
4
>>> math.ceil(4.2)
5
>>> # Conversão entre int e float
>>> int(7.6)
7
>>> float(4)
4.0
>>> # Conversão entre números e str
>>> str(10)
'10'
>>> int('123')
123
>>> str(3.2)
'3.2'
>>> float('5.6')
5.6Os booleanos
são representados pelo tipo bool, e podem
assumir os valores True ou False. As
operações com booleanos são not, and e or.
>>> not 3 > 5
True
>>> 3 > 5 or 3 < 5
True
>>> # and tem prioridade sobre or
>>> True or False and False
TrueAs strings
são representadas pelo tipo str
(armazenadas em utf-8). As strings são imutáveis em Python. Algumas
operações comuns com strings são mostradas a seguir.
>>> # Concatenação
>>> 'Idade: ' + str(32)
'Idade 32'
>>> # Repetição
>>> 'abc' * 3
'abcabcabc'
>>> 'nada' * -1
''
>>> # Remoção de espaços da direita e esquerda
>>> ' alguns espaços '.strip()
'alguns espaços'
>>> # Versão com chamada na forma de função ao invés de método
>>> str.strip(' alguns espaços ')
'alguns espaços'
>>> # Substring
>>> din = 'departamento de informatica'
>>> din[13:15] # inicio:fim, inicio está incluido e fim não está
'de'
>>> # Quantidade de caracteres (code points)
>>> len('teste')
5
>>> # Verificação se uma string é substring de outra
>>> 'este' in 'um teste simples'
TrueO Python não tem um tipo específico para representar um caractere, strings com um code point são usadas com esse propósito.
O tipo mais comum para sequência
de valores é o tipo list. O tipo
list
representa arranjos dinâmicos (os elementos são contíguos). Python não
tem um tipo para arranjos de tamanho fixo. Os elementos de list são
indexados a partir de 0 e o acesso é
checado, se o índice estiver fora da faixa, uma exceção é lançada.
Algumas operações com listas são mostradas a seguir.
>>> # Inicialização com alguns elementos
>>> lst = [3, 2, 4]
>>> # Acesso pelo índice
>>> lst[0]
3
>>> lst[2]
4
>>> lst[5]
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
IndexError: list index out of range
>>> # Quantidade de elementos - tempo O(1)
>>> len(lst)
3
>>> # Verificação de pertinência
>>> 2 in lst
True
>>> 7 in lst
False
>>> 7 not in lst
True
>>> # Inicialização sem nenhum elemento
>>> lst = [] # ou list()
>>> # Adição de elemento no final - tempo amortizado de O(1)
>>> lst.append(3)
>>> lst.append(1)
>>> lst
[3, 1]
>>> # Concatenação gerando uma nova lista
>>> lst + [4, 0, 1]
[3, 1, 4, 0, 1]
>>> # Concatenação alterando a lista
>>> lst.extend([4, 0, 1])
>>> lst
[3, 1, 4, 0, 1]
>>> # Remoção do final - tempo O(1)
>>> lst.pop()
1
>>> lst
[3, 1, 4, 0]
>>> # Criação de cópia - tempo O(n)
>>> lst.copy()
[3, 1, 4, 0]
>>> # Sublista
>>> lst[1:3]
[1, 4]
>>> # Remoção de todos os elementos - tempo O(n)
>>> lst.clear()
>>> lst
[]
Repetição de elementos
Assim como o tipo str, o tipo
list
também tem operação de repetição de elementos. A operação de repetição é
geralmente utilizada para inicializar uma lista com uma quantidade
pré-definida de elementos, conforme os exemplos abaixo
>>> # Inicialização com 5 zeros
>>> lst = [0] * 5
>>> lst
[0, 0, 0, 0, 0]
>>> # Modificação da lista
>>> lst[0] = 10
>>> lst[4] = 2
>>> lst
[10, 0, 0, 0, 2]Apesar de útil, é preciso cuidado para usar essa operação. A questão é que, conforme discutido nas seções e , todos os tipos em Python são tipos referências, dessa forma, quando os elementos de uma lista são repetidos, o que de fato está sendo repetido (copiado) são as referências para os elementos. Para tipos imutáveis, como no exemplo anterior, isso não é um problema, mas para tipos mutáveis, isso pode gerar resultados inesperados.
A seguir apresentamos uma tentativa de inicializar uma lista de
listas (arranjo bidimensional 3 x 3). Usamos a variável
linha para ficar mais claro o ponto que vamos destacar, mas
não é necessário, poderíamos escrever m = [[0, 0, 0]] * 3
e a questão seria a mesmo.
>>> linha = [0, 0, 0]
>>> m = [linha] * 3
>>> m
[[0, 0, 0], [0, 0, 0], [0, 0,0]]Por enquanto, parece que está tudo certo. No entanto, se notarmos que
linha, m[0], m[1] e
m[2] referenciam a mesma lista (objeto), então sabemos que
uma mudança feita nessa lista por qualquer dessas variáveis, será
refletida em todas as outras!
>>> m[0][0] = 3
>>> m
[[3, 0, 0], [3, 0, 0], [3, 0, 0]]Como proceder nesse caso? Existem formas compactas para fazer isso em Python, mas não são discutidas nesse texto. Usando apenas as construções mais básicas podemos fazer
m = []
for i in range(3):
linha = []
for j in range(3):
linha.append(0)
m.append(linha)
Mistura de tipos
Nós vimos na seção que Python é geralmente utilizada como uma linguagem com vinculação dinâmica de tipo, isto é, os tipos são associados aos valores, não as variáveis. Uma consequência desse fato é que os valores em uma lista podem ter tipos distintos, ou mesmo mudarem de tipo, como no exemplo a seguir:
>>> # Mistura de valores com tipos diferentes
>>> lst = [10, 'casa', False]
>>> # Alteração do tipo do valor armazenado em 0
>>> lst[0] = [1, 2]
>>> lst
[[1, 2], 'casa', False]Embora este tipo de construção seja permitida, ela pode ser confusa
se usada de forma arbitrária, por isso é importante estabelecer um
fundamento sobre a utilidade desse tipo de construção. Discutimos essa
questão mais a fundo na seção , por hora, podemos usar anotações de
tipos e o programa mypy para identificar como erro esse
tipo de construção. Por exemplo, se quiséssemos restringir os tipos de
lst para inteiros, escreveríamos:
lst: list[int] = [10, 'casa', False]Nesse caso, o seguinte erro seria gerado pelo mypy:
x.py:1: error: List item 1 has incompatible type "str"; expected "int" [list-item]
Found 1 error in 1 file (checked 1 source file)Note que só é possível usar o mypy para processar
arquivos .py, não é possível utilizar o mypy
no modo interativo. É importante lembrar também que o interpretador
padrão do Python ignora as anotações de tipo, então, mesmo que o
mypy indique erro, o código é executado pelo interpretador
(gerando erro apenas quando uma operação é invocada com tipos
inválidos).
Nessa seção apresentamos as principais estruturas de controle do Python.
A funções em Python são definidas com a palavra chave def. A palavra
chave return é usada
para indicar o valor produzido pela função e pode ser usada mais que uma
vez no corpo da função. Funções que não produzem valores explicitamente
(não usam return)
produzem como saída o valor None. O exemplo
a seguir mostra a definição de uma função:
def par(n: int) -> bool:
'''
Produz True se *n* é par, isto é, *n* é múltiplo de 2. False caso contrário.
Exemplos
>>> par(10)
True
>>> par(3)
False
>>> par(0)
True
'''
return n % 2 == 0A principal estrutura de seleção do Python é o if, (o Python
3.10 introduziu a construção match/case, que
é de certa forma similar ao switch/case
do C, mas mais geral).
Assim como no if do C, a cláusula
else do
if do
Python é opcional. Para evitar o aumento de níveis na indentação de
ifs
aninhamos, o Python permite a união de um else seguido de
if com a
palavra chave elif. O exemplo
a seguir mostra o uso do if.
def sinal(n: int) -> int:
'''
Devolve o sinal de *n*, isto é, 1 se n > 0, -1 se n < 1, 0 se n == 0.
Exemplos
>>> sinal(3)
1
>>> sinal(0)
0
>>> sinal(-4)
-1
'''
if n > 0:
return 1
else:
if n < 0:
return -1
else:
return 0
# Ou usando o elif
# if n > 0:
# return 1
# elif n < 0:
# return -1
# else:
# return 0O for
clássico do C não existe em Python. Em Python o for é usado
para fazer iteração pelos elementos de uma estrutura de dados. A outra
forma de repetição do Python é o while. O
exemplo a seguir mostra o uso do for e do while.
def ordena(nomes: list[str]) -> list[str]:
'''
Cria uma nova lista com os mesmos elementos de *nomes* mas em ordem alfabética.
Exemplo
>>> ordena(['Paulo', 'Ana', 'Maria', 'João'])
['Ana', 'João', 'Maria', 'Paulo']
'''
r = []
for nome in nomes:
r.append(nome)
i = len(r) - 1
# r[i] é o nome que foi inserido
# troca r[i] com r[i - 1] até que ele fique na posição adequada
while i > 0 and r[i - 1] > r[i]:
ri = r[i]
r[i] = r[i - 1]
r[i - 1] = ri
i = i - 1
return rQuando for necessário o índice dos elementos em uma iteração, podemos
usar o while ou o
for
combinado com a função range.
def indice_maximo(valores: list[float]) -> int:
'''
Encontra o índice do valor máximo em *valores*.
Caso o valor máximo ocorra em mais de um índice,
o menor índice é devolvido.
Requer que valores não seja vazio.
Exemplos
>>> indice_maximo([2, 1, 4, -2])
2
>>> indice_maximo([-1, -4, -1])
0
'''
assert len(valores) != 0, "valores não pode ser vazio"
imax = 0
for i in range(1, len(valores)):
if valores[imax] < valores[i]:
imax = i
return imaxNo exemplo anterior usamos uma outra estrutura de controle, o assert. O assert pode ser
usado com uma ou duas expressões. O Python avalia a primeira expressão,
se o resultador for True, a
execução continua para a próxima linha, caso contrário, uma exceção é
gerada com uma mensagem padrão ou com o resultado da segunda expressão
do assert
(se existir).
Python é uma linguagem multiparadigma, mas a forma de criação de tipos é através de classes. De fato, quase tudo em Python é um objeto, com atributos e métodos. Por exemplo, valores inteiros são objetos e podemos invocar métodos com eles:
>>> # Invoca explicitamente o método __add__ (operação +)
>>> x = 1
>>> x.__add__(2) # ou (1).__add__(2)
3Antes de vermos a forma geral de definição de classes, vamos ver formas simplificadas que são similares a definição de estruturas e enumerações em C.
Uma forma simplificada de declarar uma classe é usando o decorador @dataclass.
Um decorador é um mecanismo de meta-programação utilizado para modificar
classes, métodos e atributos. Embora o funcionamento dos decoradores
possa ser bastante elaborado, o seu uso em geral é direto e simples.
Utilizamos o decorador @dataclass
quando queremos criar uma classe que se comporte de forma semelhante a
uma struct em
C. No exemplo a seguir criamos uma classe ponto e mostramos algumas
operações:
from dataclasses import dataclass
@dataclass
class Ponto:
x: int
y: int
>>> # Construtor
>>> p = Ponto(10, 20)
>>> p.x
10
>>> p.y
20
>>> p.x = p.x + 1
>>> p
Ponto(x=11, y=20)
>>> # Comparação
>>> p == Ponto(11, 20)
TrueObserve que uma classe criada com @dataclass tem
construtor (que recebe todos os campos como parâmetro na ordem que eles
foram definidos), operador de igualdade (que compara os valores de cada
campo), entre outras operações.
O exemplo a seguir mostra a definição de uma classe e o seu uso em uma função (note a forma dos exemplos):
from dataclasses import dataclass
@dataclass
class Desempenho:
'''O desempenho de um time em um campeonato de futebol'''
# O nome do time
time: str
# Pontos (3 por vitória e 1 por empate)
pontos: int
# Saldo de gols (gols pro - gols contra)
saldo: int
def atualiza_desempenho(d: Desempenho, gols_pro: int, gols_contra: int):
'''
Atualiza o desempenho *d* considerando *gols_pro* e *gols_contra*.
O saldo de gols é atualizado somando *gols_pro* e subtraindo *gols_contra*.
Se *gols_pro > gols_contra*, o número de pontos aumenta em 3.
Se *gols_pro == gols_contra*, o número de pontos aumenta em 1.
Exemplos
>>> d = Desempenho('Maringá', 0, 0)
>>> # Vitória
>>> atualiza_desempenho(d, 5, 1)
>>> d
Desempenho(time='Maringá', pontos=3, saldo=4)
>>> # Empate
>>> atualiza_desempenho(d, 2, 2)
>>> d
Desempenho(time='Maringá', pontos=4, saldo=4)
>>> # Derrota
>>> atualiza_desempenho(d, 0, 3)
>>> d
Desempenho(time='Maringá', pontos=4, saldo=1)
'''
d.saldo = d.saldo + gols_pro - gols_contra
if gols_pro > gols_contra:
d.pontos = d.pontos + 3
elif gols_pro == gols_contra:
d.pontos = d.pontos + 1Outra forma simplificada para criar classe é usando o Enum. Usamos essa
forma quando queremos criar um tipo enumerado, isto é, quando os valores
permitidos para o tipo podem ser enumerados explicitamente. Classes
criadas com esse mecanismos são semelhantes a tipos criados com enum em C. No
exemplo a seguir, mostramos a declaração e uso de uma classe para um
tipo enumerado (observe que, por convenção, escrevemos os valores
enumerados em maiúsculas).
from enum import Enum, auto
class Cor(Enum):
'''
Representa a cor de um semáforo.
'''
VERMELHO = auto()
AMARELO = auto()
VERDE = auto()
def proxima_cor(c: Cor) -> Cor:
'''
Determina a próxima cor de um semáforo que está na cor *c*.
Exemplos
>>> proxima_cor(Cor.VERMELHO).name
'VERDE'
'''
if c == Cor.VERMELHO:
return Cor.VERDE
elif c == Cor.AMARELO:
return Cor.VERMELHO
elif c == Cor.VERDE:
return Cor.AMARELOAlém do campo name, cada valor
da enumeração também tem um campo value, que é um valor inteiro gerado
automaticamente (podemos indicar os valores de cada item da enumeração
diretamente ao invés de usar o auto na declaração).
O mypy é bastante robusto na verificação do uso de
enumerações, especialmente se todos os valores estão sendo considerados.
Use o verificador online do
mypy e teste o código anterior removendo algum dos casos e
observe o erro gerado.
As uniões em
Python são discriminadas (contém um rótulo que diz o tipo armazenado) e
são usadas em diversas situações. O operador | (a partir do
Python 3.10) é utilizado para especificar a união de tipos e a função
isinstance é
utilizada para verificar o tipo (rótulo) de um valor. O exemplo a seguir
mostra o uso de uniões (\ é usado para
permitir que a expressão continue na próxima linha).
from dataclasses import dataclass
@dataclass
class Envelope:
comprimento: int
largura: int
@dataclass
class Caixa:
comprimento: int
largura: int
altura: int
@dataclass
class Rolo:
comprimento: int
diametro: int
'''Uma embalagem para envio nos correios.'''
Embalagem = Envelope | Caixa | Rolo
def dentro_limites(emb: Embalagem) -> bool:
'''
Produz True se *emb* está dentro dos limites, False caso contrário.
Uma embalagem está dentro dos limites se suas medidas obedecem as seguintes
restrições (em cm).
mínimo máximo
Envelope
comprimento 16 60
largura 11 60
Caixa
comprimento 15 100
largura 10 100
altura 1 100
Rolo
comprimento 18 100
diametro 5 21
Exemplos (alguns omitidos para diminuir o espaço)
>>> dentro_limites(Envelope(20, 40))
True
>>> dentro_limites(Envelope(15, 40))
False
>>> dentro_limites(Caixa(30, 40, 80))
True
>>> dentro_limites(Caixa(30, 101, 80))
False
>>> dentro_limites(Rolo(50, 18))
True
>>> dentro_limites(Rolo(50, 4))
False
'''
if isinstance(emb, Envelope):
return 16 <= emb.comprimento <= 60 and \
11 <= emb.largura <= 60
elif isinstance(emb, Caixa):
return 15 <= emb.comprimento <= 100 and \
10 <= emb.largura <= 100 and \
1 <= emb.altura <= 100
elif isinstance(emb, Rolo):
return 18 <= emb.comprimento <= 100 and \
5 <= emb.diametro <= 21Um uso bastante comum de uniões é na representação de ausência de valores. Por exemplo, um nó em uma lista pode ou não ter um próximo elemento, um nó em uma árvore binária pode ou não ter filhos a direita e a esquerda, uma busca em um dicionário pode ou não encontrar um valor associado com uma chave (veja a seção ), etc. Para ilustrar de forma breve esse uso, mostramos a seguir a assinatura de uma função que busca o valor associado com uma chave em um dicionário, exemplos completos são apresentados na seção .
def busca_chave(dic: Dicionario, chave: str) -> None | int:
'''Devolve o valor associado com chave em dic, ou None se chave não estiver em dic.'''Assim como para enumerações, o mypy também é bastante
robusto no tratamento de uniões devido a análise de refinamento
de tipos. No exemplo da embalagem, o mypy só permite
que o campo diametro seja
acessado através da variável emb
se ele puder provar que emb é uma
instância de Rolo, que é o caso
no exemplo devido ao if. Use o
verificador online do
mypy e tente construções inválidas que só seriam
identificas pelo Python em tempo de execução e veja que o
mypy identifica essas construções de forma estática.
O refinamento de tipos é bastante útil, e nos permite, por exemplo, garantir que não haverá acesso a referências nulas em tempo de execução (como mostrado na seção )
A forma geral para definição de tipos em Python é a construção class. A seguir
mostramos a declaração de uma classe e um método e alguns exemplos de
uso:
class Ponto:
x: int
y: int
# Construtores que recebem parâmetros precisam ser criados explicitamente
# O parâmetro self é a instância do ponto que está sendo inicializada
def __init__(self, x: int, y: int):
self.x = x
self.y = y
def distancia_origem(self) -> float: # self é uma referência para uma instância
'''
Calcula a distância do ponto a origem.
Exemplos
>>> p = Ponto(3, 4)
>>> p.distancia_origem()
5.0
'''
return (x ** 2 + y ** 2) ** 0.5
>>> p = Ponto(10, 20)
>>> p.x
10
>>> p.y
20
>>> p.x = p.x + 1
>>> # Por padrão, a representação do objeto é opaca
>>> p
<__main__.Ponto object at 0x7fad1fac8530>
>>> # Por padrão, a comparação é por referência e não pelo conteúdo
>>> p == Ponto(11, 20)
False
>>> p == p
TrueQuando devemos usar @dataclass e
classes “normais”? Usamos @dataclass
quando queremos apenas agrupar dados e o encapsulamento não é
importante. Classes “normais” devem ser usadas nas demais situações,
como por exemplo, para criar tipos abstratos de dados (veja a seção
).
A principal função de entrada em Python é a função input, que
recebe um argumento (mensagem a ser exibida) e retorna uma linha lida
(string) da entrada padrão. O Python não tem funções para fazer entrada
de dados formatada.
O Python tem diversas funções de saída (incluindo saída formatada), a
mais comum é a função print. A função
print
recebe um número variado de argumentos (de qualquer tipo), converte cada
argumento para uma string com a função str e exibe os
valores separando-os por espaço e adicionando final de linha (esse
comportamento pode ser alterado).
O exemplo a seguir mostra como ler um nome e a data de nascimento de uma pessoa:
nome = input('Qual é o seu nome?')
data = input('Qual é a sua data de nascimento?')
# Fazemos um processamento para obter o ano.
# Omitimos o tratamento de erro.
ano = int(data.split('/')[2])
print(nome + ',', 'em 2050 você terá', 2050 - ano, 'anos.')Execução
Qual é o seu nome? João
Qual é a sua data de nascimento? 01/02/2003
João, em 2050 você terá 47 anos.Nesta seção mostramos alguns exemplos de algoritmos e estruturas de dados implementados em Python.
O exemplo a seguir mostra a implementação do algoritmo de ordenação por intercalação (merge sort). Note que o código poderia ser simplificado utilizando sublistas (slices), mas a intenção do exemplo é mostrar a implementação usando apenas as construções que são comuns na maioria das linguagens.
def ordena_intercalacao(valores: list[int], inicio: int, fim: int):
'''
Ordena o subarranjo *valores[inicio:fim]* em ordem não decrescente.
A ordenação é feita usando o algoritmo de intercalação.
Requer que 0 <= inicio <= fim <= len(valores).
Exemplos
>>> valores = [3, 1, 6, 1, 2, 5, 3]
>>> ordena_intercalacao(valores, 0, len(valores))
>>> valores
[1, 1, 2, 3, 3, 5, 6]
'''
assert 0 <= inicio <= fim <= len(valores)
if fim > inicio + 1:
m = (inicio + fim) // 2
ordena_intercalacao(valores, inicio, m)
ordena_intercalacao(valores, m, fim)
intercala(valores, inicio, m, fim)
def intercala(valores: list[int], inicio: int, m: int, fim: int):
'''
Intercala os elementos dos subarranjos *valores[inicio:m]* e *valores[m:fim]*.
Requer que 0 <= inicio < m < fim <= len(valores) e que os subarranjos
valores[inicio:m] e valores[m:fim] estajam ordenados.
Exemplo
>>> valores = [1, 5, 2, 4, 1, 3, 5, 4, 6]
>>> intercala(valores, 2, 4, 7)
>>> valores
[1, 5, 1, 2, 3, 4, 5, 4, 6]
'''
assert 0 <= inicio < m < fim <= len(valores)
# Copia os elementos a direita de m para dir
dir = []
for i in range(inicio, m):
dir.append(valores[i])
# Copia os elementos a partir de m e a esquerda para esq
esq = []
for i in range(m, fim):
esq.append(valores[i])
i = 0
j = 0
k = inicio
# Faz a intercação enquanto houver elementos em dir e esq
while i < len(dir) and j < len(esq):
if dir[i] < esq[j]:
valores[k] = dir[i]
i += 1
else:
valores[k] = esq[j]
j += 1
k += 1
# Copia o resto de dir se houver
while i < len(dir):
valores[k] = dir[i]
i += 1
k += 1
# Copia o resto de esq se houver
while j < len(esq):
valores[k] = esq[j]
j += 1
k += 1O exemplo a seguir mostra a implementação de um TAD dicionário usando
busca linear e funções. Apenas as operações de inserção e busca são
mostradas. Note que usamos @dataclass para
a implementação ficar mais semelhante a que seria feita em C. Na próxima
seção mostramos um exemplo que utiliza classe “normal” para enfatizar o
encapsulamento.
from dataclasses import dataclass
@dataclass
class Item:
'''Um par (chave, valor) em Dicionario.'''
chave: str
valor: int
@dataclass
class Dicionario:
'''
Um dicionario que associa strings com inteiros.
Este dicionário mantém uma lista de pares (chave, valor) em uma lista. As
adições são feitas no final da lista e as pesquisas são feitas de forma
linear na lista.
Este dicionário não suporta a remoção de items.
'''
items: list[Item]
def cria_dicionario() -> Dicionario:
'''
Cria um novo dicionário
'''
return Dicionario([])
def adiciona(dic: Dicionario, chave: str, valor: int) -> bool:
'''
Associa *chave* com *valor* em *dic* se ainda não existe valor associado
com *chave*. Produz True se a associação foi criada, False caso contrário.
Exemplos
>>> dic = cria_dicionario()
>>> adiciona(dic, 'Pedro', 24)
True
>>> adiciona(dic, 'Ana', 21)
True
>>> adiciona(dic, 'Pedro', 40)
False
'''
if busca_chave(dic, chave) is None:
dic.items.append(Item(chave, valor))
return True
else:
return False
def busca_chave(dic: Dicionario, chave: str) -> None | int:
'''
Devolve o valor associado com *chave* em *dic*, ou None se *chave* não
estiver em *dic*.
Exemplos
>>> dic = cria_dicionario()
>>> adiciona(dic, 'verde', 10)
True
>>> adiciona(dic, 'amarelo', 20)
True
>>> busca_chave(dic, 'verde')
10
>>> busca_chave(dic, 'azul') is None
True
'''
for item in dic.items:
if item.chave == chave:
return item.valor
return NoneNos exemplos a seguir mostramos a implementação de um TAD de lista ordenada usando encadeamento. No primeiro exemplo os nós são alocados dinamicamente. No segundo exemplo os nós são alocados quando a lista é criada (simulando alocação estática) e o encadeamento é feitos com índices (cursores). Note que são duas implementações diferentes para o mesmo TAD. Apenas a função de inserção é mostrada.
Implementação com encadeamento ilimitado
# Esse import é necessário devido a autorreferência na definição de No
from __future__ import annotations
from dataclasses import dataclass
@dataclass
class No:
'''Um nó em uma lista encadeada.'''
# O item armazenado no nó
item: int
# O próximo nó
prox: None | No
class Lista:
'''
Uma lista ordenada de números.
Essa implementação usa encadeamento de nós.
'''
primeiro: No | None
def __init__(self):
'''
Cria uma nova lista.
Exemplo
>>> lst = Lista()
>>> lst.para_list()
[]
'''
self.primeiro = None
def insere_ordenado(self, item: int) -> bool:
'''
Insere *item* na lista de maneira que ela permaneça ordenada.
Sempre produz True indicando que o item foi inserido.
Exemplos
>>> lst = Lista()
>>> lst.insere_ordenado(2)
True
>>> lst.insere_ordenado(6)
True
>>> lst.insere_ordenado(4)
True
>>> lst.insere_ordenado(1)
True
>>> lst.para_list()
[1, 2, 4, 6]
'''
# Procura a posição de inserção
pred = None
atual = self.primeiro
while atual is not None and atual.item < item:
pred = atual
atual = atual.prox
# Efetura a inserção
if pred is None:
# Não tem predecessor, então insere como primeiro
self.primeiro = No(item, self.primeiro)
else:
# Insere item entre pred e atual
# antes : pred -> atual
# depois: pred -> novo -> atual
pred.prox = No(item, pred.prox)
return True
def para_list(self) -> list[int]:
'''
Converte a lista para uma list do Python.
Este método é útil para testar o funcionamento da lista.
'''
resultado = []
atual = self.primeiro
while atual is not None:
resultado.append(atual.item)
atual = atual.prox
return resultadoImplementação com encadeamento de tamanho máximo fixo
from dataclasses import dataclass
@dataclass
class No:
'''Um nó em uma lista encadeada.'''
# O item armazenado no nó
item: int
# O índice do próximo nó no encademento
prox: None | int
class Lista:
'''
Uma lista ordenada de números.
A implementação é feita com um encadeamento de tamanho máximo fixo.
Os nós são alocados quando a lista é criada e a quantidade de nós não é
alterada. O campo prox de cada nó é utilizado para indicar o próximo nó da
lista (se o nó está na lista), ou o próximo nó livre (se o nó não está na
lista). Se o nó está disponível, o campo item não armazena nenhum valor
válido.
'''
# Os nós pré-alocados
nos: list[No]
# O índice em nos do primeiro nó da lista ou None se a lista está vazia
primeiro: None | int
# O índice em nos do primeiro nó disponível ou None se não existe nenhum
disponivel: None | int
# O número de itens na lista
num_itens: int
def __init__(self, n: int):
'''
Cria uma nova lista com tamanho máximo *n*.
Requer que n > 0.
Exemplo
>>> lst = Lista(3)
>>> lst.para_list()
[]
'''
assert n > 0
self.nos = []
self.primeiro = None
self.disponivel = 0
self.num_itens = 0
# Faz o encadeamento dos disponíveis, começando com 0
for i in range(n):
self.nos.append(No(0, i + 1))
# O último nó não tem um próximo
self.nos[n - 1].prox = None
def insere_ordenado(self, item: int) -> bool:
'''
Insere *item* na lista de maneira que ela permaneça ordenada.
Produz True se existia espaço na lista e *item* foi inserido, False caso contrário.
Exemplos
>>> lst = Lista(4)
>>> lst.insere_ordenado(2)
True
>>> lst.insere_ordenado(6)
True
>>> lst.insere_ordenado(4)
True
>>> lst.insere_ordenado(1)
True
>>> # Não tem mais espaço
>>> lst.insere_ordenado(7)
False
>>> lst.para_list()
[1, 2, 4, 6]
'''
if self.disponivel is None:
return False
# Usa o primeiro nó disponível
novo = self.disponivel
self.disponivel = self.nos[novo].prox
self.nos[novo].item = item
# Procura a posição de inserção
pred = None
atual = self.primeiro
while atual is not None and self.nos[atual].item < item:
pred = atual
atual = self.nos[atual].prox
# Efetura a inserção
if pred is None:
# Não tem predecessor, então insere como primeiro da self
self.nos[novo].prox = self.primeiro
self.primeiro = novo
else:
# Insere novo entre pred e atual
# antes : pred -> atual
# depois: pred -> novo -> atual
self.nos[pred].prox = novo
self.nos[novo].prox = atual
self.num_itens += 1
return True
def para_list(self) -> list[int]:
'''
Converte a lista para uma list do Python.
Este método é útil para testar o funcionamento da lista.
'''
resultado = []
atual = self.primeiro
while atual is not None:
resultado.append(self.nos[atual].item)
atual = self.nos[atual].prox
return resultadoEssas são algumas convenções oficiais para escrita de código em Python.
Indente o código usando 4 espaços, não utilize tabulações;
Nomeie tipos da forma CapitalizedWords;
Nomeie funções e variáveis da forma
lower_case_with_underscores;
Nomeie constantes da forma
UPPER_CASE_WITH_UNDERSCORES;
Use um import por
linha;
Evite espaçamentos extras (spam(ham[1], {eggs: 2})
ao invés de spam( ham[ 1 ], { eggs: 2 } ));
Use espaços entre operadores (c += (a + b) * (a - b)
ao invés de c+=(a+b)*(a-b))
A seguir estão algumas referências bibliográficas que podem ser úteis tanto para os professores quanto para os alunos.
Introdução a programação
Think Python 2e (tradução em português)
Notas de aula de introdução a programação e de estruturas de dados em Python (do mesmo autor desse texto)
Estruturas de dados
Linguagem Python