Atenção: Esta tarefa não será corrigida manualmente, mas você deve tentar respondê-la genuinamente. Se tiver alguma dúvida se ela está ou não correta, procure os monitores. Tentativas de passar no teste automático sem responder as questões serão consideradas fraude. Você não pode copiar nem consultar quaisquer soluções prontas; qualquer tentativa nesse sentido será considerada fraude.

É obrigatório resolver cada um dos problemas seguintes utilizando recursão.

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.

18 75 70 10 168 13 184 76 97 195 35 99 79 82 162 114 73 136 148 26 119 159 153 122 15 116 15 36 176 92 57 193 166 127 2 133 139 185 9 35 180 44 134 58 125 95 171 198 31 119 23 150 78 176 71 93 91 85 128 66 177 185 59 142 111 60 75 49 45 84 84 25 127 18 82 52 113 53 49 143 171 72 93 49 47 163 141 138 48 69 4 24 53 62 166 164 122 41 12 167

Saída

O maior elemento da sequência.

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-Fibonacci

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

Faça um programa fibonacci3.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.

Saída

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

83047505

Conjectura de Collatz

Considere o seguinte procedimento em um número inteiro positivo $n$:

se $n$ é par, divida por 2;
se $n$ é ímpar, multiplique $n$ por 3, some 1 e divida por 2.

A conjectura de Collatz diz que se repetirmos esse procedimento no resultado da execução anterior um número suficiente de vezes, eventualmente vamos chegar ao número 1. Faça um programa collatz.py que dado um número inteiro positivo, determina o número de repetições do procedimento para chegar em 1.

Entrada

Um número inteiro positivo $n$.

Saída

O número de passos para convergir para 1.

Mínimo Múltiplo Comum

O mínimo múltiplo comum entre dois números $a$ e $b$ é o menor número $c$ que é divisível por $a$ e $b$. Faça um programa mmc.py que dados dois números $a$ e $b$, calcula o mínimo múltiplo comum entre esses dois números sem fazer uma busca exaustiva. Você pode usar o algoritmo para encontrar o máximo divisor comum.

Entrada

Dois números $a$ e $b$ separados por espaço.

12 9

Saída

O mínimo múltiplo comum de $a$ e $b$.

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 retorne o índice da posição desse número no vetor ou $-1$ se esse número não está no vetor.

Entrada

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

1 3 4 7 12 17 18 24 25 26 28 29 31 32 33 34 35 36 37 40 43 44 45 47 51 53 54 55 57 58 60 62 63 65 70 74 75 77 79 81 82 85 86 87 90 93 94 95 97 100
31

Saída

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

Torre de Hanoi

Faça um programa hanoi.py que determina o número mínimo de movimentos para resolver o problema da torre de Hanói com $n$ discos.

Entrada

Um número $n$.

Saída

O número mínimo de movimentos para resolver a torre de Hanói com $n$ discos.

Merge sort

Faça um programa merge_sort.py que dada uma lista de elementos, retorna essa lista em ordem crescente. Para isso, implemente o algoritmo de ordenação mergesort.

Entrada

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

18 75 70 10 168 13 184 76 97 195 35 99 79 82 162 114 73 136 148 26 119 159 153 122 15 116 15 36 176 92 57 193 166 127 2 133 139 185 9 35 180 44 134 58 125 95 171 198 31 119 23 150 78 176 71 93 91 85 128 66 177 185 59 142 111 60 75 49 45 84 84 25 127 18 82 52 113 53 49 143 171 72 93 49 47 163 141 138 48 69 4 24 53 62 166 164 122 41 12 167

Saída

A sequência em ordem crescente.

2 4 9 10 12 13 15 15 18 18 23 24 25 26 31 35 35 36 41 44 45 47 48 49 49 49 52 53 53 57 58 59 60 62 66 69 70 71 72 73 75 75 76 78 79 82 82 84 84 85 91 92 93 93 95 97 99 111 113 114 116 119 119 122 122 125 127 127 128 133 134 136 138 139 141 142 143 148 150 153 159 162 163 164 166 166 167 168 171 171 176 176 177 180 184 185 185 193 195 198

Potência, rápido!!!

Dado dois números inteiros positivos $a$ e $b$, faça um programa potencia.py que calcule $a^b$ fazendo no máximo $\log_2(b) + 1$ chamadas recursivas.

Entrada

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

2 3

Saída

O resultado de $a^b$.

Encontrar o menor elemento ausente de uma sequência ordenada

Dada uma sequência ordenada (crescente) de números, faça um programa menor_ausente.py que encontre o menor elemento ausente dessa sequência.

Entrada

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

0 1 2 3 4 5 6 7 8 9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95  96  97  98  99 100 101

Saída

O menor número ausente da sequência.

Encontrar o k-ésimo menor elemento em uma sequência possivelmente não-ordenada

Dada uma sequência de números não necessariamente ordenada, faça um programa k-esimo.py que encontre o $k$-ésimo menor elemento.

Entrada

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

88 46 50 82 128 91 36 78 163 188 4 142 89 27 148 18 194 130 156 115 13 26 34 85 174 74 95 104 182 150 134 64 24 100 155 187 159 48 38 65 127 195 41 8 129 75 93 103 6 33 169 166 190 132 177 19 147 105 110 60 59 7 53 111 114 39 189 153 141 136 139 168 108 140 124 71 123 101 90 70 200 122 20 175 35 21 162 58 126 109 25 11 172 146 43 69 183 133 2 52
25

Saída

O maior $k$-ésimo menor elemento da sequência.

Todas as combinações de $n$ dígitos

Dado um número $n$. Encontre todas as combinações de $n$ dígitos (0-9) cuja soma dos dígitos é um determinado valor $s$. Seu programa n-digitos.py deverá imprimir todas combinações em ordem crescente.

Entrada

Um número de dígitos $n$ e o valor da soma $s$.

3 10

Saída

Todas as combinações em ordem crescente.

Dica

Há várias formas de fazer isso. Uma maneira é supor que sua função recursiva já recebe um vetor dos $n$ dígitos, mas que as primeiras $m$ posições já estão preenchidas. Assim, falta listar apenas as combinações que começam com esses $m$ dígitos.

Menor caminho para escapar do labirinto

Faça um programa menor_caminho.py que encontra o caminho mais curto 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

O labirinto com o menor caminho marcado com *.

###E#########
#***  #  #  #
#*# #### # ##
#*### #  # ##
#******# #  #
## ###*   # #
#   # *##   #
######S######

Dicas

Você pode supor que há um único caminho, para cada um dos labirintos de teste. Assim, não precisa se preocupar em encontrar o menor caminho.
Imagine que você está dentro desse labirinto. Se você já passou por alguma posição, você não deseja passar por lá novamente. Assim, 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.

Observações

Para obter conceito B você precisa passar em todos os testes com exceção de teste_11_ndigitos e teste_12_menor_caminho. Para obter conceito A é necessário passar em pelo menos um desses dois.
Não custa lembrar: faça um commit registrando suas alterações a cada nova atividade realizada.