Programação I Aula 10 Processamento de listaspbv/aulas/programacaoI/teorica-10.pdf · Crivo de Eratóstenes Construir a tabela dos números primos até n: 1 escrevemos todos os

Programação IAula 10 — Processamento de listas

Pedro Vasconcelos

DCC/FCUP

2018

Pedro Vasconcelos (DCC/FCUP) Programação I Aula 10 — Processamento de listas 2018 1 / 32

Nesta aula

Vamos ver alguns exemplos de processamento de listas:

1 Agregações

2 Eliminar repetidos

3 Crivo de Eratóstenes


Somar valores duma sequência

A função pré-definida sum soma os valores duma sequência.

Exemplo:

>>> sum([0.5, 1, 0.5])2.0

Vamos definir a nossa própria implementação desta função.


Somar valores duma sequência

def soma(xs):"Somar valores duma lista xs."# variável ‘total’ vai acumular a somatotal = 0# percorre todos os valoresfor x in xs:

# acrescenta ao totaltotal = total + x

# o resultado da função é ‘total’return total


Exemplos

>>> soma([1, 2, 3])6

>>> soma([1.0, 0.5, 2.0])3.5

>>> soma([1.0])1.0

>>> soma([])0


Alternativa

def soma(xs):"Somar valores duma lista xs."# variável ‘total’ vai acumular a somatotal = 0# percorre todos os índicesfor i in range(len(xs)):

# acrescenta ao totaltotal = total + xs[i]

# fim do ciclo; retorna o resultadoreturn total

Um ciclo sobre os índices em vez dos valoresA primeira solução é mais direta


Outras agregações

A média aritméticaO produtoO máximo ou mínimo


Média aritmética duma sequência

def media(xs):"Calcula a média aritmética duma lista."# média é a soma / número de elementosreturn soma(xs)/len(xs)


Exemplos

>>> media([2.0, 1.0, 1.0])1.33333333333

>>> media([2.0])2.0

A média não está definida para a lista vazia:

>>> media([])ZeroDivisionError: integer division ormodulo by zero


Produto duma lista

Análogo à soma, substituindo:o operador + por *;o valor inicial 0 por 1 (elemento neutro de *).


Produto duma lista

def produto(xs):"Produto duma lista xs."# variável ’total’ vai acumular o productototal = 1# percorrer todos os valoresfor x in xs:

# acrescenta ao totaltotal = total * x

# fim do ciclo; retorna o resultadoreturn total


Exemplos

>>> produto([2, 3, 4])24

>>> produto(range(1,5))24

>>> produto([])1


Máximo / mínimo duma lista

Podemo usar as funções pré-definidas max e min para determinar ovalor máximo/mínimo de uma lista.

>>> max([5, 1, 3])5

>>> min([5, 1, 3])1

>>> max([2, 3, 1, 0])3

>>> min([2, 3, 1, 0])0

Vamos ver como implementar a nossa própria versão destas funções.


Algoritmo para o máximo

Usamos uma variável para guarda o maior valor já encontradoInicialmente é o maior valor é o primeiro valor na sequênciaPara cada um dos restantes valores: for superior ao maior valor jáencontrado atualizamos este último


Valor máximo duma lista

def maximo(xs):"Maior valor duma sequência xs."# inicialmente: maior é o primeiro valormaior = xs[0]# ciclo sobre os restantes índicesfor i in range(1,len(xs)):

if xs[i] > maior: # será maior?maior = xs[i] # se sim, atualizar

# fim do ciclo; retornar o maior valor encontradoreturn maior


Exemplos

>>> maximo([1, 3, 2, -1]3

>>> maximo([2, 1])2

Nota que calcular o máximo de uma lista vazia é um erro:

>>> max([])ValueError: max() arg is an empty sequence

>>> maximo([])IndexError: list index out of range


Valor mínimo

Análogo ao anterior, trocando apenas a comparação.

def minimo(xs):"Menor valor duma sequência xs."# inicialmente: menor é o primeiro valormenor = xs[0]# percorrer os restantes índicesfor i in range(1,len(xs)):

# atualizar o menorif xs[i] < menor: # será menor?

menor = xs[i] # se sim, atualizar# fim do ciclo; retornar o resultadoreturn menor


Eliminar elementos repetidos

Vamos definir um procedimento para eliminar elementos repetidosduma lista.

Exemplo: se a lista original for

[2, 1, 3, 4, 1, 4, 1]

então o resultado deve ser

[2, 1, 3, 4]

Cada valor ocorre apenas uma vez e pela mesma ordem da listaoriginal.


Eliminar elementos repetidos

Duas soluções:1 construir uma lista nova sem repetidos;2 modificar a lista original apagando elementos repetidos.


Eliminar repetidos: algoritmo 1

Construir uma nova lista ysInicialmente ys = [ ]

Para cada elemento x na lista dada:se x /∈ ys, então acrescentamos x à lista ys


Eliminar repetidos: implementação 1

def elimrep(xs):"Constroi uma nova lista sem repetidos."# ys é a lista sem repetidos# inicialmente vaziays = []for x in xs:

# se x não é repetidoif not (x in ys):

# acrescenta à nova listays.append(x)

# retorna a lista novareturn ys


Exemplos

>>> elimrep([2,1,3,3,1,4,1])[2, 1, 3, 4]

>>> elimrep([2,2,2])[2]

>>> elimrep([1,2,3])[1, 2, 3]


Eliminar repetidos: algoritmo 2

Uma lista xs com n elementosUm ciclo sobre os índices 0 ≤ i ≤ n − 1Invariante: não há repetidos nos índices inferiores a i

sem repetidos︷︸︸︷xs[0], . . . , xs[i − 1],

pode haver repetidos︷︸︸︷xs[i], . . . , xs[n − 1]

Actualização: se xs[i] ∈ {xs[0], xs[1], . . . , xs[i − 1]} entãoapagamos xs[i]; caso contrário, avançamos i uma posição


Eliminar repetidos: implementação 2

def elimrep(xs):"Eliminar repetidos em xs."i = 0while i<len(xs):

if xs[i] in xs[0:i]:# xs[i] é repetido; apagamosdel xs[i]

else:# xs[i] não é repetido; avançamosi = i+1


Exemplos

>>> lista = [2,1,3,3,1,4,1]>>> elimrep(lista)>>> lista[2, 1, 3, 4]

>>> lista = [2,2,2]>>> elimrep(lista)>>> lista[2]

>>> lista = [1,2,3]>>> elimrep(lista)>>> lista[1, 2, 3]


Sumário

Ambas as soluções são válidasA primeira solução:

constroi uma nova lista;é mais simples de compreender.

A segunda solução:modifica a lista original;poderá ser mais eficiente (necessita de menos memória).


Crivo de Eratóstenes

Construir a tabela dos números primos até n:1 escrevemos todos os inteiros de 2 até n2 o primeiro número (2) é primo e riscamos todos os seus múltiplos3 o segundo número (3) é primo e riscamos todos os seus múltiplos4 repetimos o processo: o próximo número não riscado é primo e

riscamos todos os seus múltiplos5 no fim: a tabela contém todos os números primos menores do

que n



Começamos com todos os inteiros de 2 até 30

2 3 4 5 6 7 8 9 10 1112 13 14 15 16 17 18 19 20 2122 23 24 25 26 27 28 29 30



O número 2 é primo e riscamos os seus múltiplos

2 3 //4 5 //6 7 //8 9 ///10 11///12 13 ///14 15 ///16 17 ///18 19 ///20 21///22 23 ///24 25 ///26 27 ///28 29 ///30




2 3 //4 5 //6 7 //8 //9 ///10 11///12 13 ///14 ///15 ///16 17 ///18 19 ///20 ///21///22 23 ///24 25 ///26 ///27 ///28 29 ///30



O número 4 não é primo (já foi riscado)

2 3 //4 5 //6 7 //8 //9 ///10 11///12 13 ///14 ///15 ///16 17 ///18 19 ///20 ///21///22 23 ///24 25 ///26 ///27 ///28 29 ///30




2 3 //4 5 //6 7 //8 //9 ///10 11///12 13 ///14 ///15 ///16 17 ///18 19 ///20 ///21///22 23 ///24 ///25 ///26 ///27 ///28 29 ///30



Repetimos o processo até esgotar a tabela; restam apenas os primosinferiores a 30.

2 3 //4 5 //6 7 //8 //9 ///10 11///12 13 ///14 ///15 ///16 17 ///18 19 ///20 ///21///22 23 ///24 ///25 ///26 ///27 ///28 29 ///30


Implementação do crivo

Representamos a tabela de números por uma listaRemovemos da lista os números compostosNo final restam apenas os primos


Implementação do crivo

def crivo(xs):"Remove números compostos da lista xs."i = 0while i<len(xs):

p = xs[i] # p é primoj = i+1 # vamos remover múltiploswhile j<len(xs):

if xs[j]%p == 0:del xs[j]

else:j = j+1

i = i+1 # próximo primo# fim do crivo


Construir uma lista de primos

def primos(n):"Constroi a lista de primos menores que n."xs = list(range(2,n)) # inteiros entre 2 e n-1crivo(xs) # remove os compostosreturn xs # lista de primos

Note que o crivo modifica a lista dada em vez de criar uma nova.


Exemplos

Calcular todos os primos até 100:

>>> primos(100)[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Quantos primos inferiores a 1000?

>>> len(primos(1000))168


Documents

Programação I Aula 10 Processamento de listaspbv/aulas/programacaoI/teorica-10.pdf · Crivo de Eratóstenes Construir a tabela dos números primos até n: 1 escrevemos todos os