4.17. Exercícios de Programação¶

Escreva uma função recursiva para calcular o fatorial de um número.
Escreva uma função recursiva para inverter uma lista.
Modifique o programa recursivo para desenhar árvores usando uma ou todas as seguintes idéias:
- Modifique a espessura dos ramos para que, quando o branchLen ficar menor, a linha fica mais fina.
- Modifique a cor dos ramos para que, quando o branchLen ficar muito curto, seja colorido como uma folha.
- Modifique o ângulo usado na rotação da tartaruga para que em cada bifurcação o ângulo seja selecionado aleatoriamente dentro de algum intervalo. Por exemplo escolha o ângulo entre 15 e 45 graus. Teste alguns valores até descobrir valores que geram boas árvores.
- Modifique o branchLen de forma recursiva para que, em vez de subtrair sempre a mesma quantidade, subtraia uma quantidade aleatória dentro de algum intervalo.
Se você implementar todas as idéias acima, você terá uma árvore bem mais realista.
Encontre ou invente um algoritmo para desenhar uma montanha fractal. Dica: um abordagem para esse problema usa triângulos novamente.
Escreva uma função recursiva para calcular a sequência de Fibonacci. Como o desempenho da função recursiva se compara com o de uma versão iterativa?
Implemente uma solução para a Torre de Hanoi usando três pilhas para manipular os discos.
Usando o módulo gráfico turtle, escreva um programa recursivo para exibir uma curva de Hilbert.
Usando o módulo gráfico turtle, escreva um programa recursivo para exibir um floco de neve Koch.
Escreva um programa para resolver o seguinte problema: você tem dois jarros: um de 4 litros e outro de 3 litros. Nenhum dos jarros tem marcações. Existe uma torneira que pode ser usada para encher os jarros com água. Como você pode obter exatamente dois litros de água no jarro de 4 litros?
Generalize o problema acima para que os parâmetros da sua solução incluam os tamanhos de cada jarro e a quantidade final de água a ser deixada no jarro maior.
Escreva um programa que resolva o seguinte problema: Três missionários e três canibais chegam a um rio e encontram um barco que transporta até duas pessoas. Todos devem atravessar o rio para continuar a viagem. No entanto, se o número de canibais for maior que o número de missionários em qualquer lado do rio, os missionários serão comidos. Encontre uma série de travessias que vão levar todos com segurança para o outro lado do rio.
Modifique o programa Torre de Hanoi usando o módulo gráfico turtle para animar o movimento dos discos. Dica: você pode criar várias tartarugas na forma de retângulos.
O triângulo de Pascal é um triângulo numérico com números dispostos em filas escalonadas de tal forma que

\[a_{nr} = {n! \over{r! (n-r)!}}\]

Essa equação é a equação de um coeficiente binomial. Você pode construir o triângulo de Pascal adicionando os dois números diagonalmente acima de um número no triângulo. Um exemplo do triângulo de Pascal é mostrado abaixo.
```
            1
         1     1
      1     2     1
   1     3     3     1
1     4     6     4     1
```
Escreva um programa que imprima o triângulo de Pascal. Seu programa deve aceitar um parâmetro que define quantas linhas do triângulo devem ser impressas.
Suponha que você é um cientista da computação/ladrão de arte que invadiu uma grande galeria de arte. Tudo o que você tem para levar sua arte roubada é a sua mochila que só consegue carregar \(W\) kilos, e para cada obra de arte você conhece seu valor e seu peso. Escreva uma função usando programação dinâmica para ajudá-lo a maximizar seu lucro. Aqui está um exemplo de problema para ajudar você a começar: Suponha que sua mochila pode carregar um peso total de 20. Você tem os 5 itens a seguir:
```
item  peso  valor
   1  2  3
   2  3  4
   3  4  8
   4  5  8
   5  9  10
```
Esse problema é chamado de problema de distância de edição de string e é bastante útil em muitas áreas de pesquisa. Suponha que você queira transformar a palavra “algorithm” na palavra “alligator”. Para cada letra que você pode copiar a letra de uma palavra para outra a um custo de 5, ou você pode remover a letra ao custo de 20 ou inserir uma letra a um custo de 20. O custo total para transformar uma palavra em outra é usado em programas de verificação ortográfica para fornecer sugestões de palavras. Use técnicas de programação dinâmica para desenvolver um algoritmo que lhe dá a menor distância de edição entre quaisquer duas palavras.

Next Section - 5. Ordenação e Busca