Lista 2 - Algoritmos Recursivos

Lista II Introdução à Computação II, 5954006 1 Lista de Exercícios II – Algoritmos Recursivos 1. Dado um vetor V de n elementos inteiros, desenvolva funções recursivas para: (a) Encontrar o valor máximo do vetor (b) Encontrar o valor mínimo do vetor (c) Encontrar a soma dos elementos do vetor (d) Para cada caso, qual tipo de algoritmo seria mais recomendado: recursivo ou não recursivo? Por quê? 2. Desenvolva funções ou procedimentos recursivos para: (a) Escrever os números de n até 0 (b) Escrever os números de 0 até n (dica: basta alterar a ordem de uma linha do programa anterior) (c) Calcular a soma de todos os números inteiros entre 1 e n (d) Calcular o produto de todos os quadrados dos números inteiros entre 1 e n (por exemplo, se n=4, 12 * 22 * 32 * 42 = 576) (e) Ler e mostrar uma cadeia de caracteres (string) na ordem reversa, sem utilizar vetores/strings (f) Verificar se o número n é primo (você deve verificar se n é divisível por qualquer número menor do que n) (g) Calcular a potência de 2 elevado a um número inteiro não negativo 3. Desenvolva funções recursivas para: (a) Calcular a potência de qualquer número elevado a um número inteiro não negativo, utilizando xn = x × xn-1 (b) Calcular a potência de qualquer número elevado a um número inteiro positivo utilizando quadrados, isto é, x2n = (xn)2 e x2n+1 = x × x2n 4. O que o programa seguinte faz? 1 2 Algoritmo mystery( array[], size ) 3 se (size > 0) 4 size = size - 1 5 imprima (array[size]) 6 mystery( array , size ) 7 5. O que o programa seguinte faz? 1 2 Algoritmo mystery( a[], size ) 3 size = size - 1 4 se (size > 0) 5 retorne a[size] + mystery(a , size) 6 senão 7 retorne a[size] 8 Resolução da lista 2 - 2021 1) #include <stdio.h> #include <stdlib.h> #include <time.h> int menor(int *v, int n, int menorT) { //checar se tem apenas um elemento if(n==0) { return menorT; } else if(v[n]>menorT) { menor(v,n-1,menorT); } else { menorT = v[n]; } } int maior(int *v, int n, int maiorT) { if(n==0) { return maiorT; } else if(v[n]>maiorT) { maiorT = v[n]; } else { maior(v,n-1,maiorT); } } int soma(int *v, int n, int somaT) { if(n==0) { return somaT; } somaT = somaT + v[n]; soma(v,n-1,somaT); } int main() { int *v; int n; int i; printf("Tamanho do vetor: "); scanf("%d%*c",&n); v = (int*)malloc(n*sizeof(int)); srand(time(NULL)); for(i=0;i<n;i++) { v[i] = rand() % 100; } printf("\nVetor gerado\n"); for(i=0;i<n;i++) { printf("v[%d] = %d ",i,v[i]); } int menorNum = v[0]; printf("\nMenor elemento do vetor: %d ",menor(v,n-1,menorNum)); int maiorNum = v[0]; printf("\nMaior elemento do vetor: %d ",maior(v,n-1,maiorNum)); int somaT = v[0]; printf("\nSoma: %d",soma(v,n-1,somaT)); return 0; } d) A complexidade de uma função recursiva é o produto da complexidade de cada chamada pela quantidade de chamadas. Tanto com uma implementação recursiva quanto com uma implementação iterativa, o vetor teria que ser percorrido a fim de realizar os procedimentos, portanto no pior caso todos os procedimentos têm uma complexidade assintótica O(N), sendo N o tamanho do vetor. A vantagem da iteração em relação à recursão é que não há empilhamento de chamadas de função, então o uso de memória é mais otimizado na iteração. Vale lembrar: 2) #include <stdio.h> #include <stdlib.h> #include <math.h> #include <stdbool.h> void letra_a(int n)//n a 0 { if(n==0) printf(" %d ",n); else { printf(" %d ",n); letra_a(n-1); } } void letra_b(int n)//0 a n { if(n==0) { printf(" %d ",n); } else { letra_b(n-1); printf(" %d ",n); } } int soma_n(int n, int soma)//letra c { if(n==0) { return soma; } else { soma += n + soma_n(n-1,soma); } } int produto_n(int n, int produto)//letra d { if(n==0) { return (int)produto; } else { produto = produto*pow(n,2); produto_n(n-1,produto); } } void string_reversa(int n)//letra e { char c; if(n == 1) { scanf("%c%*c",&c); printf("\nReversa: \n\n"); putc(c,stdout); } else { scanf("%c%*c",&c); string_reversa(n-1); putc(c,stdout); } } //letra f bool primo(int n, int divisor)//divisor = 0, inicialmente { if((divisor == n/2) && (n%divisor != 0)) return false; if(n%divisor == 0) return true; primo(n,divisor++); } int potenciaDeDois(int n, int base, int potencia) { if(n==0) { return potencia; } potencia = potencia*base; potenciaDeDois(n-1,base,potencia); } int main() { int n; printf("\nValor de n: \n"); scanf("%d%*c",&n); letra_a(n); printf("\n"); letra_b(n); printf("\n"); printf("\nSoma: %d",soma_n(n,0)); printf("\n"); printf("\nProduto dos numeros ao quadrado: %d",produto_n(n,1)); printf("\n"); printf("\nString reversa, digite os caracteres: \n"); string_reversa(n); if(primo(n,2)) { printf("\n%d eh divisivel por algum numero menor ou igual a ele.\n",n); } else { printf("\n%d nao e divisivel por nenhum numero menor que ele.\n",n); } printf("\n2^n -> 2^%d = %d ",n,potenciaDeDois(n,2,1)); return 0; } 3) #include <stdio.h> #include <stdlib.h> int letra_a(int x, int n,int potencia) // x^n { if(n==0) { return potencia; } else { potencia = potencia*x; letra_a(x,n-1,potencia); } } int letra_b(int x,int n, int counter, int potencia) { if((n%2 != 0) && (counter > 2*n)) // x^2n+1 = x*(x^2n) return x*potencia; if((n%2 == 0) && (counter > 2*n)) // x^2n = (x^n)^2 return potencia; letra_b(x,n,counter+1,potencia*x); } int main() { int X; int n; printf("Numero X e o numero n ao qual ele sera elevado:\n"); scanf("%d%*c",&X); scanf("%d%*c",&n); printf("\nLetra A)\nX^n = %d^%d = %d\n",X,n,letra_a(X,n,1)); printf("\nLetra B)\nX^2n = %d^%d = %d\n",X,2*n,letra_b(X,n,1,1)); return 0; } 4) Imprime o array de trás para frente. Se size maior que zero(não chegou no último elemento), size é decrescido, imprime o elemento naquela posição e a função é chamada novamente para fazer a mesma coisa. 5) Soma de (size-1) até 0. Quando chega em a[0], retorna o primeiro elemento. Ex: a[]= {1,2,3,4,5}, size = 5 size = 4 retorne a[4]+mystery(a,4) size = 1 ... retorne a[1] + mystery(a,1) size = 1 - 1 = 0 retorne a[size] -> nesse caso, a[0]