next up previous
Next: About this document ...

MAC-IME-USP CARLOS EDUARDO FERREIRA


SALA 297A TEL.: 3818 6140


E-MAIL cef@ime.usp.br


MONITOR: MARCIO C. CABRAL




MAC 122 - Princ�pios de Desenvolvimento de Algoritmos

Segundo semestre de 2000

Lista de exerc�cios--Recurs�o

``Para fazer uma fun��o recursiva
� preciso ter f�.''
Siang Wun Song

    1. Fa�a uma fun��o recursiva MaxMin que calcula o elemento m�ximo e o elemento m�nimo de um vetor com $n$ n�meros inteiros.
    2. Quantas compara��es (em fun��o de $n$) envolvendo elementos do vetor o seu algoritmo faz?

  2. Fa�a uma fun��o recursiva D�gito que recebe um n�mero inteiro $n$ e calcula a soma dos digitos de $n$. Exemplo: se $n=132$ ent�o D�gito$(n) = 6$.

    1. Fa�a uma fun��o recursiva que verifica se uma express�o de par�nteses � bem formada.

    2. Idem para uma express�o com par�nteses, colchetes (`[',`]') e chaves (`{',`}').

  4. Considere a fun��o abaixo: 
    double f(double x, double y)
{
  if (x >= y) 
     return ((x+y)/2); 
  return (f(f(x+2, y-1), f(x+1, y-2));
}
    Qual � o valor de $f(1,10)$? Como se poderia calcular $f(a,b)$ de maneira mais simples?

  5. A fun��o de Akermann � definida da seguinte maneira:

    \begin{displaymath} A(m,n) := \left\{ \begin{array}{ll} n+1 & \mbox{se $m=0$,} ... ... A(m-1,A(m,n-1)) & \mbox{se $m, n >0$.} \end{array} \right. \end{displaymath}

    Escreva uma fun��o recursiva que recebe inteiros n�o negativos $m$ e $n$ e devolve $A(m,n)$.

  6. Simule a execu��o do programa abaixo: 
    #include <stdio.h> 
int fusc(int n)
{
  if (n <= 1) return (1);
  if (n % 2 == 0) 
     return( fusc(n / 2) );
  return( fusc((n-1)/2) + fusc((n+1)/2) );
}

int main()
{
  int m = 7;
  printf("Fusc = %d\n", fusc(m));
}

  7. Considere a seguinte fun��o: 
    void misterio (int A[], int inic, int fim)
{
  int aux; 
  while (A[fim] % 2 == 0 && inic < fim)
     fim --; 
  while (A[inic] % 2 == 1 && inic < fim) 
     inic++;
  if (inic < fim){
    aux = A[inic];
    A[inic] = A[fim];
    A[fim] = aux;
    misterio(A, inic, fim);
  }
}
    1. Simule a fun��o Mist�rio para
      $0$ $1$ $2$ $3$ $4$ $5$ $6$ $7$ $8$  
      $A=$ 8 10 3 6 5 2 9 1 4 Inicio$=0$ e Fim $=8$.
    2. O que faz a fun��o Mist�rio? Quantas compara��es envolvendo elementos do vetor $A$ s�o feitas? Escreva um algoritmo que faz a mesma coisa com um n�mero menor de compara��es.

  8. Simule a seguinte fun��o recursiva para $N=6$: 
    int zzz(int n)
{ 
  int aux; 
  if (n <= 2)
    return(1);
  n--; 
  aux = zzz(n);
  n--;
  return (aux + zzz(n));
}

  9. Escreva uma fun��o recursiva Tab$(N,X,Y)$ que recebe como par�metro um inteiro n�o negativo $N$ e calucula um par de inteiros $(X,Y)$, onde $X$ e $Y$ s�o as coordenadas de $N$ na tabela abaixo:
    $0$ $1$ $2$ $3$ $4$ $\ldots$ $Y$
    0 0 2 5 9 14    
    1 1 4 8 13      
    2 3 7 12        
    3 6 11          
    4 10            
    ...              
    $X$             $N$

  10. Suponha que temos de calcular o produto de matrizes

    \begin{displaymath}M_1 \times M_2 \times \ldots \times M_n, \end{displaymath}

    onde cada $M_i$ � uma matriz com $r_i$ linhas e $r_{i+1}$ colunas. (Portanto, $r_1,\ldots,r_{n+1}$ descrevem as dimens�es das matrizes.) Suponha ainda que o produto de qualquer par de matrizes ser� calculado pelo algoritmo usual; assim o produto de uma matriz $p \times q$ por uma matriz $q \times r$ requer $p \times q \times r$ opera��es de multiplica��o entre n�meros. A ordem em que a multiplica��o de tr�s ou mais matrizes � executada pode afetar sensivelmente o n�mero total de multiplica��es. Por exemplo, se $n=4$ e $(r_1,\ldots,r_5)=(10,20, 50, 1, 100)$ ent�o o c�lculo da express�o $M_1 \times (M_2 \times (M_3 \times M_4))$ requer 125000 multiplica��es enquanto que o c�lculo da express�o $M_1 \times (M_2 \times M_3)) \times M_4$ requer 2200 multiplica��es. Seja $m_{i,j}$ o n�mero m�nimo de multiplica��es necess�rias para calcular $M_i \times \cdots \times M_j$. Temos que

    \begin{displaymath}m_{i,j} = \left\{ \begin{array}{ll} 0 & \mbox{se $i=j$} \\ ... ...1} \times r_{j+1}\} & \mbox{ se $i < j$.} \end{array}\right. \end{displaymath}

    Escreva uma fun��o recursiva que recebe $n$ e a seq��ncia $(r_1,\ldots,r_{n+1})$ e calcula $m_{1,n}$.

  11. Escreva uma fun��o que dado $n$ imprime todas as permuta��es dos n�meros inteiros $1,\ldots,n$. Escreva duas vers�es, uma iterativa e uma recursiva. (Sugest�o: O conjunto das permuta��es dos inteiros $1,\ldots,n$ pode ser obtida atrav�s do conjunto das permuta��es dos inteiros de $1, \ldots, n-1$ inserindo-se $n$ em cada poss�vel posi��o de cada permuta��o.)

  12. Escreva uma fun��o que dados dois inteiros positivos $n$ e $k$ imprima todas as combina��es de $1,\ldots,n$ em grupos de tamanho $k$. Escreva duas vers�es, uma iterativa e outra recursiva.

  13. Escreva um programa para imprimir em ordem lexicogr�fica todos os subconjuntos do conjunto $\{1,\ldots,n\}$. Para $n=4$ o resultado deve ser:
    $ \emptyset \ \{1\} \ \{1,2\} \ \{1,2,3\} \ \{1,2,3,4\} \ \{1,2,4\} \ \{1,3\} \ \{1,3,4\}$
    $\{1,4\}\ \{2\} \ \{2,3\}\ \{2,3,4\}\ \{2,4\}\ \{3\} \ \{3,4\} \ \{4\}. $

  14. A fun��o abaixo calcula o maior divisor comum dos inteiros positivos $m$ e $n$. Escreva uma fun��o recursiva equivalente. 
    int Euclides (int m, int n)
{
  int r;
  do{
     r = m % n;
     m = n;
     n = r;
  }
  while (r != 0);
  return(m);
}

next up previous
Next: About this document ...
Carlos Eduardo Ferreira
2000-10-02