Ficha 01 · Recursão e algoritmos
- Aplicar recursão
- Implementar pesquisa
- Reconhecer complexidade
- Comparar algoritmos
- Depurar
Parte I · Recursão
Exercício 1 · Identificar partes (10 pts)
Para esta função, que calcula o máximo divisor comum de dois inteiros:
def mdc(a, b):
if b == 0:
return a
return mdc(b, a % b)
a) Qual o caso base? (3 pts)
b) Qual o passo recursivo e porque é que se aproxima do caso base? (3 pts)
c) Traça as chamadas de mdc(48, 18) e indica o resultado. (4 pts)
Exercício 2 · Implementar recursivamente (10 pts)
Implementa as seguintes funções recursivamente:
a) soma_natural(n): soma 1 + 2 + ... + n. (5 pts)
b) contar_digitos(n): quantos dígitos tem o número n (para n >= 0). (5 pts)
Exercício 3 · Contar ficheiros numa árvore de pastas (15 pts)
Implementa contar_py(pasta) que devolve quantos ficheiros terminados em .py existem na pasta indicada e em todas as subpastas. Usa os.listdir e os.path.isdir. Se uma pasta não puder ser lida por falta de permissão, conta como 0.
Parte II · Pesquisa
Exercício 4 · Pesquisa binária em registos (15 pts)
Uma lista de tuplos (número, nome) está ordenada por número de aluno. Implementa procurar_aluno(alunos, numero) com pesquisa binária, que devolve o nome ou None se o número não existir.
alunos = [(3, "Marta"), (8, "Hugo"), (12, "Inês"), (15, "Tiago"),
(21, "Bia"), (27, "Dário"), (30, "Lia")]
Exercício 5 · Comparar complexidades (10 pts)
Uma aplicação de uma biblioteca guarda 100 000 códigos de livros, ordenados. Cada comparação demora 2 μs.
a) Quantas comparações faz, no máximo, a pesquisa linear? (2 pts)
b) E a pesquisa binária? Mostra como chegas ao número. (4 pts)
c) Quanto tempo demora cada uma, no pior caso? (4 pts)
Parte III · Ordenação
Exercício 6 · Bubble sort decrescente com contagem (15 pts)
Implementa bubble_desc(lst) que ordena por ordem decrescente, pára cedo se uma volta não trocar nada, e devolve a lista, o número de trocas e o número de voltas feitas. Indica o resultado para [4, 9, 2, 7, 5] e para [9, 7, 5, 4, 2].
Exercício 7 · Mergesort com chave (15 pts)
Implementa mergesort(lst, chave) que ordena uma lista de nomes primeiro por comprimento e, em caso de empate, por ordem alfabética (chave=lambda n: (len(n), n)). Compara o resultado com sorted(..., key=chave) para ["Rita", "Ana", "Joaquim", "Eva", "Luís", "Bruno", "Rui"].
Parte IV · Depuração
Exercício 8 · Encontrar o erro (10 pts)
A função devia contar quantos valores de uma lista são superiores a um limite, mas contar_acima([5, 12, 9, 15], 10) devolve 0 em vez de 2.
def contar_acima(lista, limite):
n = 0
for x in lista:
if x > limite:
n = n + 1
return n
a) Traça a execução e localiza o erro. (5 pts)
b) Escreve a versão corrigida e dois casos de teste, um deles com a lista vazia. (5 pts)