Baixe o app para aproveitar ainda mais
Prévia do material em texto
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 1/45 Recursão – Lista de exercícios Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 2/45 Solução lista de exercícios ● Vamos tentar, antes de mais nada, estabelecer como seria a definição recursiva do problema ● Depois usaremos na implementação Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 3/45 Exercício 3 ● 3) Implemente uma função recursiva que, dados dois números inteiros x e n, calcula o valor de xn. ● Caso base? Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 4/45 Exercício 3 ● 3) Implemente uma função recursiva que, dados dois números inteiros x e n, calcula o valor de xn. ● Caso base? x0 = 1 ● Passo da recursão: Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 5/45 Exercício 3 ● 3) Implemente uma função recursiva que, dados dois números inteiros x e n, calcula o valor de xn. ● Caso base? x0 = 1 ● Passo da recursão: xn = x * xn-1 Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 6/45 Exercício 3 int pot(int b, int p) { if ( p == 0 ) return 1; return ( b * pot(b, p1)); } Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 7/45 Exercício 7 ● 7) Usando recursividade, calcule a soma de todos os valores de um array de reais. ● Caso base? Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 8/45 Exercício 7 ● 7) Usando recursividade, calcule a soma de todos os valores de um array de reais. ● Caso base? Tamanho do array = 0. Soma é 0. Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 9/45 Exercício 7 ● 7) Usando recursividade, calcule a soma de todos os valores de um array de reais. ● Caso base? Tamanho do array = 0. Soma é 0. ● Passo da recursão: v Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 10/45 Exercício 7 ● 7) Usando recursividade, calcule a soma de todos os valores de um array de reais. ● Caso base? Tamanho do array = 0. Soma é 0. ● Passo da recursão: v v[n-1] + soma do restante do array. Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 11/45 Exercício 7 int soma_a(int v[], int n) { if ( n == 0 ) return 0; return v[n1] + soma(v, n1); } Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 12/45 Exercício 1 ● 1) Dado um array de inteiros e o seu número de elementos, inverta a posição dos seus elementos. ● Caso base? Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 13/45 Exercício 1 ● 1) Dado um array de inteiros e o seu número de elementos, inverta a posição dos seus elementos. ● Caso base? Tamanho do array menor ou igual a 1 Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 14/45 Exercício 1 ● 1) Dado um array de inteiros e o seu número de elementos, inverta a posição dos seus elementos. ● Caso base? Tamanho do array menor ou igual a 1 ● Passo da recursão: Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 15/45 Exercício 1 ● 1) Dado um array de inteiros e o seu número de elementos, inverta a posição dos seus elementos. ● Caso base? Tamanho do array menor ou igual a 1 ● Passo da recursão: ● Troca 1o. e último elementos e inverte resto do array. Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 16/45 Exercício 1 void inverte(int v[], int esq, int dir) { int t; if (esq >= dir) return; t = v[esq]; v[esq] = v[dir]; v[dir] = t; inverte(v, esq+1, dir 1); } Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 17/45 Exercício 9 ● 9) Escreva uma função recursiva que determine quantas vezes um dígito K ocorre em um número natural N. Por exemplo, o dígito 2 ocorre 3 vezes em 762021192. ● Caso base? Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 18/45 Exercício 9 ● 9) Escreva uma função recursiva que determine quantas vezes um dígito K ocorre em um número natural N. Por exemplo, o dígito 2 ocorre 3 vezes em 762021192. ● Caso base? Quando todos os digitos já foram examinados, ou seja, N = 0 Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 19/45 Exercício 9 ● 9) Escreva uma função recursiva que determine quantas vezes um dígito K ocorre em um número natural N. Por exemplo, o dígito 2 ocorre 3 vezes em 762021192. ● Caso base? Quando todos os digitos já foram examinados, ou seja, N = 0 ● Passo da recursão: n4n3n2n1n0 Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 20/45 Exercício 9 ● 9) Escreva uma função recursiva que determine quantas vezes um dígito K ocorre em um número natural N. Por exemplo, o dígito 2 ocorre 3 vezes em 762021192. ● Caso base? Quando todos os digitos já foram examinados, ou seja, N = 0 ● Passo da recursão: n4n3n2n1n0 (0 ou 1) + número de ocorrências em N / 10 (n4n3n2n1) Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 21/45 Exercício 9 int conta_dig(int N, int K) { if ( N == 0 ) return 0; return conta_dig( N / 10 , K) + ( N % 10 == K ); } Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 22/45 Exercício 4 ● 4) Um problema típico em ciência da computação consiste em converter um número da sua forma decimal para a forma binária. ● Caso base? Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 23/45 Exercício 4 ● 4) Um problema típico em ciência da computação consiste em converter um número da sua forma decimal para a forma binária. ● Caso base? Quando o número já foi todo transformado em binário. Ou seja: x = 0 ● Passo da recursão: Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 24/45 Exercício 4 ● 4) Um problema típico em ciência da computação consiste em converter um número da sua forma decimal para a forma binária. ● Caso base? Quando o número já foi todo transformado em binário. Ou seja: x = 0 ● Passo da recursão: Saber como x/2 é convertido. Depois, adicionar um dígito (o ou 1) relativo a x. Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 25/45 Exercício 4 void print_bin(int x) { if ( x == 0 ) return; print_bin(x / 2); printf("%d", x % 2); } Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 26/45 Exercício 4 void print_bin(int x) { if ( x == 0 ) return; print_bin(x / 2); printf("%d", x % 2); } void print_bin(int x) { if ( x == 0 ) { printf("0"); return; } print_bin(x / 2); printf("%d", x % 2); } Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 27/45 Exercício 5 ● 5) O máximo divisor comum (MDC) de dois números inteiros x e y pode ser calculado usando-se uma definição recursiva: ● MDC(x, y) = MDC(x − y, y), se x > y ● MDC(x,y) = MDC(y,x) ● MDC(x,x) = x ● Caso base? Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 28/45 Exercício 5 ● 5) O máximo divisor comum (MDC) de dois números inteiros x e y pode ser calculado usando-se uma definição recursiva: ● MDC(x, y) = MDC(x − y, y), se x > y ● MDC(x,y) = MDC(y,x) ● MDC(x,x) = x ● Caso base? x == y Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 29/45 Exercício 5 ● 5) O máximo divisor comum (MDC) de dois números inteiros x e y pode ser calculado usando- se uma definição recursiva: ● MDC(x, y) = MDC(x − y, y), se x > y ● MDC(x,y) = MDC(y,x) ● MDC(x,x) = x ● Caso base? x == y ● Passo da recursão? Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 30/45 Exercício 5 ● 5) O máximo divisor comum (MDC) de dois números inteiros x e y pode ser calculado usando-se uma definição recursiva: ● MDC(x, y) = MDC(x − y, y), se x > y ● MDC(x,y) = MDC(y,x) ● MDC(x,x) = x ● Caso base? x == y ● Passo da recursão? Os dois outros casos acima. O problema é definido recursivamente. Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP31/45 Exercício 5 int mdc(int p, int q) { if ( p == q ) return p; if ( p < q ) return mdc(q, p); return mdc(p q, q); } Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 32/45 Exercício 6 ● 6) Pode-se calcular o resto da divisão, MOD, de x por y, dois números inteiros positivos, usando-se a seguinte definição: ● MOD(x,y) = MOD(x - y, y) se x > y ● MOD(x,y) = x se x < y ● MOD(x,y) = 0 se x = y ● Caso base? Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 33/45 Exercício 6 ● 6) Pode-se calcular o resto da divisão, MOD, de x por y, dois números inteiros positivos, usando-se a seguinte definição: ● MOD(x,y) = MOD(x - y, y) se x > y ● MOD(x,y) = x se x < y ● MOD(x,y) = 0 se x = y ● Caso base? São dois: x < y ou x = y Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 34/45 Exercício 6 ● 6) Pode-se calcular o resto da divisão, MOD, de x por y, dois números inteiros positivos, usando-se a seguinte definição: ● MOD(x,y) = MOD(x - y, y) se x > y ● MOD(x,y) = x se x < y ● MOD(x,y) = 0 se x = y ● Caso base? São dois: x < y ou x = y ● Passo da recursão: Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 35/45 Exercício 6 ● 6) Pode-se calcular o resto da divisão, MOD, de x por y, dois números inteiros positivos, usando-se a seguinte definição: ● MOD(x,y) = MOD(x - y, y) se x > y ● MOD(x,y) = x se x < y ● MOD(x,y) = 0 se x = y ● Caso base? São dois: x < y ou x = y ● Passo da recursão: MOD(x - y, y) se x > y Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 36/45 Exercício 2a ● 2) Escreva as funções recursivas que unem dois (arrays), sem elementos repetidos, classificadas considerando que as duas listas não têm elementos em comum ● Caso base? Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 37/45 Exercício 2a ● 2) Escreva as funções recursivas que unem dois (arrays), sem elementos repetidos, classificadas considerando que as duas listas não têm elementos em comum ● Caso base? Quando ambos os arrays têm tamanho 0 ● Passo da indução: Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 38/45 Exercício 2a ● 2) Escreva as funções recursivas que unem dois (arrays), sem elementos repetidos, classificadas considerando que as duas listas não têm elementos em comum ● Caso base? Quando ambos os arrays têm tamanho 0 ● Passo da indução: Menor deles Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 39/45 Exercício 2a ● 2) Escreva as funções recursivas que unem dois (arrays), sem elementos repetidos, classificadas considerando que as duas listas não têm elementos em comum ● Caso base? Quando ambos os arrays têm tamanho 0 ● Passo da indução: Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 40/45 Exercício 2a void merge(int v1[], int n1, int v2[], int n2, int v3[]) { if ( n1 == 0 && n2 == 0 ) return; if (n1 == 0) { v3[0] = v2[0]; merge(v1, n1, ++v2, n2, ++v3); } else if (n2 == 0) { v3[0] = v1[0]; merge(++v1, n1, v2, n2, ++v3); } else if (v1[0] <= v2[0]) { v3[0] = v1[0]; merge(++v1, n1, v2, n2, ++v3); } else { v3[0] = v2[0]; merge(v1, n1, ++v2, n2, ++v3); } } Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 41/45 Exercício 2c void merge(int v1[], int n1, int v2[], int n2, int v3[]) { if ( n1 == 0 && n2 == 0 ) return; if (n1 == 0) { v3[0] = v2[0]; merge(v1, n1, ++v2, n2, ++v3); } else if (n2 == 0) { v3[0] = v1[0]; merge(++v1, n1, v2, n2, ++v3); } else if (v1[0] < v2[0]) { v3[0] = v1[0]; merge(++v1, n1, v2, n2, ++v3); } else if (v1[0] > v2[0]){ v3[0] = v2[0]; merge(v1, n1, ++v2, n2, ++v3); } else { v3[0] = v2[0]; merge(++v1,n1,++v2,n2, ++v3); } } Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 42/45 Exercício 8 ● 8) Escreva um algoritmo recursivo capaz de gerar todos os elementos do conjunto potência dado um conjunto formado por letras. ● Caso base? Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 43/45 Exercício 8 ● 8) Escreva um algoritmo recursivo capaz de gerar todos os elementos do conjunto potência dado um conjunto formado por letras. ● Caso base? 2{} = {} ● Passo da recursão: Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 44/45 Exercício 8 ● 8) Escreva um algoritmo recursivo capaz de gerar todos os elementos do conjunto potência dado um conjunto formado por letras. ● Caso base? 2{} = {} ● Passo da recursão: 2{a,b,c} = 2{b,c} U {a} x 2{b,c} Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 45/45 Exercício 8 void potencia(char pref[], char s[], char *p) { int l; char aux[100]; l = strlen(s); if ( l == 0 ) { if (strlen(pref) == 0 ) strcpy(p, "{}"); else { strcat(p, " "); strcat(p, pref); } return; } potencia(pref, s+1, p); strcpy(aux, pref); l = strlen(aux); aux[l] = s[0]; aux[l+1] = '\0'; potencia(aux, s+1, p); return; } Slide 1 Slide 2 Slide 3 Slide 4 Slide 5 Slide 6 Slide 7 Slide 8 Slide 9 Slide 10 Slide 11 Slide 12 Slide 13 Slide 14 Slide 15 Slide 16 Slide 17 Slide 18 Slide 19 Slide 20 Slide 21 Slide 22 Slide 23 Slide 24 Slide 25 Slide 26 Slide 27 Slide 28 Slide 29 Slide 30 Slide 31 Slide 32 Slide 33 Slide 34 Slide 35 Slide 36 Slide 37 Slide 38 Slide 39 Slide 40 Slide 41 Slide 42 Slide 43 Slide 44 Slide 45
Compartilhar