Programação II

Exercícios

Universidade de LisboaFaculdade de Ciências

Departamento de InformáticaLicenciatura em Tecnologias da Informação

2015/2016

1 Exceções e Tratamento de Ficheiros

1. Escreva uma função media que dada uma lista de strings, cada umarepresentando um número, devolva a sua média, um número emvírgula flutuante. A função levanta a exceção ValueError quando pelomenos um elemento da lista não for convertível para float. Levanta aexceção ZeroDivisionError quando a lista de strings estiver vazia.

2. Dados referentes a observações são frequentemente guardados emficheiros de texto. Por exemplo, as temperaturas lidas a várias horas dodia, ao longo de vários dias, podem ser guardadas num ficheiro denúmeros em vírgula flutuante, onde cada linha contém os valores dasvárias temperaturas medidas num dia.

5.6 7.8 11.7 12.6 9.3 7.36.7 8.5 11.6 11.6 9.4 7.05.4 7.2 10.5 11.1 10.0 8.3

Utilizando a função media do exercício anterior, escreva uma funçãoimprime_medias que, dado o nome de um ficheiro de texto como oacima, imprima as temperaturas médias diárias. Deverá imprimir umvalor por linha e tantos valores quantas as linhas do ficheiro. Sugestão:utilize o método string.split(s) para obter a lista de palavrasexistentes numa string.

A função imprime_medias deve apanhar as exceções lançadas pelafunção media. No caso de divisão por zero deverá imprimir “linhavazia”; no caso de uma linha que contenha uma palavra que nãorepresenta um número em vírgula flutuante deverá imprimir “linha malformada”. Exceções relativas à abertura do ficheiro deverão ser tratadaspelo chamador (ver exercício seguinte).

(a) Escreva a função imprime_medias que imprima algo (a média ouuma mensagem de erro) para cada linha no ficheiro. Utilize ocomando try: finally: para se assegurar que fecha o ficheiro.

(b) Adapte a solução da alínea anterior utilizando desta vez ocomando with.

(c) Finalmente, escreva uma versão da função imprime_medias quepára ao primeiro erro (escrevendo no entanto a mensagem de errocorrespondente).

3. Escreva uma função principal sem parâmetros que pede ao utilizadoro nome dum ficheiro de temperaturas, e chama a funçãoimprime_medias passando o nome do ficheiro. Caso ocorra algumproblema de acesso ao ficheiro, a função principal deve escrever Errode I/O ao ler o ficheiro <nome do ficheiro>.

4. Por vezes os ficheiros de observações trazem informação sobre os dadosna forma de linhas comentadas, cada qual iniciada pelo carater cardinal#. Eis um exemplo:

# Localização: Observatório de Muge# 14/2/20165.6 7.8 11.7 12.6 9.3 7.3# 15/2/20166.7 8.5 11.6 11.6 9.4 7.0# 16/2/20165.4 7.2 10.5 11.1 10.0 8.3

Escreva uma função salta_comentario que, dado um ficheiro abertopara leitura, devolva a primeira linha que não está comentada.

5. Usando a função salta_comentario, altere a função imprime_medias

do exercício 2, de modo a ignorar linhas comentadas no ficheiro.Apelide-a de medias_salta_comentario.

6. Escreva uma função lista_para_ficheiro que, dada uma lista e onome de um ficheiro, escreve os vários elementos da lista, um por linha,no ficheiro.

7. Usando a função lista_para_ficheiro, altere a função do exercício 2,de modo a escrever as médias num dado ficheiro. Apelide-a demedias_para_ficheiro. Deve receber duas strings com os nomes dosdois ficheiros envolvidos.

8. Informação referente a símbolos químicos pode ser guardada emficheiros de texto. Neste caso estamos interessados apenas no nome,número atómico e densidade (em g/dm3). Eis um exemplo:

2

Hélio 2 0.1786Néon 10 0.9002Árgon 18 1.7818Crípton 36 3.708Xénon 54 5.851Rádon 86 9.97

Escreva uma função linha_para_elemento que dada uma linha de umficheiro de elementos (uma string), produz um dicionário com chaves'nome', 'atomico' e 'densidade'. O nome é do tipo string, o númeroatómico do tipo int e a densidade do tipo float.

9. Utilizando a função linha_para_elemento, escreva uma outra funçãoque dada uma string representando o nome de um ficheiro, produz umalista de dicionários com chaves 'nome', 'atomico' e 'densidade'.Chame-lhe ler_elementos.

10. Escreva a função inversa de linha_para_elemento, isto é, uma funçãoque dado um dicionário representando um elemento, devolve umastring com o nome, número atómico e densidade, separados porespaços. Apelide a função de elemento_para_string.

11. Utilizando a função elemento_para_string, escreva uma funçãoescrever_elementos que, dada uma lista de dicionários representandoelementos químicos e o nome de um ficheiro, escreva o conteúdo da listano ficheiro, um elemento por linha.

12. O arranjo de átomos em moléculas pode ser descrito em formato textual,e portanto guardado em ficheiros. Cada molécula é descrita por umnúmero variável de linhas: a primeira contém o nome da molécula, assubsequentes contêm informação sobre o átomo. A última linha, END,fecha a molécula. Cada átomo é composto pelo seu identificador,símbolo químico, e as coordenadas tri-dimensionais. Eis o exemplo deum ficheiro contendo duas moléculas.1

COMPND AMMONIAATOM 1 N 0.257 -0.363 0.000ATOM 2 H 0.257 0.727 0.000ATOM 3 H 0.771 -0.727 0.890ATOM 4 H 0.771 -0.727 -0.890ENDCOMPND METHANOLATOM 1 C -0.748 -0.015 0.024ATOM 2 O 0.558 0.420 -0.278ATOM 3 H -1.293 -0.202 -0.901

1Exercício retirado de “Practical Programming: An Introduction to Computer Science UsingPython 3”, Paul Gries, Jennifer Campbell, e Jason Montojo, Pragmatic Programmers, 2013.

3

ATOM 4 H -1.263 0.754 0.600ATOM 5 H -0.699 -0.934 0.609ATOM 6 H 0.716 1.404 0.137END

Escreva uma função linha_para_atomo que, dada uma string contendouma linha ATOM, devolve um dicionário com chaves 'símbolo', 'id','x', 'y', e 'z'.

13. Escreva uma função ler_atomos que, dado um leitor (isto é um ficheiroaberto para leitura), devolve uma lista de átomos. Assuma que o leitorestá posicionado numa linha que começa com ATOM. A função deverádeixar o leitor posicionado na primeira linha após o END que marca ofim da molécula correspondente aos átomos lidos. Não se pretende ler oficheiro até ao fim, mas apenas até ao fim da molécula.

14. Utilizando a função ler_atomos, escreva uma função ler_molecula

que, dado um leitor, devolve ou uma molécula ou None. Assuma que oleitor está no fim do ficheiro (caso em devolve None) ou está posicionadonuma linha que começa com COMPND (caso em devolve a molécula).Cada molécula é representada por um dicionário com duaschaves—'molécula', e 'átomos'—representando o nome da moléculae a lista de átomos que a compõem, respetivamente.

15. Utilizando a função ler_molecula, escreva uma função ler_moleculas

que, dado um leitor, devolve uma lista de moléculas.

16. Finalmente, utilizando a função ler_moleculas escreva uma funçãoler_ficheiro que dado uma string representando o nome de umficheiro, devolve uma lista de moléculas. Não se esqueça de fechar oficheiro e apanhar as exceções.

4

2 Testes Baseados na Partição do Espaço de Entrada

Nota prévia. Os alunos devem complementar também, em regime detrabalho autónomo, os exercícios da folha 9 da disciplina Programação I,2015–2016.Para testar os nossos programas vamos utilizar o módulo doctest. Consulte adocumentaçãoù.

1. Considere as duas funções abaixo.2

def encontra_ultimo (lista, x):"""O índice do último elemento numa lista que é iguala um dado elemento.Requires: o primeiro argumento é uma listaEnsures: devolve o índice do último elemento da listaque é igual a x.Se x não ocorrer na lista, devolve None."""for i in range(len(lista)-1, 0, -1):

if lista[i] == x:return i

return None

def conta_positivos (v):"""O número de elementos positivos em vRequires: v é uma lista de númerosEnsures: Devolve o número de valores positivos em v"""conta = 0for x in v:

if x >= 0:conta = conta + 1

return conta

Para cada um dos programas:

(a) Encontre a falha (o defeito).

(b) Se possível encontre um teste que não execute a falha.

(c) Repare a falha.

2. Para a função encontra_ultimo, e utilizando a técnica da partição deespaço de entrada, escreva uma bateria de testes. Considere as seguintescaracterísticas.

• A lista está vazia;

• Número de ocorrências do elemento na lista;

• O elemento ocorre pela última vez na lista na última posição.

• O elemento ocorre pela última vez na lista na primeira posição.

2Exercício adaptado de “Introduction to Software Testing”, Paul Ammann and Jeff Offutt, Cam-bridge University Press, 2008.

5

O que é que os testes, quando executados, permitem concluir sobre acorreção da função?

3. Escreva uma bateria de testes para a função conta_positivos

utilizando a técnica da partição de espaço de entrada. Considere ascaracterísticas que achar apropriadas.

4. Considere a seguinte especificação da função unicos.

A função recebe uma lista e devolve uma outra contendoexactamente uma ocorrência de cada elemento da listaoriginal. A lista original está ordenada; a lista resultadodeverá estar também ordenada. A lista original não deve seralterada.

Escreva uma bateria de testes para esta função.

5. Escreva testes baseados na partição do espaço de entrada para aseguinte função:

def diferenca(l1, l2):"""Requires: l1 é uma listaRequires: l2 é uma listaEnsures: devolve uma lista que contem os elementos del1 que não estão em l2. As listas l1 e l2 não sãoalteradas."""

6. Considere a seguinte função:

def interseccao (conjunto1, conjunto2):"""Devolve um conjunto igual à interseção dos doisconjuntos.

Requires: conjunto1 é um listaRequires: conjunto2 é um listaEnsures: é devolvido, em forma de lista, o conjuntointersecção dos conjuntos dados."""

Escreva uma bateria de testes de acordo com as seguintes características:

• Tipo de conjunto1: lista vazia, lista com pelo menos um elemento;

• Relação entre conjunto1 e conjunto2: as listas representam omesmo conjunto, conjunto1 é subconjunto de conjunto2,conjunto2 é subconjunto de conjunto1, os conjuntos não têmelementos em comum.

6

3 Testes Baseados na Cobertura do Grafo de Fluxode Controle

Notas prévias. Os alunos devem complementar também, em regime detrabalho autónomo, os exercícios da folha 9 da disciplina Programação I,2015–2016.Para testar os nossos programas vamos utilizar o módulo doctest. Consulte adocumentaçãoù.

1. Para a função encontra_ultimo (listada no exercício 1 da semana 2) ebaseado no fluxo de controle escreva um teste para cada um dos casosseguintes.

(a) Não entra no ciclo;

(b) Entra no ciclo exactamente uma vez e passa no ramo then (isto é oteste v[i] == x é verdadeiro)

(c) Entra no ciclo exactamente uma vez e passa no ramo else (isto é oteste v[i] == x é falso)

(d) Entra no ciclo mais do que uma vez, passando sempre pelo else;

(e) Entra no ciclo mais do que uma vez, passando umas vezes por thene outras por else;

(f) Consegue escrever um teste que passe mais do que uma vez porthen? Ou estaremos em face de um teste inviável?

2. Considere a função conta_positivos (listada no exercício 1 dasemana 2).

(a) Desenhe o diagrama de fluxo de controlo da função.

(b) Escreva testes de acordo com as regras do método de análise dofluxo de controlo.

3. Para a função abaixo, escreva testes baseados na cobertura de grafos.Comece por desenhar o diagrama de fluxo de controlo da função.

def diferenca(l1, l2):resultado = l1i=0while i < len(l1):

if l1[i] in l2:resultado.remove(l1[i])

i += 1return resultado

Ao executar os testes, o que pode concluir sobre a correção da função?Consegue escrever algum teste que falhe?

7

4. Dada a seguinte implementação da função unicos, desenhe o grafo defluxo e seguidamente uma bateria de testes baseados na cobertura dografo de fluxo de controlo.

def unicos(lista):resultado = []i = 0while i < len(lista):

elemento = lista[i]i = i + 1resultado.append(elemento)while i < len(lista) and elemento == lista[i]:

i = i + 1return resultado

5. Para a seguinte função, escreva testes baseados no fluxo de controle dafuncão. Comece por desenhar o diagrama de fluxo da execução dafunção.

def principal (nome_ficheiro):try:

medias (nome_ficheiro)except IOError:

print "Erro de I/O ao ler o ficheiro",nome_ficheiro

6. Escreva testes baseados no fluxo de controlo para a seguinte função.

def busca(lista, elemento):"""Requires: lista é uma listaEnsures: Devolve True se o elemento está na lista, eFalse caso contrário"""encontrado = Falsei=0while i < len(lista) and not encontrado:

encontrado = lista[i] == elementoi += 1

return encontrado

7. Escreva testes baseados no fluxo de controlo para a seguinte função.

def produto_matrizes (a, b, c):"""Requires: linhas de a == linhas b; colunas de a =colunas de c; colunas de b = linhas cEnsures: Coloca em a o produto de duas matrizes b ec"""for i in range (len(b)):

for j in range (len(c[0])):

8

a[i][j] = 0for k in range (len(c)):

a[i][j] += b[i][k] * c[k][j]

9

4 Complexidade Algorítmica

1. Apresente uma caracterização O do tempo de execução de cada funçãoabaixo. Indique em cada caso o significado de n.

def par (x):return x % 2 == 0

def absoluto (x):return x if x > 0 else 0

def max3 (x, y, z):return max(x, max(y, z))

def max (x, y):return x if x > y else y

2. Apresente uma caracterização O do tempo de execução de cada funçãoabaixo. Indique em cada caso o significado de n.

def a (n):m = 0for i in range (1, 10* n):

for j in range (1, n):m += 1

return m

def b (n):x = 0for a in range (0, 2004):

x += a * nreturn x

def c (n):b = n * nwhile b > n:

if b % 2 == 0:b -= 1

else:b -= 2

return b

def d (n, v):soma = 0for i in range(0, n):

for j in range (1, 4):soma += v[i]

return soma

10

def e (n):x = n * n * nwhile x > 1:

x /= 2

def f (n):soma = n * nwhile soma % 2 == 0:

soma -= 1return soma

def g (a, b, c):for i in range (len(b)):

for j in range (len(c[0])):a[i][j] = 0for k in range (len(c)):

a[i][j] += b[i][k] * c[k][j]

def h (n):c = 0for i in range (0, n):

for j in range (i, n):c += 1

return c

3. Analise a complexidade computacional da função diferenca,exercício 3 da semana 3.

4. Analise o O-grande da função unicos, exercício 4 da semana 3.

5. Analise o tempo de execução da função busca, exercício 6 da semana 3.

6. Considere o seguinte algoritmo para o cálculo das médias dos prefixosde um vector.

def media_prefixos (l):""""Requires: uma lista de númerosEnsures: devolve uma lista m onde m[i] é a média doselementos l[0] ,... ,l[i-1]"""m = []for i in range(len(l)):

soma = 0.0for j in range(i + 1):

soma += l[j]m.append(soma/(i + 1))

return m

(a) Verifique que o algoritmo dado tem um tempo de execuçãoquadrático.

11

(b) Apresente uma solução com tempo linear. Sugestão: calculeincrementalmente a média de cada um dos prefixos através daseguinte fórmula.{

m[0] = l[0]

m[k + 1] = (m[k] · (k + 1) + l[k + 1])/(k + 2)

7. As funções sem_repetidos e sem_repetidos2 verificam se uma listanão tem repetidos.

def sem_repetidos1 (l):for i in range (len(l)):

if l[i] in l[(i+1):]:return False

return True

def sem_repetidos2 (l):copia = list(l)copia.sort()for i in range (len(l) - 1):

if copia[i] == copia[i+1]:return False

return True

(a) Analise a complexidade assintótica de cada uma das soluções.

(b) Proponha uma solução linear. Sugestão: converta a lista numconjunto.

12

5 Algoritmos de Pesquisa e de Ordenação

1. Escreva uma versão iterativa da seguinte função. Analise acomplexidade computacional da solução obtida.

def busca_binaria (l, e):"""Requires: l é uma lista e está ordenada por ordemcrescenteEnsures: Devolve True se e ocorre em l, e False casocontrário"""

def busca_bin (baixo, alto):"""Requires: l é uma lista e está ordenada por ordemcrescenteEnsures: Devolve True se e ocorre em l entre osíndices baixo e alto, e False caso contrário"""

if alto < baixo:return False

meio = (baixo + alto) // 2if l[meio] > e:

return busca_bin (baixo, meio - 1)elif l[meio] < e:

return busca_bin (meio + 1, alto)else:

return Truereturn busca_bin (0 , len(l) - 1)

2. Analise a complexidade computacional das seguintes funções:

• No pior caso;

• No melhor caso.

Identifique cada um dos casos.

(a) Ordenação por flutuação (variante do bubble sort).3

def ordenacao_por_flutuacao (lista):"""Ordena a lista por ordem ascendente.Requires: lista é uma lista de elementoscomparáveis entre siEnsures: a lista fica ordenada por ordemascendente"""for comeco in range (len(lista) -1 , 0 ,-1):

for i in range (comeco):if lista[i] > lista[i+1]:

lista[i+1], lista[i] = lista[i],lista[i+1]

3Barack Obama—Computer Science Questionù

13

(b) Ordenacao por seleção (selection sort).

def ordenacao_por_selecao (lista):"""Ordena a lista por ordem ascendente.Requires: lista é uma lista de elementoscomparáveis entre siEnsures: a lista fica ordenada por ordemascendente."""for comeco in range (len(lista)):

for i in range (comeco+1, len(lista)):if lista[i] < lista[comeco]:

lista[comeco], lista[i] = lista[i],lista[comeco]

(c) Ordenação por inserção (insertion sort).

def ordenacao_por_insercao (lista):"""Ordena a lista por ordem ascendente.Requires: lista é uma lista de elementoscomparáveis entre siEnsures: a lista fica ordenada por ordemascendente"""for i in range (1, len(lista)):

valor_corrente = lista[i]posicao = iwhile posicao > 0 and lista[posicao - 1] >

valor_corrente:lista[posicao] = lista[posicao - 1]posicao = posicao - 1

lista[posicao] = valor_corrente

3. Considere a ordenação por flutuação (exercício 2 acima).

(a) Qual o tempo de execução quando a lista estiver ordenada?

(b) Adapte o algoritmo de modo a torná-lo linear neste caso.

4. Quicksort, desenvolvido por Sir Tony Hoareù, 1960, apoia-se numaestratégia de dividir para conquistar em que uma sequência inicial S édividida em várias sub-sequências às quais o algoritmo é aplicadorecursivamente. O resultado é posteriormente concatenado obtendo-seuma sequência ordenada. Tipicamente o QuickSort pode ser dividido emtrês passos:

Dividir Se S tem pelo menos dois elementos (se tem zero ou um asequência está ordenada), selecionar um elemento de S que passa aser o pivot. Retirar todos os elementos de S construindo asseguintes duas sequências:

B (baixo) contendo todos os elementos inferiores ou iguais ao pivot;A (alto) contendo todos os elementos superiores ao pivot;

14

Conquistar Aplicar recursivamente o algoritmo às sequências B e A.

Combinar Concatenar B, pivot, A, por esta ordem para obter oresultado.

(a) Discuta a complexidade computational do algoritmo no melhor eno pior caso.

(b) Qual o tempo de execução quando todos os elementos da lista sãoiguais?

(c) Qual o tempo de execução quando a lista estiver ordenada?

(d) Implemente o algoritmo na linguagem Python.

5. O algoritmo de ordenação BucketSort apoia-se no pressuposto que oselementos a ordenar estão associados a chaves, as quais podem serusadas como índices de uma sequência de baldes (buckets). Eis oalgoritmo:

• Seja S uma sequência de elementos com chaves no intervalo[0, N − 1].

• Seja B uma sequência (lista) de N baldes inicialmente vazios.

• Para cada elemento e de S:

– seja k a chave de e;– retirar e de S;– adicionar e ao balde B[k].

• Para cada k entre 0 e N − 1:

– Para cada elemento e de B[k]:

* remover e de B[k];

* adicionar e no final de S.

• Devolver S.

(a) Implemente o algoritmo na linguagem Python. Considere que S éuma lista de pares (chave, elemento). Por exemplo, paraS = [(5, 'a'), (2, 'b'), (5, 'c'), (1, 'd')]

o algoritmo deverá modificar S paraS = [(1, 'd'), (2, 'b'), (5, 'c'), (5, 'a')]

(b) Discuta a complexidade computational do algoritmo. Se chegar auma solução sub O(n · log n) explique porque é que esta nãocontradiz o resultado que estabelece O(n · log n) como limiteinferior para qualquer algoritmo de ordenação baseado emcomparação.

15

6 Funções de Ordem Superior

1. Qual o valor de cada expressão?

(a) map (lambda x: x + 1, range(1, 4))

(b) map (lambda x: x > 0, [3, -5, -2, 0])

(c) filter (lambda x: x > 5, range(1, 7))

(d) filter (lambda x: x % 2 == 0, range(1, 11))

(e) filter (lambda x: x > 0, map (lambda y: y ** 2,

range(-3, 4)))

(f) map (lambda x: x ** 2, filter (lambda x: x > 0,

range(-3, 4)))

(g) map (lambda x: x + 's', ['As', 'armas', 'e', 'os',

'barões'])

(h) map (lambda x: 's' + x, ['As', 'armas', 'e', 'os',

'barões'])

(i) map (lambda x: map (lambda y: y * y, x), [[1, 2], [3,

4, 5]])

2. Defina uma função produto_interno que calcule o produto escalarΣn

1xi · yi de dois vetores ~x e ~y. Os vetores são dados por listas denúmeros. Sugestão: utilize a função zip.

3. Determine o valor de cada uma das expressões seguintes.

(a) reduce (lambda y, z: y * 3 + z, range(1, 5))

(b) reduce (lambda x, y: x + y if x > 0 else y, [4, -3, 2,

-1])

(c) reduce (lambda x, y: x ** 2 + y, range(2, 6))

(d) reduce (operator.mul, range(-3, 0, -1), 1)

(e) reduce (operator.sub, [1, 2, 3])

(f) reduce (operator.sub, [1, 2, 3], 10)

Não se esqueça de fazer import operator para os últimos trêsexercícios.

4. Recorrendo à função reduce escreva a função que calcule o factorial deum número não negativo.

5. Escreva um conversor binário para decimal utilizando a função reduce.O número binário é apresentado por uma lista de inteiros. Por exemplo:

>>> binario_para_decimal([1, 1, 0, 1])13>>> binario_para_decimal([])0

16

6. Defina uma função mapa_seletivo que devolve uma lista contendo osresultados de aplicar a função dada no primeiro argumento aoselementos da lista dada no terceiro argumento, que satisfaçam acondição dada no segundo argumento. Exemplo:

>>> mapa_seletivo (lambda x: x * 3, lambda y: y > 0,range(-4, 5))

[3, 6, 9, 12]

7. Utilizando a função map, escreva uma função gz que transforme umalista de listas de inteiros numa lista de listas de valores lógicos, ondecada entrada indica se o valor respetivo é ou não maior do que zero. Porexemplo:

>>> gz([[1, 2, 3], [2, -1, 3, 7]])[[True, True, True], [True, False, True, True]]

8. Escreva a função filter recorrendo às funções map e reduce. Sugestão:para o predicado lambda x: x > 0 e a lista [2, 0, -3, 4] comece porcalcular a lista [[2], [], [], [4]]. Concatene depois as listas todaspara obter [2, 4].

9. Escreva a função filter recorrendo apenas à função reduce.

10. Escreva a função map recorrendo apenas à função reduce.

11. Dado um par de listas, a função zip devolve uma lista de pares. Oi-ésimo par é composto pelo i-ésimo elemento da primeira lista e peloi-ésimo da segunda lista. A lista resultante contém tantos elementosquantos os da mais curta das duas listas parâmetro. Neste exercícioestamos interessados numa função zip_with, variante da função zip,que recebe uma função que combina os dois elementos.

def zip_with (f, lista1, lista2):""">>> zip_with(lambda x, y: x, [], [1, 2])[]>>> zip_with(lambda x,y : x, ['a'], [])[]>>> zip_with(lambda x, y: (x, y), ['a', 'b'], [2, 3,4])[('a', 2), ('b', 3)]>>> zip_with(max, [5, 2, 0, 9], [2, 3, 4])[5, 3, 4]"""

(a) Proponha uma definição função zip_with que itere sobre as listasdadas.

17

(b) Escreva uma função recorrendo à função zip e map.

(c) Proponha uma solução recorrendo apenas à função map. A funçãomap pode ser utilizada com mais do que uma lista. Neste caso afunção é chamada com um argumento retirado de cada lista,utilizando None quando nem todas as listas tiverem o mesmocomprimento.

12. Escreva a função zip recorrendo à função zip_with do exercício acima.

18

7 Gráficos de funções, de barras e histogramas compylab

1. Vamos chamar gráfico a um par de listas de números com o mesmocomprimento. A primeira lista deve estar ordenada por ordem crescentee denota as abcissas, a segunda as ordenadas. Eis o gráfico da funçãoquadrática tomada nos números inteiros entre 0 e 5:

([0, 1, 2, 3, 4, 5], [0, 1, 4, 9, 16, 25])

Procuramos uma função grafico que, dada uma função de números emnúmeros, devolve o seu gráfico. A função grafico recebe quatroparâmetros, três dos quais opcionais. São eles: a função, a primeiraabcissa baixo = 0.0, a última abcissa alto = 10.0, e o incrementoentre abcissas incremento = 1.0. Exemplo:

>>> grafico (lambda x: 2*x, alto = 5.0, incremento = 1.7)([0, 1.7, 3.4], [0, 3.4, 6.8])

2. Escreva uma função tracar_grafico que trace o gráfico de umafunção. A função deve receber um gráfico (um par de listas, verexercício acima) e três parâmetros opcionais, a saber: etiquetax = 'x',etiquetay = 'f(x)', titulo = 'grafico da funcao f'. Consulte omanual do Pylabù, secção Beginner’s Guide para descobrir as funçõesapropriadas.

Eis o aspeto da função n · log(n), gerado pelo código abaixo.

>>> import math>>> g = grafico(lambda n: n*math.log(n), baixo = 1, alto =

10000)>>> tracar_grafico(g, etiquetax = 'n', etiquetay =

'n*log(n)', titulo = u'Gráfico da função log-linear')

19

3. Escreva uma função tracar_graficos que trace conjuntamente osgráficos de um número variável de funções. A função recebe como únicoparâmetro a lista dos vários gráficos (cada gráfico é um par de listas, verexercício 1). Utilize uma função de ordem superior para iterar sobre osgráficos na lista. Por exemplo:

>>> baixo = 0.1>>> alto = 100>>> linear = grafico (lambda n: n, baixo = baixo, alto =

alto)>>> loglinear = grafico (lambda n: n*math.log(n), baixo =

baixo, alto = alto)>>> quadratico = grafico (lambda n: n**2, baixo = baixo,

alto = alto)>>> tracar_graficos ([linear, loglinear, quadratico])

deverá produzir um gráfico deste tipo:

4. Escreva uma função potencias que devolva gráficos (pares de listas)para as várias potências de um número. Dado um número k, a funçãodeverá devolver uma lista com k + 1 gráficos correspondentes àsfunções x0, x1, x2, . . . , xk. Para além deste parâmetro (que é obrigatório),a função deverá receber três parâmetros opcionais, tal como noexercício 1. Utilize funções de ordem superior sempre que possível.

5. Escreva uma função graficos que devolva gráficos (pares de listas)para várias funções. A função recebe uma lista de funções e devolveuma lista de gráficos, um gráfico por função. Para além deste parâmetro(que é obrigatório), a função deverá receber três parâmetros opcionais,tal como no exercício 1. Utilize funções de ordem superior sempre quepossível.

20

6. Podemos traçar um gráfico num par de eixos (caso do exercício 2),vários gráficos no mesmo par de eixos (caso do exercício 3) ou gráficosem diferentes pares de eixos (caso de este exercício). Todos os comandospyplot dizem respeito ao par de eixos (abcissas, ordenadas) corrente. Osvários eixos estão organizados em linhas e colunas. Para escolher umnovo par de eixos usamos a função

pylab.subplot(numero_de_linhas, numero_de_colunas,numero_dos_eixos)

onde o número dos eixos deverá estar entre 1 e o produto das linhaspelas colunas.

Escreva uma função tracar_subgrafico que dado um gráfico (isto é,um par de listas ordenadas-abcissas), o número de linhas e de colunas, eo número do gráfico, construa um novo gráfico (pylab.plot) num dadopar de eixos.

Depois construa uma função tracar_subgraficos que dado uma listade gráficos e o número de linhas construa uma figura com tantosgráficos quantos os presentes na lista. Por exemplo, o código Pytonabaixo deve imprimir o gráfico na figura também abaixo.

>>> baixo = 0.1>>> alto = 20.0>>> constante = grafico (lambda x: 10.0, baixo = baixo,

alto = alto)>>> logaritmico = grafico(lambda x: math.log(x), baixo =

baixo, alto = alto)>>> linear = grafico(lambda x: x, baixo = baixo, alto =

alto)>>> loglinear = grafico (lambda x: x*math.log(x), baixo =

baixo, alto = alto)>>> quadratico = grafico (lambda x: x*x, baixo = baixo,

alto = alto)>>> exponencial = grafico (lambda x: 2**x, baixo = baixo,

alto = alto)>>> seis_graficos = [constante, logaritmico, linear,

loglinear, quadratico, exponencial]>>> tracar_subgraficos(seis_graficos, 2)

21

7. De modo a distinguir melhor os diferentes gráficos a traçar num par deeixos podemos personalizar a sua visualização. Assim, é possíveladicionar a cada plot uma string de formatação. Por exemplo, podemosfazer:

pylab.plot(abcissas, ordenadas, 'go--')

para que a linha seja desenhada em cor verde ('g' de green), commarcas circulares ('o') e tracejada ('--'). Todas a opções deformatação das linhas podem ser consultadas na documentação dafunção plotù.

Escreva uma função tracar_graficos_personalizados que recebedois argumentos: uma lista de gráficos e uma lista de strings deformatação com as formatações pretendidas para cada um dos gráficosfornecidos. As duas listas deverão ter o mesmo comprimento. A funçãodeverá traçar os gráficos dados de acordo com as respectivas strings deformatação.

Por exemplo:

>>> baixo = 0.1>>> alto = 10>>> linear = grafico (lambda n: n, baixo = baixo, alto =

alto)>>> loglinear = grafico (lambda n: n*math.log(n), baixo =

baixo, alto = alto)>>> quadratico = grafico (lambda n: n**2, baixo = baixo,

alto = alto)>>> formatacoes = ['r^-','go--','bs:']>>> tracar_graficos_personalizados ([linear, loglinear,

quadratico], formatacoes)

deverá produzir um gráfico deste tipo:

22

8. Escreva uma função maximos que, dada uma lista de gráficos, devolveuma lista com os máximos de cada um dos gráficos. A lista a devolverdeverá ser uma lista de pares (abcissa, ordenada) correspondentes aospontos máximos de cada gráfico.

9. Escreva uma função medias que, dada uma lista de gráficos, constróium novo gráfico no qual, para cada abcissa, a ordenada é a média dasordenadas dos vários gráficos fornecidos. Assuma que todos os gráficostêm a mesma lista de abcissas.

10. Utilizando a função medias, definida no exercício 9, defina uma funçãotracar_com_medias que recebe uma lista de gráficos e traça, nummesmo sistema de eixos, todos esse gráficos e ainda o gráfico dasmédias, sendo que este deverá ser apresentado com marcas circulares.

11. Escreva uma função booleana eh_maxima que, dados dois gráficos,verifica se o primeiro é maior ou igual que o segundo em todos ospontos fornecidos, devolvendo, nesse caso, o valor True. Deverádevolver False caso exista pelo menos uma abcissa para a qual asordenadas não verifiquem a condição indicada.

12. Defina uma função grafico_barras que, dada uma lista de pares,apresente um gráfico de barras no qual as alturas das barrascorrespondem aos valores dos segundos elementos de cada par e osnomes das barras aos primeiros elementos. Defina a função de modo aque, para a lista seguinte:

precipitacao = [('jan', 118), ('fev', 98), ('mar', 61),('abr', 80), ('mai', 70), ('jun', 18), ('jul', 17),('ago', 17), ('set', 42), ('out', 97), ('nov', 110),('dez', 143)]

seja apresentado o gráfico

23

13. Defina uma função histogramas_classes que permita mostrar arepresentação em histograma de um conjunto de valores, considerandoum número variável de classes. A função recebe dois argumentos: a listade valores e uma lista de inteiros, na qual cada inteiro representa umnúmero de classes a considerar. A função apresenta assim tantoshistogramas quantos os elementos desta segunda lista. Defina a funçãode modo a que:

(a) Cada histograma seja apresentado numa figura independente.

(b) Os histogramas apareçam todos numa mesma figura, havendo, nomáximo, 2 por coluna. Por exemplo, o código seguinte deverámostrar a figura apresentada.

>>> coleta = [1, 1, 1, 3, 2, 5, 1, 5, 6, 6, 7, 8, 8]>>> histogramas_classes(coleta,[2,3,5])

24

8 Ficheiros de Valores Separados por Vírgulas(CSV)

1. Escreva uma função ler_csv que lê um ficheiro CSV, linha a linha, parauma lista de listas de strings. Assuma que o ficheiro tem um númeroindeterminado de linhas.

2. Escreva uma função converter que, dada uma lista de listas e umafunção de conversão, devolve uma nova lista de listas onde todos oselementos da lista original foram convertidos pela função parâmetro.Por exemplo:

>>> converter([['0', '1', '2', '3', '4', '5'], ['0', '2','4', '6', '8', '10']], int)

[[0, 1, 2, 3, 4, 5], [0, 2, 4, 6, 8, 10]]

3. Escreva uma função ler_csv_float que leia dum ficheiro CSV o gráficode uma função (no formato de um par de listas de números em vírgulaflutuante; ver exercício 1 da semana 7). A função recebe o nome de umficheiro. Sugestão: Utilize as duas funções acima.

4. No seguimento do exercício anterior, constatamos que é bem maiscomum encontrarmos as funções dispostas em colunas do que emlinhas. Pretende-se neste exercício construir uma funçãocsv_para_grafico que devolva o gráfico de uma função, assumindoque o ficheiro CSV contém as abcissas na primeira coluna e asordenadas na segunda.

(a) Escreva depois uma função transposta que transpõe uma lista delistas, isto é, que troca as linhas pelas colunas.

(b) Finalmente, para compor a função csv_para_grafico, utilize asfunções ler_csv, transposta, converter, e tuple, por estaordem. Poderia alterar a ordem das funções transposta econverter? E das funções converter e tuple?

5. Este exercício assume que o ficheiro CSV está organizado da seguinteforma. Coluna 1: abscissas para todas as funções, coluna 2: ordenadasprimeira função, coluna 3: ordenadas segunda função, e por aí emdiante. Escreva uma função csv_para_graficos que devolva uma listacom os gráficos das várias funções constantes no ficheiro. Sugestão:utilize as funções do exercício anterior.

6. Escreva uma função grafico_para_csv_linha que receba o nome deum ficheiro e um gráfico (um par de listas), e escreva o gráfico noficheiro do seguinte modo: a primeira linha contém as abcissas, asegunda as ordenadas.

25

7. Escreva uma função grafico_para_csv que escreva o gráfico, desta vezorganizado por colunas.

8. Escreva uma função graficos_para_csv que, dado o nome de umficheiro e uma lista de gráficos (uma lista de listas de números), escrevaos gráficos num ficheiro CSV. Organize a informação no ficheiro doseguinte modo: a primeira coluna contém as abcissas, a segunda colunacontém as ordenadas da primeira função, a terceira coluna contém asordenadas da segunda função, e por aí em diante. Assuma que todas asfunções têm listas de abcissas iguais.

9. Neste exercício escrevemos listas de dicionários em ficheiros CSV.

(a) Escreva uma função ler_csv_para_lista_dicionarios que,dado o nome de um ficheiro CSV e uma lista de strings, devolva alista de dicionários (tabela) com a informação constante no ficheiro.A lista de strings é um argumento opcional contendo os nomes dascolunas (cabeçalho), que deverá ser usado apenas quando oficheiro CSV não inclui cabeçalho.

(b) Suponha que temos ficheiros contendo a seguinte informação sobrejogadores de voleibol, referentes a uma dada época desportiva: naprimeira coluna o nome do jogador, na segunda o clube a quepertence, na terceira o número de pontos que marcou, na quarta onúmero de ases (número de serviços que resultaram diretamenteem ponto), na quinta a eficiência de ataque (rácio entre o númerode passes que recebe e o número de pontos que marca), na sexta onúmero de blocos efetuados, e na sétima o número de cartõesamarelos. Escreva uma função ler_volei que, dado o nome de umficheiro CSV, sem cabeçalho, incluindo a informação referida acima,devolve a lista de dicionários com os dados constantes no ficheiro.

10. Suponha agora que é necessário guardar uma lista de dicionários numficheiro CSV.

(a) Escreva uma função escrever_lista_dicionarios_para_csv

que, dado o nome do ficheiro CSV a criar, dada uma tabela (lista dedicionários), e dada a ordem pretendida para as colunas (lista daschaves pela ordem pretendida), crie um ficheiro CSV com ocabeçalho indicado e com o conteúdo definido na tabela.

(b) Utilizando a função da alínea anterior, escreva uma funçãoescrever_volei que, dada uma tabela de jogadores de voleibolcom a estrutura indicada no exercício 9b, e dado o nome doficheiro, crie um ficheiro CSV com a informação correspondente.

26

9 Manipulação de tabelas em memória

Para efeitos desta lista de exercícios, uma tabela é uma lista de dicionários.Cada dicionário na lista tem exactamente as mesmas chaves.

1. Considere uma tabela descrevendo o desempenho de jogadores de vóleinuma dada época, tal como descrita no exercício 9b da página 26. Atabela tem os campos descritos abaixo, onde os campos 'clube' e'nome' são do tipo string, o campo 'eficiencia' é float e todos osoutros são int. Assuma também que não há jogadores repetidos natabela. Por outras palavras: o nome do jogador é chave na tabela. Eis umexemplo:

nome clube pontos ases eficiência blocos amarelosVasco SL Benfica 20 5 0,50 122 0Mario SC Espinho 33 4 0,30 99 2Joao FC Porto 50 6 0,22 102 3Antonio Castelo da Maia 47 2 0,47 93 0Andre SL Benfica 23 1 0,17 117 2Luis SC Espinho 47 0 0,64 86 2Pedro SC Espinho 35 3 0,72 123 4Nuno Castelo da Maia 51 7 0,44 108 0

Recorrendo à função ler_csv_para_dict() (exercício 9, página 26)escreva uma função ler_volei(nome_ficheiro) que lê dados de umficheiro CSV e efectua as necessárias conversões para float a para intdos campos numéricos (todos menos 'nome' e 'clube').

2. Este exercício determina valores máximos em tabelas.

(a) Escreva uma função maximo_tabela(tabela, campo) que calculeo dicionário contendo o maior valor de um dado campo (isto é, deuma dada chave do dicionário). Por exemplo:

>>> tabela = ler_volei('volei.csv')>>> maximo_tabela(tabela, 'amarelos')

{'clube': 'SC Espinho', 'nome': 'Pedro', 'ases':3, 'pontos': 35, 'amarelos': 4, 'blocos': 123,'eficiencia': 0.72}

(b) Use a função acima para calcular o nome do jogador que maispontos marcou. Exemplo:

>>> tabela = ler_volei('volei.csv')>>> jogador_mais_pontos(tabela)'Nuno'

(c) Calcule agora o nome do clube a que pertence o jogador que maisamarelos sofreu.

27

3. Estamos agora interessados em calcular o clube que mais pontosmarcou. Para isso:

(a) Comece por escrever uma função reduzir_soma(tabela, campo)

que produza uma tabela com chaves 'clube' e campocorrespondentes à soma das propriedades na tabela original.Exemplo:

>>> tabela = ler_volei('volei.csv')>>> reduzir_soma(tabela, 'pontos')[{'clube': 'Castelo da Maia', 'pontos': 98}, {'clube':

'FC Porto', 'pontos': 50}, {'clube': 'SC Espinho','pontos': 115}, {'clube': 'SL Benfica', 'pontos':43}]

(b) Utilize depois a função maximo_tabela() do exercício 1, para obtero clube com mais pontos.

>>> tabela = ler_volei('volei.csv')>>> clube_com_mais_pontos(tabela)'SC Espinho'

(c) Aproveite para calcular o clube que obteve o maior número de ases.

4. Calcule uma lista ordenada dos clubes por ordem crescente de cartõesamarelos recebidos. Sugestão: utilize a função reduzir_soma() doexercício 3. Exemplo:

>>> tabela = ler_volei('volei.csv')>>> clubes_cartoes(tabela) #doctest: +NORMALIZE_WHITESPACE[{'clube': 'Castelo da Maia', 'amarelos': 0},{'clube': 'SL Benfica', 'amarelos': 2},{'clube': 'FC Porto', 'amarelos': 3},{'clube': 'SC Espinho', 'amarelos': 8}]

5. Neste exercício estamos interessados numa tabela com a percentagem depontos que foram obtidos por ases por clube.

(a) Escreva uma função fusao(tabela1, tabela2, campo) que juntaduas tabelas por um dado campo. Este campo deve ser chave emambas as tabelas, isto é não deve haver dois dicionários com omesmo campo. Exemplo:

>>> pontos = [{'clube': 'Castelo da Maia', 'pontos':98}, {'clube': 'FC Porto', 'pontos': 50},{'clube': 'SC Espinho', 'pontos': 115}, {'clube':'SL Benfica', 'pontos': 43}]

28

>>> ases = [{'ases': 9, 'clube': 'Castelo da Maia'},{'ases': 6, 'clube': 'FC Porto'}, {'ases': 7,'clube': 'SC Espinho'}, {'ases': 6, 'clube': 'SLBenfica'}]

>>> fusao(pontos, ases, 'clube')[{'ases': 9, 'clube': 'Castelo da Maia', 'pontos':

98}, {'ases': 6, 'clube': 'FC Porto', 'pontos':50}, {'ases': 7, 'clube': 'SC Espinho', 'pontos':115}, {'ases': 6, 'clube': 'SL Benfica','pontos': 43}]

(b) Calcule agora a tabela de percentagem de ases por pontos: umatabela com chaves 'clube' e 'ases por ponto'. Sugestão:comece por utilizar a função reduzir_soma() da alínea 3 paraobter tabelas com os números de ases e de pontos. Efectue depoisuma fusão das duas tabelas. Finalmente calcule uma nova tabelaonde as colunas 'pontos' e 'ases' são convertidas numa únicacoluna 'ases por ponto'.

(c) Aproveite para calcular o clube que obteve a maior percentagem depontos marcados por ases. Sugestão, utilize a funçãomaximo_tabela() do exercício 1.

6. Neste exercício estamos interessados em relacionar nomes de clubescom listas de jogadores.

(a) Generalize a função reduzir_soma() do exercício 3 de modo areceber mais dois parâmetros: a função de acumulação e o valorbase (tipicamente o valor neutro da operação de acumulação).Estes dois parâmetros são exatamente os mesmos que seriampassados para a função reduce da biblioteca Python. Chamereduzir à nova função. Exemplo:

>>> import operator>>> tabela = ler_volei('volei.csv')>>> reduzir(tabela, 'pontos', operator.add, 0)[{'clube': 'Castelo da Maia', 'pontos': 98}, {'clube':

'FC Porto', 'pontos': 50}, {'clube': 'SC Espinho','pontos': 115}, {'clube': 'SL Benfica', 'pontos':43}]

(b) Calcule agora uma tabela onde cada dicionário contém um campocom o nome do clube e outro contém uma lista com os nomes dosjogadores. Exemplo:

>>> tabela = ler_volei('volei.csv')>>> clube_jogadores(tabela) #doctest:

+NORMALIZE_WHITESPACE[{'clube': 'Castelo da Maia', 'nome': ['Antonio',

'Nuno']},

29

{'clube': 'FC Porto', 'nome': ['Joao']},{'clube': 'SC Espinho', 'nome': ['Mario', 'Luis',

'Pedro']},{'clube': 'SL Benfica', 'nome': ['Vasco', 'Andre']}]

7. Calcule uma tabela com campos 'clube' e 'melhor marcador'.

8. Calcule uma lista ordenada por ordem decrescente dos jogadores commaior eficiência de ataque. Em caso de empate ganha o jogador commaior número de blocos efetuados. Em caso de empate utiliza-se aordem alfabética do nome do jogador.

30

10 Probabilidades, Estatística e Simulação I

1. Escreva uma função lancar_dado que devolva um número aleatórioentre 1 e 6. Escreva a função de quatro modos distintos, utilizando asfunções choice, randint, randrange e random do módulo random.

2. Escreva uma função lancar_n_dados(n) que devolva um número como resultado de n lançamentos de um dado equilibrado de seis faces.Escreva um contrato apropriado para a função.

3. Nem todos os dados são equilibrados. Escreva uma funçãolancar_dado_viciado() que simule um dado viciado, comprobabilidade P (1) = 0, 20, P (2) = 0, 10, P (3) = 0, 30, P (4) = 0, 05,P (5) = 0, 27, P (6) = 0, 08. Resolva este exercício sem usar instruções ife elif encadeadas. Sugestão: comece por escrever uma função maisgeral, escolher_com_probabilidade, que recebe uma lista deprobabilidades.

4. O paradoxo do aniversário diz que a probabilidade de pelo menos duaspessoas numa sala terem a mesma data de aniversário é superior a 1/2mesmo para um número de pessoas relativamente pequeno. Estapropriedade não é realmente um paradoxo, mas muitas pessoasacham-na surpreendente. Dado o número de pessoas na sala escrevauma função simular_aniversarios(n_pessoas, n_experiencias)

que teste o “paradoxo” através de uma série de experiências com diasde aniversário gerados aleatoriamente. Determine experimentalmentequal o mais pequeno número de pessoas para qual o “paradoxo”acontece. Mais concretamente, escreva uma funçãomenor_numero_pessoas_paradoxo() que devolve o menor número depessoas que precisam de estar numa sala para se verificar o “paradoxo”.

5. A técnica de Monte Carlo pode ser utilizada para estimar o valor de π.Imagine que dispõe de um alvo circular inscrito num quadrado.Suponha que todos os lançamentos de dardos acertam no quadrado,possivelmente no alvo. Se n for o número total de dardos lançados, e hfor o número que acerta no alvo, é fácil mostrar que π = 4h

n . Escrevauma função sim_pi que calcule o valor de π, dado o número delançamentos de dardos.

Sugestão: utilize a fórmula 2*random.random()-1 para gerar ascoordenadas x e y de um ponto dentro de quadrado 2× 2 centrado em(0, 0). O ponto está no alvo se x2 + y2 ≤ 1.

6. Suponha uma corrida de quatro cavalos conhecidos: Artimanhas,Bombom, Caramelo e Dilúvio. Estima-se que a probabilidade de venceré 5% para Artimanhas, 20% para Bombom, 25% para Caramelo e 50%Dilúvio. Determine a percentagem de vitórias obtidas por cada cavalonas realização de n corridas. Sugestão: utilize a funçãoescolher_com_probabilidade do exercício 3. Exemplo:

31

>>> simular_corrida_cavalos(10000,['Artimanhas', 'Bombom', 'Caramelo', 'Diluvio'],[0.05, 0.20, 0.25, 0.50])

{'Artimanhas': 0.0474, 'Caramelo': 0.2516,'Bombom': 0.2001, 'Diluvio': 0.5009}

32

11 Probabilidades, Estatística e Simulação II

1. Considere o lançamento de três dados. Faça uma estimativa daprobabilidade da sua soma ser 3, 4, . . . , 18 através de simulaçãocomputacional. Escreva uma funçãosimular_lancar_dados(num_dados, num_experiencias) quepermita simular o lançamento de um número arbitrário de dados.Aplique-a depois ao caso dos três dados. Apresente o resultado naforma de um histograma.

2. Suponha uma roleta de um casino com 37 ranhuras e com a numeração

0, 1, 2, . . . , 36. A ranhura 0 é verde, dezoitodas restantes são pretas e as outras dezoito são vermelhas. O banqueirofaz a roleta girar e lança uma bola.

(a) Se um jogador apostar na cor preta e a bola parar na cor preta,ganha uma importância igual à que apostou (além de recuperar aimportância que apostou). Caso contrário, perde o dinheiro daaposta. Estime a probabilidade de um jogador ganhar, simulandoeste jogo e supondo que ele aposta um grande número de vezesseguidas a importância de e1.

>>> random.seed(101)>>> simulacao_pretas(10000)0.4764

(b) Se um jogador apostar num número específico e a bola parar nessaranhura, ganha 35 vezes o valor da aposta (sempre de e1) além derecuperar a importância que apostou. Caso contrário, perde odinheiro da aposta.Considere a seguinte estratégia: o jogador aposta sempre nomesmo número (por exemplo, 6), fixa o limite da perda diária (porexemplo, e50), e faz por noite um número máximo de apostas (porexemplo, 100). Faça uma simulação do que ganharia um jogadornuma noite. Por exemplo, para um máximo de 100 apostas, umorçamento inicial de e50 e número da sorte 6:

>>> random.seed(971)>>> simulacao_noite(100, 50, 6)

33

8>>> simulacao_noite(100, 50, 6)-50

(c) A experiência acima tem pouca relevância estatística. Estime olucro obtido, repetindo a experiência um grande número de vezes.Eis um exemplo, onde o primeiro parâmetro é o número deexperiências noites, e os três últimos como na alínea anterior:

>>> random.seed(211)>>> simulacao_n_noites(10000, 100, 50, 6)-1.3382

(d) Suponha agora que um jogador de roleta usa a estratégia daduplicação de parada que consiste no seguinte: aposta sempre na corpreta. Se ganhar a aposta, volta a apostar e1 (no preto claro). Seperder, duplica a aposta anterior. Continua a jogar até que tenhaganho ou perdido e10. Simule este jogo um número suficiente devezes para poder concluir que deve evitar este tipo de estratégia.Eis um exemplo, onde o primeiro parâmetro é o número deexperiências e o segundo o máximo que o jogador está disposto aperder ou ganhar.

>>> random.seed(571)>>> simulacao_duplicacao_n_paradas(10000, 10)-0.9497

3. Nas próximas eleições autárquicas há dois candidatos à presidência dacâmara: o Abel e a Beatriz. Sabe-se que x% dos votantes querem votarna Beatriz e (100− x)% no Abel. Um jornal local encomendou umasondagem a uma empresa de marketing, baseada na opinião de nvotantes. O objectivo é prever o vencedor e publicar o resultado dasondagem antes do fim da campanha eleitoral. Pretende-se simular estasondagem e analisar as possibilidades do jornal se enganar nosseguintes casos:

(a) x = 45% e n = 10, 100, 1000

(b) x = 47% e n = 10, 100, 1000

(c) x = 49% e n = 10, 100, 1000

4. Efectue a simulação de um jogo de voleibol entre duas equipas.

Um jogo de voleibol joga-se à melhor de 5 sets. Cada um dos sets iniciaisjoga-se até aos 25 pontos. O quinto set, chamado a negra, se acontecer,joga-se até aos 15 pontos. Em qualquer caso, um set tem de ser ganhopor uma diferença igual ou superior a 2 pontos.

34

O lançamento de uma moeda decide a equipa que sai (serve o primeiroponto) no primeiro set.4 Nos sets seguintes, as equipas saem por ordemalternada. Para a negra uma nova moeda é lançada. A equipa ganha umponto mesmo que não tenha sido ela a servir. A equipa que ganha oponto serve o ponto seguinte.A eficiência do serviço é a percentagem de pontos que uma equipaconsegue quando serve. Uma eficiência de 20% indica que a equipaganha 1 em 5 pontos que serve. Obviamente as equipas com melhoreficiência de serviço terão maior probabilidade de ganhar. Mas quantomais? Este exercício de simulação responde a esta questão. Resolva-o epasme-se!Os dados da simulação são: a probabilidade da equipa A ganhar oponto quando serve, a probabilidade da equipa B ganhar o pontoquando serve, e o número de jogos a simular.Para a simulação temos de simular_um_set_volei(),simular_um_jogo_volei() e simular_n_jogos_volei().

5. O jogo de dados (craps) é um jogo jogado em muitos casinos. Umjogador lança um par de dados, convencionais, de seis faces. Se olançamento inicial somar 2, 3, ou 12, o jogador perde. Se o dado mostrar7 ou 11 o jogar vence. Em qualquer outro caso, o número que saiutorna-se o ponto. A partir daqui só interessam dois números: o 7 e oponto. O jogador continua a lançar o dado até que saia um destesvalores. Se sair o ponto, o jogador ganha; se sair 7 o jogador perde.Escreva uma função simula_n_jogos_dados que simule múltiplos jogosde dados e que estime a probabilidade do jogador ganhar. Por exemplo:>>> simula_n_jogos_dados (100000)0.49108

indica que a probabilidade do jogador ganhar é 49,108%, ou que ojogador ganhou 49108 jogos em 100000.

6. Na realidade o jogo dos dados consta de duas apostas principais: aaposta na linha de passagem e a aposta na linha de não passagem. Oexercício acima desenvolve a aposta na linha de passagem. Na aposta nalinha de não passagem aplica-se o oposto, mas aparece a noção deempate: se o lançamento inicial somar 7 ou 11 o jogador perde, se sair 2ou 3 o jogador ganha, e se sair 12 dá-se um empate. O jogo prosseguecom o número ponto, tal como em linha de passagem.Prepare uma funçãosim_dados_nao_passagem(lancamentos_por_jogo,

numero_de_jogos) que calcule o retorno sobre investimento (ROI eminglês, “Return On Investment”), na forma de média e desvio padrão.

4Na realidade a face favorável da moeda permite que o capitão da equipa escolha ou o campoou a equipa que serve primeiro.

35

Que consegue concluir sobre a “melhor estratégia”?

7. Vinte e Um (Blackjack) é um jogo de casino jogado com cartas. O objetivodo jogo é retirar cartas de um baralho que somem um número tãopróximo quanto possível de 21, sem nunca ultrapassar este valor.

O valor da mão (conjunto de cartas) é determinado pela soma do valorde cada uma das cartas na mão. Cartas numeradas de 2 a 10 valem o seuvalor facial; figuras (valetes, damas ou reis) valem 10 pontos cada; asesvalem 1 ou 11 pontos, aquele que for mais favorável.

O jogo é jogado de encontro a um banqueiro. O banqueiro dá duascartas abertas (com a face virada para cima) para cada jogador. Obanqueiro tira duas cartas para si, mas apenas uma aberta. Com base nacarta do banqueiro virada para cima e na sua mão, o jogador decide sebate (pede carta adicional) ou passa (mantem sua mão como está).

Uma vez os jogadores satisfeitos com as suas mãos, o banqueiro mostraa face da sua segunda carta e procede de acordo com as regras dobanqueiro. As regras do banqueiro são as seguintes:

• O banqueiro deve tirar cartas adicionais até que a sua mão valha 17pontos ou mais;

• Se a mão do banqueiro somar 17 ou mais, então ele deve “passar”.

Ganham os jogadores que somarem mais pontos do que o banqueiro.

(a) Escreva uma função probabilidade_banqueiro_rebentar quesimule múltiplos jogos de Vinte e Um e que estime a probabilidadedo banqueiro rebentar. Verifique o resultado obtido de encontro aoproposto por BlackJack Ageù.

(b) Se estiver indeciso sobre se há-de pedir nova carta ou passar, sabera probabilidade do banqueiro rebentar dada a carta virada paraconstitui uma grande ajuda. Escreva uma funçãoprobabilidade_banqueiro_rebentar_dada_uma_carta queapresente uma tabela com três colunas: valor da carta virada paracima, probabilidade de rebentar, e desvio padrão. Analise os váriosvalores da carta virada para cima: 2 a 10, e ás. Novamente,verifique o resultado obtido de encontro ao proposto por BlackJackAgeù.

36

12 Expressões Regulares em Python

1. Em cada alínea, indique quais das strings (ou alguma das suassubstrings) são reconhecidas pela expressão regular indicada.

(a) Expressão regular: '^[a-z]*[0-9]+.$'

i. 33ii. 2

iii. carro2iv. carro234v. _25

(b) Expressão regular: r'^[1-4]\d{3}[^a-z]$'

i. 12345ii. 5392A

iii. 1274aiv. 2461_v. 4a221

(c) Expressão regular: r'([a-z0-9]{2}|[A-Z])\d-?'

i. 456ii. ab-

iii. F44iv. 23A5-v. aZ3x-

2. Para cada uma das expressões regulares, indique quantas (e quais)ocorrências serão reconhecidas nas strings indicadas:

(a) Expressão regular: r'[a-z0-9]\d'

i. 'a456'ii. '456'

iii. '456b'iv. 'ab456'v. 'a5b2d456'

(b) Expressão regular: '.[^0-9]*,?[^a-zA-Z]*'

i. '234abc'ii. 'abc234'

iii. '234,abc'iv. ',234abc'v. 'xabc,999x'

vi. 'xabc999y'vii. '0'

37

viii. '00,99'ix. '\n\n\n'

3. Para cada um dos casos abaixo escreva uma expressão regular Python.

(a) Os códigos postais de Portugal. Exemplos: 1749-016 Lisboa,2795-241 Linda a Velha

(b) As matrículas de veículos registados em Portugal. Exemplos:AA-11-11, ou 11-AA-11, ou ainda 11-11-AA.

(c) Um número vírgula flutuante. Exemplos: 2.3 e -1.345. Nãoexemplos: 4 e 0034.0 e -0.0.

(d) Um número escrito na notação científica. Exemplos: 2e4, 2.3e4 e-1.345e-34, para além de todos os da alínea anterior. Nãoexemplos: 4, -03.0e7.

(e) Os endereços de email dos alunos da FCUL. Exemplo:fc99999@alunos.fc.ul.pt.

(f) Identificadores numa linguagem de programação: uma sequênciade letras, algarismos e traços inferiores (_) que não começam porum algarismo.

(g) Versão simplificada de URL (Uniform Resource Locator), da forma

scheme:[//[user:password@]host[:port]]

onde: os parêntesis retos indicam partes opcionais; scheme é umasequência de carateres que começa com uma letra, seguida porqualquer combinação de letras, números, mais (+), ponto (.) ouhífen (-); user e passwd são sequências não vazias de carateres;host é um nome de um domínio ou um endereço IP (em notaçãodecimal-ponto); e port é o número de um porto. (wikipediaù).

(h) Um número romano. Exemplos: MM, CCI, CM, XLVII. Nãoexemplos: IM, DIC. Considere apenas números romanos entre 1 e3999.

4. Baseado nas soluções do exercício anterior, escreva funções Python que,dada uma string, devolvam a informação indicada. As funções devemdevolver None caso a string fornecida não corresponda a um valor bemformado de acordo com a expressão regular.

(a) Um triplo contendo as três partes de um código postal. Exemplo:('2795', '241', 'Linda a Velha').

(b) Os três constituintes de uma matrícula, juntamente com ainformação sobre o tipo de matrícula: letras-primeiro,letras-no-meio, letras-no-fim.

(c) Um número em vírgula flutuante.

(d) Um dicionário com os vários elementos constantes num URL.

38

(e) Um número inteiro, em numeração árabe, correspondente a umdado número romano.

5. Extração de padrões. Em cada alínea, escreva uma função que:

(a) Devolva uma lista com todas as ocorrências de uma expressãoregular numa string.

(b) Devolva uma lista com todas as ocorrências de uma expressãoregular numa lista de strings.

(c) Calcule o número de matrículas que ocorrem numa lista de strings.

(d) Obtenha a lista de matrículas que ocorrem numa lista de strings,mas apenas aquelas cujo grupo das letras começa por uma letradada.

6. Substituição de strings em ficheiros.

(a) Escreva uma função que aplique uma dada substituição noconteúdo de um ficheiro. O resultado deve ser escrito num outroficheiro.

(b) Utilize o resultado da alínea anterior para substituir vírgulas porponto e vírgulas num ficheiro CSV.

(c) Idem para reescrever os nomes das estações do ano em minúscula(de modo a ficar de acordo com a nova ortografia).

(d) Escreva uma função que elimine de um ficheiro a ocorrência demúltiplos espaços em branco entre duas palavras. Adicionalmente,inclua também a inclusão de dois espaços após cada ponto final.

7. Escreva uma função que, dada uma lista de strings, devolva umdicionário com quatro campos: número de matrículas letras-primeiro,número de letras-no-meio, número letras-no-fim, e número de stringsque não representam matrículas.

8. Escreva uma função que agrupe os algarismos de um número detelefone em três. Por exemplo, dado o número '217500000', a funçãodeve devolver '217 500 000'.

9. Escreva uma função, que dado uma lista de números de telefone (emformato string), os classifique de acordo com o Plano Nacional deNumeraçãoù. Para tal utilize um dicionário em que as chaves são osvários indicativos ('00', '1', '2', . . . , '9', 'invalido') e os valores sãolistas de números de telefone (em formato string).

39

13 Ferramentas de Sistema I

1. Escreva um script paramin que imprima no ecrã o conteúdo do ficheirocom todas as letras convertidas para minúsculas. Exemplo:

$ cat mensagem.txtA Europa jaz, posta nos cotovellos:De Oriente a Occidente jaz, fitando,$ python paramin.py mensagem.txta europa jaz, posta nos cotovellos:de oriente a occidente jaz, fitando,

Sugestão: proceda em dois passos:

(a) Escreva uma funcão paramin(nome_ficheiro) que imprime noecrã o conteúdo de um ficheiro com todas as letras convertidaspara minúsculas.

(b) Baseado na função anterior, escreva agora o script paramin.py quelê da linha de comandos o nome do ficheiro e imprime no ecrã oconteúdo deste com todas as letras convertidas para minúsculas.

2. Escreva um script para imprimir os ficheiros numa directoria esubdirectorias em forma de “árvore deitada”. Para cada ficheiro,imprimos o seu nome; o nome de cada directoria deve ser precedido dosinal +. Cada nova directoria começa uma nova coluna dois espaçospara a direita.

$ python deitada.py disciplinas/prog2+docs

exercicios.tex+trabalho

enunciado.texgrafico.png

+srcmore.pydeitados.py

3. Escreva um script que imprima o caminho absoluto de todos os ficheirosPython que se encontram numa dada directoria, incluindo as suassubdirectorias.

$ python todospy.py exemplosC:\temp\exemplos\simulacao\roleta.pyC:\temp\exemplos\scripts\more.pyC:\temp\exemplos\scripts\deitada.pyC:\temp\todospy.py

40

Escreva duas versões:

(a) Versão iterativa, utilizando os.walk();

(b) Versão recursiva, utilizando os.listdir().

Sugestão: para obter o caminho absoluto utilize a funçãoos.path.abspath().

4. Escreva um script que imprima o maior ficheiro numa dada diretoria,incluindo as suas subdiretorias.

$ python maior_ficheiro.py .(18254877, 'atrasos.csv')

5. Este exercício tem como objectivo a escrita de scripts que imprimam onome de todos os ficheiros Python numa certa diretoria que contenhamalguma linha que emparelhe com uma certa expressão regular.

(a) Por exemplo, o comando seguinte lista todos os ficheiros Python nodiretoria src que tenham alguma linha iniciada pela palavra“import”:

$ python todoser.py '^import' srcsrc/cat.pysrc/coop.pysrc/frequentes.py

Sugestão: utilize a biblioteca para expressões regulares reù, eadapte o exercício 3 acima.

(b) Adapte o exercício anterior para que seja utilizada a diretoriacorrente quando não for indicada a diretoria raiz.

(c) Faça agora o seu script aceitar a opção -r indicando que a buscadeve ser efectuada recursivamente nas subdiretorias.

6. Escreva um script que imprima a lista, sem repetidos e ordenada, detodos os módulos importados por todos os ficheiros Python constantesnuma dada diretoria. Considere os padrões:

• import m1, ..., mn

• from m import f

O nome de um módulo pode descrever submódulos utilizando umponto: from sound.effects.echo import echofilter. Por exemplo:

>>> python modulos.py sources[argparse, er, os, sys]

41

14 Ferramentas de Sistema II

1. More é um filtro para visualizar o conteúdo de um ficheiro, uma páginade cada vez. Na mais simples utilização, more é lançado da linha decomandos deste modo:

$ python more.py o_meu_ficheiro

Neste caso a primeira página do ficheiro aparece no ecrã. Depois,sempre que o utilizador carregar em Enter aparecerá uma nova página.Qualquer outra tecla seguida de Enter termina o programa.

Um exemplo de interação mais complexo especifica o número daprimeira linha a exibir (-l) e o tamanho de cada página (-c):

$ python more.py -l 15 -p 20 more.py

O valor por omissão para a primeira linha é 1 e o do comprimento dapágina é 10. Deverá ser possível executar o script com as seguintesopções:

• -h, --help mostra como utilizar o programa;

• -c N, --comprimento N indica o comprimento da página emnúmero de linhas;

• -l M, --linha M indica o número da primeira linha a mostrar.

Escreva o script more.py. Utilize o módulo argparse.

2. Escreva um script que, à semelhança do comando wc (word count) dosistema Unix, conte o número de palavras em vários ficheiros deentrada. Adicionalmente, o script deverá aceitar as seguintes opções:

• -h, --help

mostra como utilizar o programa;

• -c

mostra o número de bytes do ficheiro;

• -l

mostra o número de linhas.

Por exemplo:

$ python conta_palavras.py lab1.py lab2.py146 634 4404 lab1.py154 469 3781 lab2.py300 1103 8185 total

42

$ python conta_palavras.py -l lab1.py lab2.py146 lab1.py154 lab2.py300 total

$ python conta_palavras.py -c lab1.py lab2.py4404 lab1.py3781 lab2.py8185 total

$ python conta_palavras.py -l -c lab1.py lab2.py146 4404 lab1.py154 3781 lab2.py300 8185 total

$ python conta_palavras.py lab1.py lab2.py ff146 634 4404 lab1.py154 469 3781 lab2.py

conta_palavras.py: ff: open: No such file or directory300 1103 8185 total

3. Escreva um script que dado um ficheiro comprimido no formato .zipmostre a lista de ficheiros nele contido, o tamanho original de cadaficheiro, e o seu tamanho comprimido.

$ python listazip.py umficheiro.zip

Nome do ficheiro Tamanho Compressãot1-1415.pdf 300074 bytes 251683 bytes (83.9%)t2-1415.pdf 83083 bytes 82260 bytes (99.0%)

Sugestão: utilize o módulo zipfileù.

$Date: 2016-05-13 11:01:49 +0100 (Fri, 13 May 2016) $

43