Partilhar: Classroom Teams WhatsApp
aulify
UC UC00607 · T. Desenv. Software

Ficha 01 · Recursão e algoritmos

Caso base, passo recursivo, pesquisa, ordenação, depuração
Versão · Aluno
Tempo · 60 minutos
Cotação · 100 pontos
Aluno(a)
Turma
Nº
Data
Objectivos da ficha

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)