Prazo de entrega recomendado: 04/07/2021

Não há como aprender recursão sem praticar bastante.

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ásico, 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. Máximo

Dada uma lista de elementos, faça um programa maximo.py que encontra o maior elemento.

Entrada

Uma sequência de números separados por espaço.

19 21 24 23 10 29 24 8 23 29 8 6

Saída

O maior elemento da sequência.

2. Fatorial

Faça um programa fatorial.py que calcula o fatorial de um número inteiro $n$ não-negativo.

Entrada

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

Saída

O fatorial de $n$.

3. Busca em um vetor ordenado

Dado um vetor de inteiros em ordem crescente e um número, faça um programa busca_binaria.py que realize uma busca binária e retorne o índice da posição desse número no vetor ou -1 se esse número não estiver no vetor.

Entrada

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

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

Saída

A posição de $i$ na sequência ou -1.

4. Sequência de Pedrinho

Pedrinho acha muito chata a sequência de Fibonacci, então resolveu criar sua própria sequência, a sequência de Pedrinho. Os três primeiros elementos são $P_1 = 1$, $P_2 = 2$ e $P_3 = 3$ e os demais elementos têm a seguinte regra de formação:

$$ P_n = 1P_{n-1} + 2P_{n-2} + 3P_{n-3}. $$

Crie um programa sequencia.py que calcule o $n$-ésimo número de Pedrinho.

Entrada

Um número $n$.

Saída

O número $P_n$.

5. Formiga de Langton

Um tabuleiro retangular tem diversos quadrados dispostos em uma grade de tamanho $m \times n$, onde $m$ e $n$ são o número de linhas e o número de colunas, respectivamente. Cada um desses quadrados tem uma cor, que pode ser branco ou preto. Sobre esse tabuleiro, há uma formiga que se move de acordo com as seguintes regras:

estando em um quadrado branco, ela vira 90° para a direita, muda a cor do quadrado para preto e avança uma unidade;
estando em um quadrado preto, ela vira 90° para a esquerda, muda a cor do quadrado para branco e avança uma unidade.

Essa é uma formiga de Langton. Crie um programa langton.py que mostre o estado do tabuleiro após $t$ iterações. Suponha que a formiga inicia no quadrado central do tabuleiro virada para baixo e que ela não sairá do tabuleiro em nenhuma das entradas de teste.

Entrada

A primeira linha contém os inteiros $t$, $m$ e $n$. É garantido que $m$ e $n$ são ímpares. As demais linhas correspondem às linhas do tabuleiro, de forma que um ponto . representa um quadrado branco e um caractere # representa um quadrado preto.

4 9 9
....#....
....#....
....#....
....#....
#########
....#....
....#....
....#....
....#....

Saída

O estado final do tabuleiro.

....#....
....#....
....#....
....###..
####..###
....#....
....#....
....#....
....#....

6. Quick-sort

Faça um programa quick_sort.py que, ao receber uma lista de elementos, retorna essa lista em ordem crescente. Para isso, implemente o algoritmo de ordenação quick-sort.

Entrada

Uma sequência de números separados por espaço.

8 10 13 17 14 16 2 19 7 2 18 16

Saída

A sequência em ordem crescente.

2 2 7 8 10 13 14 16 16 17 18 19

7. Quase palíndromo

Uma string é um $k$-quase palíndromo se, ao compará-la com o seu inverso, tiver no máximo $k$ caracteres diferentes. Por exemplo, arara é um $0$-quase palíndromo e araro é um $2$-quase palíndromo.

Crie um programa quase_palindromo.py que verfique se uma palavra é um $k$-quase palíndromo.

Entrada

A primeira linha contém um número $k$ e a segunda linha contém uma string.

2
araro

Saída

Uma linha contendo sim ou nao, dependendo se a string é um $k$-quase palíndromo.

sim

8. 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.

9. Todas as somas que levam a $n$

Dado um número $n$, encontre todas as combinações de somas de números positivos que resultam em $n$. Seu programa soma_n.py deverá imprimir todas as somas cujos termos estão em ordem crescente. As diferentes somas devem ser apresentadas em ordem lexicográfica, sem repetições.

Entrada

O número $n$.

Saída

Todas as combinações em ordem crescente.

1+1+1+1+1=5
1+1+1+2=5
1+1+3=5
1+2+2=5
1+4=5
2+3=5
5=5

10. Um caminho para escapar do labirinto

Faça um programa caminho.py que encontra um caminho (não necessariamente com comprimento mínimo) para atravessar um labirinto. O labirinto é representado por uma matriz sendo que as paredes são indicadas por #. A entrada e saída são indicadas por E e S respectivamente. É possível se mover em $4$ direções: cima, baixo, esquerda e direita.

Entrada

Um labirinto.

###E####
#      #
# #  # #
# ## # #
#  #   #
#####S##

Saída

Um caminho na forma de uma sequência de coordenadas de matriz.

Dicas

Há diversas formas de ler a matriz da entrada. Uma forma bastante simples é, tendo importado a biblioteca fileinput, ler cada linha da entrada iterando entre fileinput.input(), sem esquecer de chamar a função rstrip() para remover caracteres de final de linha.
```
for linha in fileinput.input():
  linha_final = linha.rstrip()
```
Imagine que você está dentro desse labirinto. Se você já passou por alguma posição, você não deseja passar por lá novamente. Assim, o que você faz para marcar que já passou por ali? Deixa uma migalha de pão, digo, um asterisco. Depois de marcar uma posição, você tenta mover-se para cada uma das direções possíveis, uma por vez, evitando voltar a alguma posição marcada. Se não tiver sorte em nenhuma das direções, provavelmente você fez alguma escolha errada antes. Desmarque a posição, coma sua migalha de pão e retorne à posição anterior.

Correção

Esta tarefa será avaliada pelo corretor automático e por um monitor, mas sem apresentação do aluno. Para passar na tarefa, você precisa resolver corretamente as questões 1, 2, 3 e 4. Para obter o conceito B você também precisa resolver corretamente as questões 5, 6 e 7. Para obter o conceito A você também precisa resolver pelo menos duas dentre as questões 8, 9 e 10.

O script de teste não irá verificar se você realmente utilizou um algoritmo recursivo, mas você deve resolver cada questão individualmente e genuinamente. Se tiver alguma dúvida, procure os monitores. Tentativas de passar no teste automático sem resolver os problemas ou usando algoritmos não recursivos serão consideradas fraude. Você não pode copiar nem consultar quaisquer soluções prontas; qualquer tentativa nesse sentido será considerada fraude.

Lembre-se de que seu programa deverá estar organizado em funções adequadamente, cada uma com uma responsabilidade bem definida. Crie uma função principal e não execute instruções no nível global. Não serão aceitos programas desorganizados ou ilegíveis.

A pasta da tarefa no seu repositório vem inicialmente com um arquivo nao_corrigir.txt que serve para indicar que você ainda está trabalhando nesta tarefa. Você pode realizar quantos pushes quanto forem necessários. O monitor só irá corrigir sua tarefa quando esse arquivo for removido do repositório.