# Exercícios de Exame

Questões de exames antigos de Fundamentos da Programação, com resolução.

Página: https://resumos.rgo.pt/cadeiras/fp/exercicios-exame/

## Condições e ciclos

Par ou ímpar decide a operação

PE1, 2020/21

Escreve um programa em Python que lê três inteiros `n1`, `n2` e `n3` dados pelo utilizador. Se `n1` for ímpar, o programa escreve o produto de `n2` e `n3`. Se `n1` for par, escreve a subtração entre `n2` e `n3`.

```python
n1 = int(input("n1? "))
n2 = int(input("n2? "))
n3 = int(input("n3? "))

```



### Testes

**Ímpar dá produto**

Entrada:

```text
3
4
5
```

Saída esperada:

```text
20
```

**Par dá subtração**

Entrada:

```text
2
4
5
```

Saída esperada:

```text
-1
```

Solução

```
n1 = int(input("n1? "))
n2 = int(input("n2? "))
n3 = int(input("n3? "))

if n1 % 2 != 0:
    print(n2 * n3)
else:
    print(n2 - n3)
```

O resto da divisão por 2 distingue par de ímpar: `n1 % 2 != 0` é verdadeiro só quando `n1` é ímpar. Cada ramo escreve a expressão pedida.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/fp/condicoes-ciclos/#escolher-um-ramo)

Persistência multiplicativa

PE1, 2020/21

A persistência multiplicativa de um inteiro positivo é o número de vezes que os seus dígitos podem ser multiplicados até o número ficar com um só dígito. Por exemplo, a persistência de 39 é 3, porque 39 → 3·9 = 27 → 2·7 = 14 → 1·4 = 4. Escreve um programa em Python que, dado um número `num` lido do utilizador, escreve a sua persistência multiplicativa.

```python
num = int(input("num? "))
count = 0
print(count)
```



### Testes

**Exemplo do enunciado**

Entrada:

```text
39
```

Saída esperada:

```text
3
```

**Um dígito**

Entrada:

```text
4
```

Saída esperada:

```text
0
```

**Quatro passos**

Entrada:

```text
77
```

Saída esperada:

```text
4
```

Solução

```
num = int(input("num? "))

count = 0
while num > 9:
    aux = 1
    while num != 0:
        aux = (num % 10) * aux
        num = num // 10
    num = aux
    count += 1

print(count)
```

O ciclo exterior conta um passo por multiplicação. O ciclo interior calcula o produto dos dígitos: `num % 10` dá o último dígito e `num // 10` o remove. O ciclo termina quando resta um só dígito (`num <= 9`).

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/fp/condicoes-ciclos/#ciclos-while-e-termina%C3%A7%C3%A3o)

Inverter um inteiro sem usar strings

PE1, 2019/20

Escreve um programa em Python que, dado um inteiro `num` lido do utilizador, calcula o seu reverse (o número com os dígitos por ordem inversa) e o escreve. Não podes converter o número numa string nem manipular strings. Por exemplo, para `num = 766` a saída é `667` e para `num = 45654` a saída é `45654`.

```python
num = int(input("num? "))
rev = 0
print(rev)
```



### Testes

**Três dígitos**

Entrada:

```text
766
```

Saída esperada:

```text
667
```

**Palíndromo**

Entrada:

```text
45654
```

Saída esperada:

```text
45654
```

**Zero**

Entrada:

```text
0
```

Saída esperada:

```text
0
```

Solução

```
num = int(input("num? "))

tmp = num
rev = 0
while tmp > 0:
    d = tmp % 10
    rev = rev * 10 + d
    tmp = tmp // 10

print(rev)
```

A cada passo, `tmp % 10` extrai o último dígito e `rev = rev * 10 + d` acrescenta esse dígito à direita do número que está a construir. Para `num = 0` o ciclo não corre e a saída é 0.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/fp/condicoes-ciclos/#construir-um-n%C3%BAmero-a-partir-dos-d%C3%ADgitos)

Converter quaternário para decimal

PE1, 2019/20

Um número quaternário (base 4) usa apenas os dígitos 0, 1, 2 e 3. Escreve um programa em Python que converte um número quaternário `quat` (base 4), lido do utilizador, no número decimal (base 10) correspondente. Por exemplo, para `quat = 123` a saída é `27` e para `quat = 112233` a saída é `1455`.

```python
quat = int(input("Quaternary number = "))
dec = 0
print(dec)
```



### Testes

**Exemplo 123**

Entrada:

```text
123
```

Saída esperada:

```text
27
```

**Exemplo 11**

Entrada:

```text
11
```

Saída esperada:

```text
5
```

**Seis dígitos**

Entrada:

```text
112233
```

Saída esperada:

```text
1455
```

Solução

```
quat = int(input("Quaternary number = "))

dec = 0
power = 0

while quat:
    last = quat % 10
    dec += last * 4 ** power
    quat //= 10
    power += 1

print(dec)
```

Cada dígito `last` vale `last * 4^power`, com a posição `power` a começar em 0. `quat % 10` dá o dígito menos significativo e `quat //= 10` avança para o seguinte.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/fp/condicoes-ciclos/#construir-um-n%C3%BAmero-a-partir-dos-d%C3%ADgitos)

## Funções

Verificar número de Armstrong

PE2, 2020/21

Escreve uma função em Python `is_armstrong(n)` que verifica se um número `n` de três dígitos é um número de Armstrong. Num número de Armstrong de três dígitos, a soma dos cubos de cada dígito é igual ao próprio número. A função devolve `True` ou `False`.

```python
def is_armstrong(n):
    return False
```



### Testes

**153 é Armstrong**


```python
print(is_armstrong(153))
```


Saída esperada:

```text
True
```

**370 é Armstrong**


```python
print(is_armstrong(370))
```


Saída esperada:

```text
True
```

**123 não é Armstrong**


```python
print(is_armstrong(123))
```


Saída esperada:

```text
False
```

Solução

```
def is_armstrong(n):
    soma = 0
    aux = n
    while aux > 0:
        digit = aux % 10
        soma += digit ** 3
        aux //= 10
    return soma == n
```

Percorrem-se os dígitos de `n` com `aux % 10` e `aux //= 10`, acumulando o cubo de cada um em `soma`. No fim, compara-se a soma com o número original. Para 153: 1 + 125 + 27 = 153.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/fp/funcoes/#contrato-e-decomposi%C3%A7%C3%A3o)

Média móvel com vizinhança ímpar

PE2, 2020/21

Escreve uma função em Python `moving_average(alist, n)` que, dada uma lista `alist` de inteiros e um inteiro ímpar `n` (a amplitude da vizinhança), devolve uma lista com as médias da vizinhança de cada número, arredondadas a duas casas decimais. Cada vizinhança tem exatamente `n` elementos. Se `alist` tiver comprimento menor que 3 ou se `n < 3`, o resultado é a lista vazia. Por exemplo, `moving_average([1, 2, 3, 4, 5], 3)` devolve `[2.0, 3.0, 4.0]`.

```python
def moving_average(alist, n):
    return []
```



### Testes

**Exemplo do enunciado**


```python
print(moving_average([1, 2, 3, 4, 5], 3))
```


Saída esperada:

```text
[2.0, 3.0, 4.0]
```

**Lista demasiado curta**


```python
print(moving_average([1, 2], 3))
```


Saída esperada:

```text
[]
```

**Vizinhança total**


```python
print(moving_average([1, 2, 3, 4, 5], 5))
```


Saída esperada:

```text
[3.0]
```

Solução

```
def moving_average(alist, n):
    if len(alist) < 3 or n < 3:
        return []
    avgs = []
    for i in range(n // 2, len(alist) - n // 2):
        left = alist[i - n // 2:i]
        right = alist[i + 1:i + n // 2 + 1]
        neighbors = left + right
        avgs.append(round(sum(neighbors) / len(neighbors), 2))
    return avgs
```

Só os índices com `n // 2` elementos de cada lado têm uma vizinhança completa, por isso o ciclo começa em `n // 2` e termina antes de `len(alist) - n // 2`. A média usa os `n - 1` vizinhos (o elemento central não entra), como no exemplo: (1+3)/2 = 2.0.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/fp/funcoes/#listas-o-m%C3%ADnimo-necess%C3%A1rio)

Dígitos por ordem decrescente

PE2, 2019/20

Escreve uma função em Python `order_digits(n)` que, dado um inteiro `n` maior ou igual a zero, devolve um tuplo com os dígitos do número por ordem decrescente. Por exemplo, se `n = 9013322` o resultado é o tuplo `(9, 3, 3, 2, 2, 1, 0)`.

```python
def order_digits(n):
    return ()
```



### Testes

**Exemplo do enunciado**


```python
print(order_digits(9013322))
```


Saída esperada:

```text
(9, 3, 3, 2, 2, 1, 0)
```

**Zero**


```python
print(order_digits(0))
```


Saída esperada:

```text
(0,)
```

**Dígito repetido**


```python
print(order_digits(500))
```


Saída esperada:

```text
(5, 0, 0)
```

Solução

```
def order_digits(n):
    if n == 0:
        return (0,)
    result = ()
    for i in range(9, -1, -1):
        aux = n
        while aux > 0:
            if aux % 10 == i:
                result += (i,)
            aux //= 10
    return result
```

Para cada dígito possível de 9 até 0, percorre-se o número e acrescenta-se esse dígito ao tuplo uma vez por cada ocorrência. O caso `n == 0` é tratado à parte porque o ciclo while nunca correria.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/fp/funcoes/#listas-o-m%C3%ADnimo-necess%C3%A1rio)

## Strings

Trocar maiúsculas e minúsculas

PE3, 2020/21

Escreve uma função em Python `swap_case(astr)` que, dada uma string `astr`, devolve outra string com todas as letras minúsculas convertidas em maiúsculas e vice-versa. Por exemplo, `swap_case("aBcD")` devolve `"AbCd"`.

```python
def swap_case(astr):
    return astr
```



### Testes

**Exemplo do enunciado**


```python
print(swap_case('aBcD'))
```


Saída esperada:

```text
AbCd
```

**Símbolos não mudam**


```python
print(swap_case('Hello!'))
```


Saída esperada:

```text
hELLO!
```

Solução

```
def swap_case(astr):
    result = ""
    for letter in astr:
        if letter.isupper():
            result += letter.lower()
        else:
            result += letter.upper()
    return result
```

Percorre-se a string letra a letra e constrói-se o resultado por concatenação, trocando a capitalização de cada letra. Caracteres que não são letras (como `!`) não são maiúscula nem minúscula e passam para o outro ramo, que os mantém inalterados.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/fp/strings/#texto-%C3%A9-imut%C3%A1vel)

Contar padrões de subcadeias

PE2, 2019/20

Escreve uma função em Python `subpatterns(astring)` que recebe uma string `astring` e calcula quantas das suas subcadeias seguem um certo padrão. Uma subcadeia é um padrão quando o número de vezes que cresce é igual ao número de vezes que encolhe: num passo, a subcadeia cresce se o caráter for maior que o anterior e encolhe se for menor. Por exemplo, `subpatterns("aghljcb")` devolve a string `"The string 'aghljcb' contains 3 substring patterns."`.

```python
def subpatterns(astring):
    return ""
```



### Testes

**Exemplo do enunciado**


```python
print(subpatterns("aghljcb"))
```


Saída esperada:

```text
The string 'aghljcb' contains 3 substring patterns.
```

**Sem padrões**


```python
print(subpatterns("ab"))
```


Saída esperada:

```text
The string 'ab' contains 0 substring patterns.
```

Solução

```
def is_pattern(astring):
    net = 0
    for i in range(len(astring) - 1):
        if astring[i + 1] > astring[i]:
            net += 1
        if astring[i + 1] < astring[i]:
            net -= 1
    return net == 0

def subpatterns(astring):
    counter = 0
    for step in range(2, len(astring) + 1):
        for char_index in range(0, len(astring) - step + 1):
            sub_str = astring[char_index:char_index + step]
            if is_pattern(sub_str):
                counter += 1
    return "The string '{0}' contains {1} substring patterns.".format(
        astring, counter)
```

Uma subcadeia é padrão quando o saldo entre crescimentos (+1) e encolhecimentos (-1) é zero. Experimentam-se todas as subcadeias de comprimento pelo menos 2 e conta-se quantas têm saldo zero.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/fp/strings/#procurar-e-contar)

## Dicionários e conjuntos

Valores únicos de uma lista de dicionários

PE3, 2020/21

Escreve uma função em Python `unique_values(alist)` que, dada uma lista de dicionários `alist`, devolve um conjunto com os valores de todos os dicionários. Por exemplo, `unique_values([{"a": 1, "b": 2}, {"b": 2, "c": 3}])` devolve `{1, 2, 3}`.

```python
def unique_values(alist):
    return set()
```



### Testes

**Exemplo do enunciado**


```python
print(unique_values([{'a': 1, 'b': 2}, {'b': 2, 'c': 3}]))
```


Saída esperada:

```text
{1, 2, 3}
```

**Lista vazia**


```python
print(unique_values([]))
```


Saída esperada:

```text
set()
```

Solução

```
def unique_values(alist):
    uniqs = set()
    for d in alist:
        for v in d.values():
            uniqs.add(v)
    return uniqs
```

Percorrem-se os valores de cada dicionário com `d.values()` e juntam-se todos a um conjunto, que elimina duplicados automaticamente.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/fp/dicionarios-conjuntos/#conjuntos-e-perten%C3%A7a)

Somar dicionários

PE4, 2020/21

Escreve uma função em Python `sum_dicts(lst)` que recebe uma lista `lst` de dicionários, cada um com um conjunto de chaves e valores inteiros, e devolve um único dicionário com todas as chaves presentes. Os valores associados à mesma chave são somados. Por exemplo, `sum_dicts([{"a": 5, "b": 3}, {"a": 1, "c": 0}])` devolve `{"a": 6, "b": 3, "c": 0}`.

```python
def sum_dicts(lst):
    return {}
```



### Testes

**Exemplo do enunciado**


```python
print(sum_dicts([{'a': 5, 'b': 3}, {'a': 1, 'c': 0}]))
```


Saída esperada:

```text
{'a': 6, 'b': 3, 'c': 0}
```

**Chave só num dicionário**


```python
print(sum_dicts([{'x': 2}, {'y': 4}]))
```


Saída esperada:

```text
{'x': 2, 'y': 4}
```

Solução

```
def sum_dicts(lst):
    result = {}
    for d in lst:
        for k, v in d.items():
            result[k] = result.get(k, 0) + v
    return result
```

Para cada par chave-valor, `result.get(k, 0)` devolve o valor acumulado ou 0 se a chave ainda não existe, e o valor novo é somado. Assim todas as chaves ficam no dicionário final.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/fp/dicionarios-conjuntos/#dicion%C3%A1rios-chaves-e-valores)

Processar comandos sobre conjuntos

PE3, 2019/20

Escreve uma função em Python `process(commands)` que recebe uma lista `commands` a processar sobre conjuntos, pela ordem dada. Por exemplo, `[{1, 3, 4}, "|", {2, 5}]` deve ser convertido em `{1, 2, 3, 4, 5}`. As operações binárias disponíveis são `"|"` (união), `"&"` (interseção), `"-"` (diferença) e `"x"` (produto cartesiano, que devolve pares).

```python
def process(commands):
    return commands[0]
```



### Testes

**União**


```python
print(process([{1, 3, 4}, '|', {2, 5}]))
```


Saída esperada:

```text
{1, 2, 3, 4, 5}
```

**Diferença**


```python
print(process([{1, 3, 4}, '-', {3}]))
```


Saída esperada:

```text
{1, 4}
```

**Interseção**


```python
print(process([{1, 2}, '&', {2, 3}]))
```


Saída esperada:

```text
{2}
```

Solução

```
def process(commands):
    s = commands[0]
    for op, t in zip(commands[1::2], commands[2::2]):
        if op == '|':
            s = s | t
        if op == '&':
            s = s & t
        if op == '-':
            s = s - t
        if op == 'x':
            r = set()
            for i in s:
                for j in t:
                    r.add((i, j))
            s = r
    return s
```

A lista alterna conjunto, operador, conjunto. `commands[1::2]` são os operadores e `commands[2::2]` os operandos seguintes; o `zip` emparelha-os e cada operador é aplicado ao acumulador `s`. O produto cartesiano constrói explicitamente o conjunto de pares.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/fp/dicionarios-conjuntos/#conjuntos-e-perten%C3%A7a)

## Recursão

Contar elementos numa lista aninhada

PE3, 2020/21

Escreve uma função em Python `rec_count(alist)` que calcula a frequência de cada elemento da lista aninhada `alist` (uma lista que pode conter listas, que por sua vez podem conter outras listas, e assim sucessivamente) e a devolve na forma de um dicionário. Por exemplo, `rec_count([1, [2, [1, 2]], 3])` devolve `{1: 2, 2: 2, 3: 1}`.

```python
def rec_count(alist):
    return {}
```



### Testes

**Exemplo do enunciado**


```python
print(rec_count([1, [2, [1, 2]], 3]))
```


Saída esperada:

```text
{1: 2, 2: 2, 3: 1}
```

**Lista vazia**


```python
print(rec_count([]))
```


Saída esperada:

```text
{}
```

**Repetidos em níveis diferentes**


```python
print(rec_count([5, [5]]))
```


Saída esperada:

```text
{5: 2}
```

Solução

```
def rec_count(alist):
    result = {}
    for el in alist:
        if type(el) != list:
            d = {el: 1}
        else:
            d = rec_count(el)
        for k, v in d.items():
            result[k] = result.get(k, 0) + v
    return result
```

Se o elemento não é uma lista, conta-se como uma ocorrência (`{el: 1}`); se for, conta-se recursivamente a sublista. Depois de cada chamada recursiva, os pares do dicionário devolvido são somados ao acumulador `result`.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/fp/recursao/#estruturas-aninhadas)

Contar dígitos recursivamente

PE3, 2019/20

Escreve uma função em Python `count_digits(n)` que calcula a frequência de cada dígito do número `n`, com `n > 0`, e a devolve na forma de um dicionário. Não podes usar ciclos nem variáveis globais. Por exemplo, `count_digits(12321)` devolve `{1: 2, 2: 2, 3: 1}`.

```python
def count_digits(n):
    return {}
```



### Testes

**Exemplo do enunciado**


```python
print(count_digits(12321))
```


Saída esperada:

```text
{1: 2, 2: 2, 3: 1}
```

**Um dígito**


```python
print(count_digits(5))
```


Saída esperada:

```text
{5: 1}
```

Solução

```
def count_digits(n):
    if n == 0:
        return {}
    d = count_digits(n // 10)
    d[n % 10] = d.get(n % 10, 0) + 1
    return d
```

O caso base é `n == 0`, que devolve o dicionário vazio. A chamada recursiva trata do número sem o último dígito e, no regresso, esse dígito é contado no dicionário devolvido. Assim cada dígito é processado uma vez, sem ciclos.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/fp/recursao/#recurs%C3%A3o-sobre-d%C3%ADgitos)

Calculadora de frações

PE3, 2020/21

Escreve uma função em Python `calculator(expr)` que calcula o valor de uma expressão `expr`. A expressão pode ser uma fração representada por um tuplo `(numerador, denominador)` ou um tuplo da forma `(expr, operador, expr)`. Os únicos operadores válidos são a multiplicação `"*"` e a divisão `"/"`, e todos os valores são não negativos. Simplifica o resultado à menor fração inteira. Por exemplo, `calculator(((1, 3), "*", (2, 5)))` calcula 1/3 · 2/5 e devolve `(2, 15)`.

```python
def calculator(expr):
    return expr
```



### Testes

**Multiplicação do enunciado**


```python
print(calculator(((1, 3), '*', (2, 5))))
```


Saída esperada:

```text
(2, 15)
```

**Divisão simplificada**


```python
print(calculator(((1, 2), '/', (1, 4))))
```


Saída esperada:

```text
(2, 1)
```

**Expressão aninhada**


```python
print(calculator((((1, 2), '*', (1, 3)), '/', (1, 6))))
```


Saída esperada:

```text
(1, 1)
```

Solução

```
def mdc(x, y):
    while y:
        x, y = y, x % y
    return x

def calculator(expr):
    if len(expr) == 2:
        num, den = expr
    else:
        e1, op, e2 = expr
        e1 = calculator(e1)
        e2 = calculator(e2)
        if op == '*':
            num, den = e1[0] * e2[0], e1[1] * e2[1]
        else:
            num, den = e1[0] * e2[1], e1[1] * e2[0]
    d = mdc(num, den)
    return (num // d, den // d)
```

O caso base é um tuplo de dois elementos (a fracción). Num tuplo de três, calculam-se recursivamente as duas subexpressões e aplicam-se as regras: multiplicam-se numeradores com numeradores e denominadores com denominadores; na divisão, cruza-se. No fim, divide-se pelo máximo divisor comum para simplificar.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/fp/recursao/#express%C3%B5es-como-%C3%A1rvores)

## Geradores

Gerador de Fibonacci

PE4, 2020/21

Escreve uma função geradora em Python `fib(start, end)` que gera a sequência de Fibonacci de inteiros começando no `start`\-ésimo número (`start >= 1`) e acabando no `end`\-ésimo número (`end >= start`). Os dois primeiros números da sequência são 1 e cada número consecutivo é a soma dos dois anteriores. Por exemplo, se `start = 1` e `end = 7`, a sequência gerada é `[1, 1, 2, 3, 5, 8, 13]`.

```python
def fib(start, end):
    return
```



### Testes

**Sequência completa**


```python
print(list(fib(1, 7)))
```


Saída esperada:

```text
[1, 1, 2, 3, 5, 8, 13]
```

**A meio da sequência**


```python
print(list(fib(4, 6)))
```


Saída esperada:

```text
[3, 5, 8]
```

Solução

```
def fib(start, end):
    i = 1
    a, b = 1, 1
    while i <= end:
        if i >= start:
            yield a
        a, b = b, a + b
        i += 1
```

A sequência tem de ser calculada desde o início, independentemente de `start`, por isso o contador `i` começa em 1. Só se faz `yield` quando `i >= start`, e `a, b = b, a + b` avança dois termos de cada vez.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/fp/compreensoes-geradores/#geradores-e-yield)

Gerador a partir de uma lista de intervalos

PE4, 2019/20

Uma lista de intervalos é uma lista de tuplos que representam intervalos. Cada tuplo representa um intervalo da forma `(min, max)`. Os tuplos aparecem por ordem crescente na lista e os intervalos são disjuntos. Por exemplo, a lista `[(1, 1), (3, 5), (10, 15)]` representa a sequência completa 1, 3, 4, 5, 10, 11, 12, 13, 14, 15. Escreve uma função geradora `generator(intlist)` que vai devolvendo com `yield` o termo seguinte da sequência completa representada em `intlist`.

```python
def generator(intlist):
    return
```



### Testes

**Dois intervalos**


```python
print(list(generator([(1, 1), (3, 5)])))
```


Saída esperada:

```text
[1, 3, 4, 5]
```

**Intervalo com vários termos**


```python
print(list(generator([(10, 12)])))
```


Saída esperada:

```text
[10, 11, 12]
```

Solução

```
def generator(intlist):
    while intlist != []:
        yield intlist[0][0]
        if intlist[0][0] == intlist[0][1]:
            intlist = intlist[1:]
        else:
            intlist = [(intlist[0][0] + 1, intlist[0][1])] + intlist[1:]
```

Em cada passo, o primeiro valor do primeiro intervalo é devolvido com `yield`. Se `min == max`, o intervalo está esgotado e passa-se ao seguinte; senão, incrementa-se o `min` do primeiro intervalo, avançando para o próximo termo.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/fp/compreensoes-geradores/#gerar-valores-de-v%C3%A1rios-intervalos)