LP BrunoKimura lista 8 ponteiros recursividade busca

Prévia do material em texto

Lista de Exercícios 8 (Ponteiros, Recursividade e Busca)
LP – Lógica de Programação, 2015
Prof. Bruno Kimura
Fontes utilizadas para elaboração deste documento:
http://www.joinville.udesc.br/portal/professores/adriano/materiais/ListaRevis_oPonteiros.html
http://www.decom.ufop.br/guillermo/BCC201/Listas/Lista2-BCC201-Prova3.pdf
http://www.ime.usp.br/~pf/algoritmos/aulas/bubi.html
http://homepages.dcc.ufmg.br/~olmo/exercicios_recursividade.pdf
Lista de exercício disponibilizadas pelo prof. Valério Rosset.
EXERCÍCIOS SOBRE PONTEIROS
1. Se i e j são variáveis inteiras e p e q são ponteiros para inteiros, quais das seguintes expressões abaixo são
ilegais e por que? 
a) p = &i; 
b) *q = &j; 
c) p = &*&i;
d) i = (*&)j;
e) i = *&*&j; 
f) q = &p; 
g) i = (*p)++ + *q; 
2. Se i é um ponteiro, explique a diferença entre as expressões 
a) i++; 
b) (*i)++; 
c) *(i++);
3. Seja o seguinte trecho de programa:
int i=3,j=5;
int *p, *q;
p = &i;
q = &j;
Qual é o valor das seguintes expressões ?
a) p == &i; 
b) *p - *q 
c) **&p
d) 3* - *p/(*q)+7
4. Assumindo que vet[] é um vetor do tipo double, quais das seguintes expressões referenciam o valor do
quinto elemento do vetor?
a) *(vet + 5) 
b) *(vet + 4) 
c) vet + 4
d) vet + 5
5. Considere a declaração: int mat[4], *p, x; 
Quais expressões são válidas e por que?
a) p = mat + 1;
b) p = mat++;
c) p = ++mat;
d) x = (*mat)++;
6. Seja vet um vetor de 4 elementos: TIPO vet[4]. Depois da declaração, vet está armazenado no endereço de
memória 4092 (ou seja, o endereço de vet[0]). Considere que a máquina usada uma variável do tipo char
ocupa 1 byte, do tipo short int ocupa 2 bytes, do tipo int ocupa 4 bytes, do tipo float bytes e do tipo double
ocupa 8 bytes.
7. Qual o valor de vet+1, vet+2 e vet+3 se:
a) vet for declarado como char?
b) vet for declarado como short int?
b) vet for declarado como int?
c) vet for declarado como float?
d) vet for declarado como double?
EXERCÍCIOS SOBRE FUNÇÕES RECURSIVAS
Implemente funções recursiva para:
8. Determinar o MDC (máximo divisor comum) entre dois números naturais x e y, baseando-se em uma das
regras abaixo. 
mdc (x,y) = x , se y = 0
mdc (x,y) = mdc (y, x%y) , se x > 0 
mdc (x,y) = x , se x = y 
mdc (x,y) = mdc (x-y, y) , se x > y 
mdc (x,y) = mdc (x, y-x) , se x < y
9. Encontrar o menor elemento em um vetor de inteiros. 
10. Encontrar o maior elemento em um vetor de inteiros. 
11. Calcular o somatório dos elementos de um vetor de inteiros.
12. Calcular a média dos elementos de um vetor de reais.
13. Imprimir todos os elementos de um vetor.
14. Inverter a ordem dos elementos de um vetor de inteiros.
15. Contar o número de ocorrências que um valor aparece em um vetor de inteiros.
16. Contar o número de ocorrências que caractere aparece em uma string.
17. Receber duas strings a e b, verificar se elas são iguais. Retornar 1 se forem iguais ou 0, caso contrário.
18. Receber dois valores inteiros x e y, calcular e retornar o resultado de x^y (x elevado a y) 
19. Imprimir a sequência de Fibonacci.
20. Receber um valor inteiro e o retorne invertido. Exemplo: se x = 123, a função deve retornar 321.
21. Receber um valor inteiro em base decimal e imprimir em base binária.
 
EXERCÍCIOS SOBRE FUNÇÕES DE BUSCA
22. Implemente uma função recursiva para a busca sequencial de um valor em um vetor de inteiros. Se o
valor for encontrado, a função deve retornar o respectivo índice do vetor; caso contrário, retorne -1. 
23. Considere as funções abaixo.
int buscabin1(int *x, int n, int k){ 
    int i, f, m; 
    i = 0; f = n­1; 
   while (i <= f) { 
           m = (i+f)/2; 
           if (x[m] == k) return m; 
           else if (k > x[m]) i=m+1; 
           else f=m­1; 
      } 
      return ­1; 
}
int buscabin2(int *x, int n, int k) { 
   int e, d, m; 
   e = ­1; d = n;  
   while (e < d­1) {  
      m = (e + d)/2;
      if (x[m] < k) e = m;
      else d = m; 
   }
   return d;
}
a) Discuta as variantes dos dois códigos e os diferentes valores de retorno.
b) Modifique a função buscabin2 para retornar o índice de k, quando encontrado.
c) Implemente versões recursiva para as duas variantes.
d) Modifique as versões recursivas de modo que k seja uma string e x um vetor de strings.