MATA40 T03 2017 2 Aula02 RevisaoLinguagemC part2

Prévia do material em texto

MATA40 – Estrutura de dados e 
Algoritmos I
Aula 2 –Revisão Linguagem C
Turma 03
Semestre: 2017.2
Prof. Igo Amauri dos S. Luz
Abstração Procedural
• Na programação estruturada, os algoritmos são
desenvolvidos em programas através da abstração
procedural e refinamento gradual.
• A abstração procedural permite que o programador se
preocupe com a interface entre a função e o que ela
calcula.
• Pode-se ignorar os detalhes de como o cálculo é executado.
2
calcula_media(valorA, valorB);
Abstração Procedural
• Com a abstração procedural, programadores exploraram
a disponibilidade de funções predefinidas.
• Funções e bibliotecas reusáveis.
• Por exemplo, funções matemáticas: sin, cos, sqrt, etc.
• Contribuem com o desempenho no desenvolvimento dos
programas.
3
Abstração Procedural
• No refinamento gradual, o programador desenvolve o
algoritmo da sua forma mais geral para uma forma mais
específica.
• A função geral do programa é dividida em funções mais
primitivas.
• Estrutura-se através de subrotinas.
• Quebra um problema complexo em partes simples.
4
Função Geral
função_a
função_c
função_b
Abstração Procedural
• Funções são blocos de construção e o local onde toda a
atividade do programa ocorre.
• Forma geral em C:
• especificador_tipo determina o tipo de valor de retorno da
função;
• lista_de_parâmetros representa a lista de variáveis e seus
tipos que recebem seus valores quando a função é
chamada. 5
especificador_tipo nome_da_função (lista_de_parâmetros)
{
corpo_da_função
}
Abstração Procedural
• Funções são blocos de construção e o local onde toda a
atividade do programa ocorre.
• Exemplo de função em C:
6
int sqr(int x)
{
x = x*x;
return x;
}
void imprimir_mensagem(int x, int y)
{
int produto;
produto = x*y;
printf(“O resultado da multiplicação é: %d”, x);
}
Abstração Procedural
• Exemplo de refinamento gradual
• Algoritmo de ordenação
7
Interface da 
rotina de 
ordenação
Ordena(lista_elementos, tamanho);
Abstração Procedural
• Exemplo de refinamento gradual
• Algoritmo de ordenação
8
Como 
refinar?
void ordena(Type list, int len) {
for (int i = 0; i < len; i++)
for (int j = i+1; j < len; j++)
if (list[j] < list[i]) {
Type t = list[j];
list[j] = list[i];
list[i] = t;
}
}
Abstração Procedural
• Exemplo de refinamento gradual
• Algoritmo de ordenação
9
void ordena(Type list, int len) {
for (int i = 0; i < len; i++)
for (int j = i+1; j < len; j++)
if (list[j] < list[i]) {
trocar(list, i, j)
}
}
void troca(Type list, int i, int j) {
Type t = list[j];
list[j] = list[i];
list[i] = t;
}
Ponteiros
• A memória de um computador é, normalmente, uma
sequência de bytes.
• 1 byte = 8 bits = 256 possíveis valores
• Cada elemento ocupa um determinado número de bytes
consecutivos na memória do computador.
• char – ocupa 1 byte
• int – ocupa 4 bytes
• double – ocupa 8 bytes
• Pode-se utilizar a função sizeof para identificar o número de
bytes de um determinado elemento.
10
Ponteiros
11
#include <stdio.h> 
#include <stdlib.h>
void main(void){
int variavel_inteiro;
char variavel_char;
double variavel_duble;
printf("Tamanho do char: %d\n", sizeof(variavel_char));
printf("Tamanho do int: %d\n", sizeof(variavel_inteiro));
printf("Tamanho do double: %d\n", sizeof(variavel_duble));
}
Ponteiros
• Cada elemento na memória possui um endereço.
• Cada byte possui um endereço.
• Na maioria das máquinas, o endereço de um objeto é o
endereço do primeiro byte.
• O endereço de um elemento pode ser obtido pelo
operador &.
12
Ponteiros
13
#include <stdio.h> 
#include <stdlib.h>
void main(void){
int variavel_inteiro;
char variavel_char;
double variavel_duble;
int array_int[3];
//sizeof(variavel_inteiro);
printf("Tamanho do char: %d\n", sizeof(variavel_char));
printf("Tamanho do int: %d\n", sizeof(variavel_inteiro));
printf("Tamanho do double: %d\n\n\n", sizeof(variavel_duble));
printf("Endereco de variavel_char: %d\n", &variavel_char);
printf("Endereco de variavel_inteiro: %d\n", &variavel_inteiro);
printf("Endereco de variavel_duble: %d\n", &variavel_duble);
printf("Endereco de array_int[0]: %d\n", &array_int[0]);
printf("Endereco de array_int[1]: %d\n", &array_int[1]);
printf("Endereco de array_int[2]: %d\n", &array_int[2]);
}
Ponteiros
• Da mesma maneira que existem em C variáveis do tipo
char, int e float, existem variáveis do tipo ponteiro.
• Variáveis do tipo ponteiro armazenam endereços de
memória.
• Quando declaramos uma variável do tipo ponteiro,
devemos informar também que tipo de informação
estará contida no endereço que o ponteiro irá armazenar.
• Por exemplo, um ponteiro int aponta para um inteiro, isto é,
é capaz de guardar o endereço de um inteiro.
14
Ponteiros
• A forma de declaração de uma variável ponteiro é:
tipo *nome_variável
• tipo é o tipo do dado que estará contido no endereço que o
ponteiro irá armazenar.
• Por exemplo:
float *p; // p é um ponteiro de float
• Ou seja, p apontará para uma região de memória que
armazena um valor float.
15
Ponteiros
• Existem dois operadores especiais para trabalhar com
ponteiros. São eles * e &.
• & - endereço de
• Exemplo:
int a;
int *p;
p = &a; // p armazenará o endereço de memória da
variável inteira a.
16
Ponteiros
• Existem dois operadores especiais para trabalhar com
ponteiros. São eles * e &.
• * - conteúdo do endereço armazenado em
• Exemplo:
int a;
int *p;
p = &a;
*p = 10; // O valor 10 será armazenado em a.
17
Ponteiros
• Observação:
• Quando * é usado na declaração de uma variável ponteiro,
ele simplesmente indica que a variável é do tipo ponteiro
de um tipo.
• Não significa conteúdo do endereço armazenado no
ponteiro.
18
Ponteiros
• Inicialização
• Se quisermos indicar que um ponteiro não aponta para
nenhuma posição de memória, podemos atribuir a ele
um “valor nulo”:
• p = NULL;
• Essa informação pode ser útil em expressões
condicionais:
19
if (p == NULL)
{
…
}
Ponteiros
• Exemplo
20
#include <stdio.h>
void main( )
{ 
int v1, v2, *p, *q;
v1 = 3;
v2 = 12;
p = &v1; /* p recebe o endereço de memória 
da variável v1*/
q = p; /* copia o endereço guardado em
p para q */ 
*q = 44; /* altera o valor armazenado no
endereço apontado por q */
printf(“%d, %d\n”, v1, v2);
}
Ponteiros
• Exemplo
21
#include <stdio.h>
void main ()
{
int num, valor; 
int *p;
num = 55;
p = &num; /* Pega o endereço de num */
valor = *p; /* Valor é igualado a num de uma maneira 
indireta */
printf ("\n\n%d\n",valor);
printf ("Endereço para onde o ponteiro aponta: %p\n",p);
printf ("Valor da variável apontada: %d\n",*p);
}
Ponteiros
• Considere as seguintes declarações:
• int a, b, c, *p, *q, *f;
• O que acontece na memória abaixo após cada uma das 
seguintes instruções:
• b = 5; 
• p = &b;
• f = &a;
• a = 2;
• c = *f;
• q = f; 
22
28FF10
28FF14
28FF18
28FF1C
28FF20
28FF24
28FF28
28FF2C
28FF30
a
b
c
q
p
f
Ponteiros
• Considere as seguintes declarações:
• int a, b, c, *p, *q, *f;
• O que acontece na memória abaixo após cada uma das 
seguintes instruções:
• b = 5; 
• p = &b;
• f = &a;
• a = 2;
• c = *f;
• q = f; 
23
28FF10
28FF14
28FF18
28FF1C
28FF20
28FF24
28FF28
28FF2C
28FF30
a
b
c
q
p
f
5
Ponteiros
• Considere as seguintes declarações:
• int a, b, c, *p, *q, *f;
• O que acontece na memória abaixo após cada uma dasseguintes instruções:
• b = 5; 
• p = &b;
• f = &a;
• a = 2;
• c = *f;
• q = f; 
24
28FF10
28FF14
28FF18
28FF1C
28FF20
28FF24
28FF28
28FF2C
28FF30
a
b
c
q
p
f
5
2FF14
Ponteiros
• Considere as seguintes declarações:
• int a, b, c, *p, *q, *f;
• O que acontece na memória abaixo após cada uma das 
seguintes instruções:
• b = 5; 
• p = &b;
• f = &a;
• a = 2;
• c = *f;
• q = f; 
25
28FF10
28FF14
28FF18
28FF1C
28FF20
28FF24
28FF28
28FF2C
28FF30
a
b
c
q
p
f
5
2FF14
2FF10
Ponteiros
• Considere as seguintes declarações:
• int a, b, c, *p, *q, *f;
• O que acontece na memória abaixo após cada uma das 
seguintes instruções:
• b = 5; 
• p = &b;
• f = &a;
• a = 2;
• c = *f;
• q = f; 
26
28FF10
28FF14
28FF18
28FF1C
28FF20
28FF24
28FF28
28FF2C
28FF30
a
b
c
q
p
f
5
2FF14
2FF10
2
Ponteiros
• Considere as seguintes declarações:
• int a, b, c, *p, *q, *f;
• O que acontece na memória abaixo após cada uma das 
seguintes instruções:
• b = 5; 
• p = &b;
• f = &a;
• a = 2;
• c = *f;
• q = f; 
27
28FF10
28FF14
28FF18
28FF1C
28FF20
28FF24
28FF28
28FF2C
28FF30
a
b
c
q
p
f
5
28FF14
28FF10
2
2
Ponteiros
• Considere as seguintes declarações:
• int a, b, c, *p, *q, *f;
• O que acontece na memória abaixo após cada uma das 
seguintes instruções:
• b = 5; 
• p = &b;
• f = &a;
• a = 2;
• c = *f;
• q = f; 
28
28FF10
28FF14
28FF18
28FF1C
28FF20
28FF24
28FF28
28FF2C
28FF30
a
b
c
q
p
f
5
28FF14
28FF10
2
2
28FF10
Ponteiros
• Aritmética de ponteiros
• Considere os seguintes ponteiros:
• int *p, *q;
• Atribuição
q = p; /* q recebe o mesmo endereço que p 
armazena*/
• Incremento
p++; /* p passa a apontar para o próximo
inteiro. */
• Decremento
p--; /* semelhante ao incremento */ 29
Ponteiros
• Aritmética de ponteiros
• Operações com ponteiros e não de operações com o
conteúdo das variáveis para as quais eles apontam.
• Por exemplo, para incrementar o conteúdo da variável
apontada pelo ponteiro p, faz-se:
• (*p)++;
30
Ponteiros
• Aritmética de ponteiros
• Soma
p = p + 3; /* p aponta para o o endereço do
3º inteiro adiante. */
• Subtração
p = p – 3; /* Semelhante a soma*/
31
Ponteiros
• Quando declaramos um vetor A de 5 números inteiros o
compilador reserva memória suficiente para armazenar
5 inteiros consecutivos e armazena o endereço da
primeira posição reservada em A.
• Logo, A é um ponteiro.
• A[2] *(A + 2)
32
Ponteiros
• Vetores são ponteiros estáticos. Isto significa, que não é
possível alterar o endereço armazenado pelo "nome do
vetor".
• As instruções abaixo não são válidas:
int A[5];
int *p, i;
p = &i;
A = A + 2; /* ERRADO: Não podemos alterar o 
endereço armazenado por A */
A++; /* ERRADO: Não podemos alterar o 
endereço armazenado por A */
A = p; /* ERRADO: Não podemos alterar o 
endereço armazenado por A */
33
Ponteiros
• Exemplo
#include <stdio.h>
void main ()
{
int V[5], i, *p;
for(i = 0; i < 5; i++)
{
V[i] = i + 1;
}
p = V; /*p armazena o endereço do primeiro elemento 
do vetor.*/
printf("O quinto elemento do vetor e: %d.\n", p[4]);
// p[4] é o mesmo que *(p + 4)
}
34
Ponteiros
• Exercício
• Analise o código e identifique o que será escrito na tela.
#include <stdio.h>
void main()
{
int y, *p;
int v[5]={2,7,1,4,5};
p = v;
y = *p;
p = p + y;
printf("%d \n", *p);
(*p)++;
y--;
(*p) = (*p) + y;
printf("%d \n", *p);
}
35
Ponteiros
• Exercício
• Preencha a memória a seguir com os dados apropriados, como
determinados pelas declarações e instruções abaixo. Alguns
valores já foram previamente armazenados na memória. Os
endereços de memória são fictícios.
int *p, *q, *r, *s, *t, *z, a, b, c, d, e, f;
*p = d * 2;
q = &b;
s = &d;
r = &a;
b = *p + *s;
t = p;
*r = *t + 15;
z = &e;
*z = *s * 2;
f = *r + *q + *t + *s;
Memória
10500 10532 p
10504 q
10508 r
10512 s
10516 t
10520 z
10524 a
10528 b
10532 c
10536 15 d
10540 e
10544 f
36
Recursividade
• A Recursividade auxilia na resolução de problemas
quando o mesmo é grande.
• A partir do problema maior, elabora-se uma solução menor
do problema;
• Relaciona com o problema maior;
• Resolve o problema menor;
• Volta-se ao problema inicial.
37
Recursividade
• Um objeto é dito recursivo se ele consistir parcialmente
ou for definido em termos de si mesmo.
• Uma função recursiva é uma função que faz uma
chamada a si mesma.
38
Recursividade
• Recursão Direta e Indireta
• Se uma função A contiver uma chamada explícita a si
mesma, essa função é dita diretamente recursiva.
• Se uma função A contiver uma chamada a uma função B,
que por sua vez contenha uma chamada a função A, a
função A é dita indiretamente recursiva.
A  A
A  B
B  A
39
Recursividade
• Os problemas recursivos são formados por:
• Um caso base;
• E um caso recursivo.
• O caso base interrompe a recursão.
• O caso recursivo deve caminhar para o caso base.
• Omitir o caso base nas implementações recursivas é um
erro muito comum.
• Quando isso ocorre, a função nunca retornará quando
chamada.
40
Recursividade
• Exemplo: Fatorial de um número.
• O fatorial de um número n é o produto de todos os 
números inteiros entre 1 e n.
1! = 1
41
Recursividade
• Exemplo: Fatorial de um número.
• O fatorial de um número n é o produto de todos os 
números inteiros entre 1 e n.
1! = 1
2! = 2 * 1
42
Recursividade
• Exemplo: Fatorial de um número.
• O fatorial de um número n é o produto de todos os 
números inteiros entre 1 e n.
1! = 1
2! = 2 * 1
3! = 3 * 2 *1
43
Recursividade
• Exemplo: Fatorial de um número.
• O fatorial de um número n é o produto de todos os 
números inteiros entre 1 e n.
1! = 1
2! = 2 * 1
3! = 3 * 2 *1
4! = 4 * 3 * 2 * 1
44
Recursividade
• Exemplo: Fatorial de um número.
• O fatorial de um número n é o produto de todos os 
números inteiros entre 1 e n.
1! = 1
2! = 2 * 1
3! = 3 * 2 *1
4! = 4 * 3 * 2 * 1
5! = 5 * 4 * 3 * 2 * 1
45
Recursividade
• Exemplo: Fatorial de um número.
• O fatorial de um número n é o produto de todos os 
números inteiros entre 1 e n.
1! = 1
2! = 2 * 1
3! = 3 * 2 *1
4! = 4 * 3 * 2 * 1
5! = 5 * 4 * 3 * 2 * 1
5!
46
Recursividade
• Exemplo: Fatorial de um número.
• O fatorial de um número n é o produto de todos os 
números inteiros entre 1 e n.
1! = 1
2! = 2 * 1
3! = 3 * 2 *1
4! = 4 * 3 * 2 * 1
5! = 5 * 4 * 3 * 2 * 1
5!
5 * 4!
47
Recursividade
• Exemplo: Fatorial de um número.
• O fatorial de um número n é o produto de todos os 
números inteiros entre 1 e n.
1! = 1
2! = 2 * 1
3! = 3 * 2 *1
4! = 4 * 3 * 2 * 1
5! = 5 * 4 * 3 * 2 * 1
5!
5 * 4!
4 * 3!
48
Recursividade
• Exemplo: Fatorial de um número.
• O fatorial de um número n é o produto de todos os 
números inteiros entre 1 e n.
1! = 1
2! = 2 * 1
3! = 3 * 2 *1
4! = 4 * 3 * 2 * 1
5! = 5 * 4 * 3 * 2 * 1
5!
5 * 4!
4 * 3!
3 * 2!
49
Recursividade
• Exemplo: Fatorial de um número.
• O fatorial de um número n é o produto de todos os 
números inteiros entre 1 e n.
1! = 1
2! = 2 * 1
3! = 3 * 2 *1
4! = 4 * 3 * 2 * 1
5! = 5 * 4 * 3 * 2 * 1
5!
5* 4!
4 * 3!
3 * 2!
2 * 1! 50
Recursividade
• Exemplo: Fatorial de um número.
• O fatorial de um número n é o produto de todos os 
números inteiros entre 1 e n.
1! = 1
2! = 2 * 1
3! = 3 * 2 *1
4! = 4 * 3 * 2 * 1
5! = 5 * 4 * 3 * 2 * 1
5!
5 * 4!
4 * 3!
3 * 2!
2 * 1!
1
51
Recursividade
• Função recursiva:
• Dado um problema, subdivide-se este problema em
problemas menores (mais simples) e chama a mesma
função para resolvê-lo.
• Caso recursivo.
• Para de subdividir quando chega em um problema trivial.
• Caso base.
52
Recursividade
• Exemplo fatorial:
53
5!
5 * 4!
4 * 3!
3 * 2!
2 * 1!
1
Recursividade
• Exemplo fatorial:
54
5!
5 * 4!
4 * 3!
3 * 2!
2 * 1!
1
1
Recursividade
• Exemplo fatorial:
55
5!
5 * 4!
4 * 3!
3 * 2!
2 * 1!
1
2 * 1 = 2
1
Recursividade
• Exemplo fatorial:
56
5!
5 * 4!
4 * 3!
3 * 2!
2 * 1!
1
2 * 1 = 2
3 * 2 = 6
1
Recursividade
• Exemplo fatorial:
57
5!
5 * 4!
4 * 3!
3 * 2!
2 * 1!
1
2 * 1 = 2
3 * 2 = 6
4 * 6 = 24
1
Recursividade
• Exemplo fatorial:
58
5!
5 * 4!
4 * 3!
3 * 2!
2 * 1!
1
2 * 1 = 2
3 * 2 = 6
4 * 6 = 24
5 * 24 = 120
1
Valor Final = 120
Recursividade
• Implementação em C
59
int fatorial (int n)
{
int resultado;
if(n = = 1){
return 1;
}
else{
resultado = fatorial(n-1)*n
return resultado;
}
}
Recursividade
• Chamadas recursivas
60
fat = fatorial(5);
Recursividade
• Chamadas recursivas
61
fat = fatorial(5);
return 5 * fatorial(4);
Recursividade
• Chamadas recursivas
62
fat = fatorial(5);
return 5 * fatorial(4);
return 4 * fatorial(3);
Recursividade
• Chamadas recursivas
63
fat = fatorial(5);
return 5 * fatorial(4);
return 4 * fatorial(3);
return 3 * fatorial(2);
Recursividade
• Chamadas recursivas
64
fat = fatorial(5);
return 5 * fatorial(4);
return 4 * fatorial(3);
return 3 * fatorial(2);
return 2 * fatorial(1);
Recursividade
• Chamadas recursivas
65
fat = fatorial(5);
return 5 * fatorial(4);
return 4 * fatorial(3);
return 3 * fatorial(2);
return 2 * fatorial(1);
return 1;
Recursividade
• Chamadas recursivas
66
fat = fatorial(5);
return 5 * fatorial(4);
return 4 * fatorial(3);
return 3 * fatorial(2);
return 2 * 1;
Recursividade
• Chamadas recursivas
67
fat = fatorial(5);
return 5 * fatorial(4);
return 4 * fatorial(3);
return 3 * 2;
Recursividade
• Chamadas recursivas
68
fat = fatorial(5);
return 5 * fatorial(4);
return 4 * 6;
Recursividade
• Chamadas recursivas
69
fat = fatorial(5);
return 5 * 24;
Recursividade
• Chamadas recursivas
70
fat = 120;
Exercícios
1. Escreva uma função que recebe como parâmetro um inteiro
positivo n e retorna a soma de todos os números inteiros entre 1
e n.
• n = 1 → Soma(1) = 1
• n = 2 → Soma(2) = 2 + Soma(1)
• n = 3 → Soma(3) = 3 + Soma(2)
2. Utilizando a recursão, escreva um programa que exiba n
elementos da sequência de Fibonacci.
3. Escreva um programa que contenha uma função recursiva que
calcule be, em que b e e são números inteiros positivos.
4. O produto entre dois números inteiros sempre pode ser calculado
utilizando-se apenas o operador de adição. Ou seja: x * y = x + x +
...+ x (y vezes). Escreva uma função recursiva para o cálculo do
produto de dois números, usando apenas o operador de soma.
5. Escreva um programa que contenha uma função recursiva que
receba um número natural n, e devolva a soma dos n primeiros
números naturais ímpares.
71