MAC 122 Princípios de Desenvolvimento de Algoritmos

		 Quarta lista de exercícios (turma do básico)

			 Entregar na aula de 04nov99.

			   Equipes de <= 2 alunos.

1. (5.7) Calcule a profundidade da recursão (número de chamadas recursivas
   encaixadas) do algoritmo de Euclides quando a entrada são os números de
   Fibonacci F(N) e F(N+1). Mostre as árvores de recursão para N=6.

2. (5.9) Escreva um programa recursivo que avalia expressões
   pós-fixas. Descreva o funcionamento do algoritmo e teste o mesmo com
   expressões interessantes.

3. (5.41) Escreva uma função recursiva que usa programação dinâmica para
   calcular os valores de P(N), dado por P(0)=0 e para N>=1

   P(N)=chão(N/2) + P(chão(N/2)) + P(teto(N/2))

   Desenhe o gráfico de N versus P(N) - N lg N/2, para N entre 0 e 1024,
   inclusive. 

4. Escreva um programa recursivo para listar todos os 2^N subconjuntos do
   conjunto {1,2,...,N}. Por exemplo, para N=3 os subconjuntos são vazio, 1,
   12, 123, 13, 2, 23, 3. Procure listar os conjuntos em ordem alfabética,
   como é feito no exemplo.

---

MAC 122 Princípios de Desenvolvimento de Algoritmos

---

e-mail: Imre Simon <is@ime.usp.br>

Last modified: Mon Oct 25 15:10:50 EDT 1999