Recursão

Você já aprendeu que algoritmos recursivos para um certo problema são procedimentos que incluem instruções para resolver instâncias menores para o mesmo problema. Por esse motivo, é importante entender claramente qual é o conjunto de entradas (ou instâncias) do problema e qual é o conjunto de soluções (ou saídas) do problema. Quando tentamos resolver um problema de maneira recursiva, temos que considerar um ou mais casos básicos, que são exemplos de instâncias resolvidas diretamente, e os demais casos, quando uma solução é obtida a partir de uma solução de uma ou mais instâncias menores do problema.

O objetivo desta tarefa é começarmos a pensar recursivamente. Assim, é obrigatório resolver cada um dos problemas seguintes utilizando recursão, mesmo que você conheça um algoritmo iterativo mais eficiente. Uma das vantagens de recursão é que as funções recursivas são normalmente muito simples e elegantes. Se seu programa para alguma das questões abaixo parecer muito complicado, então pare e repense seu algoritmo. E não deixe de tirar as dúvidas que aparecerem no canal do Discord, ou com os monitores.

1. Fatorial

Faça um programa fatorial.py que calcula o fatorial de um número.

Entrada

Um número inteiro $n$ não-negativo.

6

Saída

O fatorial de $n$.

720

2. Relação de Stifel

O coeficiente binomial pode ser computado através do triângulo de Pascal. Uma entrada é computada pela chamada relação de Stifel:

$$ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} $$

Faça um programa stifel.py que calcula um coeficiente binomial.

Entrada

Números não negativos $n$ e $k$.

8 6

Saída

O valor de $\binom{n}{k}$.

28

3. Máximo divisor comum

Faça um programa mdc.py que computa o maior divisor comum de dois números.

Entrada

Dois números $a$ e $b$.

30 12

Saída

O máximo divisor comum de $a$ e $b$.

6

4. Busca binaria

Faça um programa busca_binaria.py que, dado um vetor de inteiros em ordem não-crescente e um número de consulta, realize busca binária e conte o número de vezes que esse número aparece no vetor.

Entrada

Uma sequência de números separados por espaço e um número inteiro $i$.

29 29 26 25 24 24 20 15 10 10 7 6 5 4 0
24

Saída

O número de vezes que $i$ aparece na sequência.

2

5. Fibonacci com salto

Podemos definir uma variação da sequência de Fibonacci como $f(n) = f(n-1) + f(n-3)$, tal que $f(n) = 1$ para $1 \le n \le 3$.

Faça um programa saltare.py que calcula o $n$-ésimo número dessa sequência. Considere que $n$ pode ser um número grande.

Entrada

Um número inteiro $n$ não-negativo.

10

Saída

O $n$-ésimo número da sequência.

19

6. Desafio e recompensa

João tem um dado com seis faces.
Maria está a $x$ passos de João.
Se João joga o dado e tira $p$,
Maria dá $p$ passos até o João.

Se $p$ é igual a $x$ desse momento,
Maria recompensa João agora.
Mas se for maior que $x$, João, lamento,
Maria dá as costas e vai-se embora.

Crie um programa recompensa.py que calcule a probabilidade de João receber a recompensa se ele puder jogar o dado até $n$ vezes. Você deve supor que todas as faces do dado ocorrem com probabilidades iguais.

Entrada

Número inteiros $n$ e $x$.

2 2

Saída

Um número entre 0 e 1 com três casas decimais após a vírgula representando a probabilidade de João conseguir a recompensa.

0.194

Dicas

Observe que no exemplo da entrada há apenas duas possibilidades para João ganhar o jogo: jogar o dado uma vez e obter a face 2; ou jogar o dado duas vezes obtendo a face 1 em cada uma delas. Em qualquer cenário diferente desses, Maria passará direto por João. A probabilidade de João obter a face 2 na primeira jogada é $1/6$. Se João obtém a face 1, ainda tem direito a mais uma jogada. Portanto, a probabilidade de João obter a face 1 duas vezes é $(1/6)^2 = 1/36$. A probabilidade de João ganhar a recompensa é $1/6 + 1/36 = 7/36 ≈ 0.194$. A imagem abaixo ilustra essas possibilidades.

7. Intercalar duas listas

Faça um programa intercalar.py que junte recursivamente duas sequências de números ordenados e devolva uma sequência com todos os números em ordem.

Entrada

Duas sequências de números.

1 2 5
1 3 4 4 7

Saída

A sequência com os números ordenados.

1 1 2 3 4 4 5 7

8. No meio do caminho

Uma pessoa está no canto superior esquerdo de um tabuleiro de tamanho $m \times n$ e a saída está no canto inferior direito. Ela só pode se mover uma casa para a direita ou para baixo de cada vez. Além disso, no meio do caminho há pedras. As pedras no meio do caminho bloqueiam a passagem. Há $p$ pedras. No meio do caminho.

Faça um programa caminhos.py que conte o número de caminhos livres de pedras para sair do tabuleiro.

Entrada

Na primeira linha, há dois números, $m$ e $n$. Na segunda, há um número $p$ seguido de $p$ linhas, cada uma com o número da linha e da coluna correspondentes à posição de uma pedra. Veja o exemplo.

4 5
3
2 2
3 3
3 5

Saída

Um número de caminhos livres de pedras para sair do tabuleiro.

4

9. Todos os produtos que levam a $n$

O teorema fundamental da aritmética diz que todo inteiro pode ser escrito como um único produto de números primos ordenados. Quando consideramos fatores compostos, pode haver outros produtos.

Escreva um programa produtos.py que, dado um número $n$, liste todas as forma de escrever $n$ como produto de números inteiros maiores que $1$. Os diferentes produtos devem ser apresentados em ordem lexicográfica, sem repetições.

Entrada

Um número inteiro positivo $n$

24

Saída

Todas as combinações em ordem crescente.

2*2*2*3=24
2*2*6=24
2*3*4=24
2*12=24
3*8=24
4*6=24
24=24

10. Numero de lagos

Considere uma matriz de caracteres que representa um mapa. Um caractere # representa terra e um caractere _, água. Faça um programa lagos.py que encontra os lagos e descobre o tamanho do maior deles.

Entrada

Números $m$ e $n$ seguidos de uma matriz de dimensões $m \times n$ com as colunas separadas por espaço. Você pode supor que as bordas da matriz são preenchidas com #.

11 20
# # # # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # # # #
# # _ _ # # _ # # _ _ _ _ # _ # _ # # #
# # # _ # # # # _ # # _ _ # _ _ _ _ # #
# # _ _ # # _ # _ # # _ # # # # # # # #
# # # _ # # # # # _ _ _ _ _ _ # _ _ # #
# # # _ # _ _ _ # # # _ # # # # _ # # #
# # # _ # # # # # # # _ # # _ # # # # #
# # # _ # # _ _ # _ # _ # # _ _ _ _ # #
# # # # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # # # #

Saída

O número de lagos e o tamanho do maior deles.

Número de lagos: 11
Tamanho do maior: 16

Critérios

É obrigatório implementar todas os programas de maneira recursiva. Você pode utilizar instruções for ou while quando fizer sentido, desde que o algoritmo que resolve o problema seja de fato recursivo. Tentativas de passar nos testes com algoritmos não-recursivos serão interpretadas como fraude. Para obter conceito B, resolva pelo menos até a questão 8. Para obter A, resolva também a questão 9 ou 10.

Correção

Esta tarefa será corrigida automaticamente sempre que você realizar um git push. Depois de terminada a tarefa, deve-se utilizar o botão na interface de notas para solicitar a correção de um monitor.

← Anterior Voltar