Recursao-em-C-Lista-de-Exercicios-Resolucao-e-Exemplos

ESTRUTURA DE DADOS UTILIZAR LINGUAGEM C LISTA DE EXERCICIOS SOBRE RECURSÃO Q1 Contando caracteres recursivamente Ação Forneça um algoritmo recursivo para contar quantas vezes um determinado caractere ocorre em uma string Não é permitido usar comandos de repetição nesta função A função main e o protótipo da função recursiva são fornecidos no arquivo de envio logo abaixo Entrada Linha 1 a string Linha 2 caractere que será contado na string anterior Saída Número de ocorrências do caractere na string Exemplos fundamentos de programacao a 4 include iostream include string using namespace std Retorna o números de ocorrências do caractere c na string str com n caracteres Algoritmo deve ser recursivo e sem comandos de repetição int contaCaracteresstring str int n char c fazer int main fazer Q2Dado um vetor com n inteiros Aa0a1an1 n0 imprima um triângulo de números tal que na base do triângulo estejam todos os elementos do vetor original ou seja a0a1an1 o número de elementos em cada nível acima da base é um a menos que no nível inferior e cada elemento no iésimo nível é a soma de dois elementos consecutivos do nível inferior Entrada A primeira linha deve ler o tamanho n do vetor A O valor de n é maior ou igual a zero A segunda linha deve ler os n elementos do vetor separados por espaço simples Saída O triângulo de somas Entrada 5 1 2 3 4 5 Saída 48 20 28 8 12 16 3 5 7 9 1 2 3 4 5 Q3 Leia um vetor de inteiros e implemente as funções sem utilizar laço para iterar sobre os elementos Você pode utilizar laço apenas para ler os elementos do vetor Entrada o um vetor de inteiros O vetor tem no mínimo 1 elemento Saída o vet o vetor o rvet o vetor impresso ao contrário o sum a soma dos elementos o mult a multiplicação dos elementos o min o menor elemento o inv inverte o vetor depois imprime ele invertido EXEMPLO Testes 01 4 vet 4 rvet 4 sum 4 mult 4 min 4 inv 4 02 3 4 2 vet 3 4 2 rvet 2 4 3 sum 9 mult 24 min 2 inv 2 4 3 Q4 Dado uma matriz que representa espaços vazios e árvores e um ponto inicial onde começa o fogo retorne a matriz com as árvores queimadas O fogo não se espalha nas diagonais apenas nas 4 direções cardeais A matriz está codificada assim 1a linha nl nc l c respectivamente número de linhas e colunas da matriz linha e coluna onde começa o fogo Nas linhas subsequentes representa uma árvore representa um espaço vazio o representa uma árvore queimada Saída esperada Imprima a matriz após a queimada acontecer EXEMPLO Testes 01 2 3 1 1 o oo 02 5 5 0 0 o o ooo oo ooo 03 5 7 2 3 ooo ooooo ooooo oo ooo Ajuda Você pode utilizar um array de strings para representar uma matriz de caracteres Uma string é um vetor de caracteres Dessa forma um string mat5 é um vetor de caracteres bidimensional com 5 linhas por exemplo O exemplo a seguir já carrega a matriz na main e já faz um método capaz de imprimir a matriz Você só precisa implementar o método tocarfogo Utilize as seguintes regras para recursão Se a posição for fora da matriz retorne Se a posição não for uma arvore retorne Queime a arvore Chame a recursão para todos os vizinhos include iostream include string using namespace std void showstring mat int nl forint l 0 l nl l cout matl void tocarfogoint nl int nc string mat int l int c TODO faca seu codigo aqui int main int nl 0 nc 0 lfire 0 cfire 0 cin nl nc lfire cfire string mat new stringnl forint l 0 l nl l string line cin line matl line tocarfogonl nc mat lfire cfire showmat nl delete mat include iostream include string using namespace std Função recursiva para contar o número de ocorrências de um caractere em uma string Recebe dois parâmetros a string a ser verificada e o caractere a ser contado int countCharstring str char c Verifica se a string é vazia ifstrlength 0 Se sim retorna 0 não há caracteres a serem contados return 0 Verifica se o primeiro caractere da string é igual ao caractere a ser contado ifstr0 c Se sim retorna 1 mais o resultado da recursão da função com a string a partir do segundo caractere return 1 countCharstrsubstr1 c else Caso contrário retorna o resultado da recursão da função com a string a partir do segundo caractere return countCharstrsubstr1 c int main Lê a string e o caractere da entrada padrão string str char c getlinecin str cin c Chama a função countChar com os parâmetros adequados e imprime o resultado na tela cout countCharstr c endl return 0 include iostream include vector biblioteca para usar vetores using namespace std int main int n cin n lê o tamanho do vetor vectorint an cria um vetor com n elementos for int i 0 i n i cin ai lê cada elemento do vetor vectorvectorint trianglen cria um vetor de vetores com n elementos trianglen1 a na última posição coloca o vetor original itera pelos níveis do triângulo de trás para frente for int i n2 i 0 i para cada posição do nível atual calcula a soma dos elementos consecutivos do nível inferior for int j 0 j i j triangleipushbacktrianglei1j trianglei1j1 insere a soma no vetor do nível atual imprime o triângulo for int i 0 i n i for int j 0 j triangleisize j cout triangleij imprime o elemento if j triangleisize1 cout se não for o último elemento imprime uma vírgula e um espaço cout endl pula linha para imprimir o próximo nível return 0 finaliza o programa include iostream include vector include algorithm include numeric biblioteca para usar a função accumulate using namespace std Função que imprime o vetor void imprimeVetorvectorint vet cout Vetor for int i vet laço foreach para percorrer o vetor cout i cout endl Função que imprime o vetor ao contrário void imprimeVetorAoContrariovectorint vet cout Vetor ao contrário for auto it vetrbegin it vetrend it laço for reverso para percorrer o vetor ao contrário cout it cout endl Função que calcula a soma dos elementos do vetor int calculaSomavectorint vet return accumulatevetbegin vetend 0 usa a função accumulate da biblioteca numeric para somar os elementos do vetor Função que calcula a multiplicação dos elementos do vetor int calculaMultiplicacaovectorint vet int mult 1 for int i vet laço foreach para percorrer o vetor mult i multiplica o valor atual da variável mult pelo valor atual do elemento do vetor return mult Função que encontra o menor elemento do vetor int encontraMenorElementovectorint vet int min vet0 for int i vet laço foreach para percorrer o vetor if i min min i atualiza o valor da variável min caso encontre um elemento menor return min Função que inverte o vetor e o imprime void inverteVetorvectorint vet reversevetbegin vetend usa a função reverse para inverter o vetor imprimeVetorvet imprime o vetor invertido Função principal int main int n valor vectorint vet cout Digite o tamanho do vetor cin n laço para ler os elementos do vetor for int i 0 i n i cout Digite o valor do elemento i 1 cin valor vetpushbackvalor chamada das funções imprimeVetorvet imprimeVetorAoContrariovet cout Soma dos elementos calculaSomavet endl cout Multiplicação dos elementos calculaMultiplicacaovet endl cout Menor elemento encontraMenorElementovet endl inverteVetorvet return 0 include iostream include vector using namespace std int main int nl nc l c cin nl nc l c vectorvectorchar matriznl vectorcharnc Cria uma matriz de tamanho nl x nc preenchida com espaços vazios for int i 0 i nl i for int j 0 j nc j cin matrizij matrizlc o A posição inicial do fogo é marcada como árvore queimada bool queimou true while queimou Enquanto houver árvores queimando queimou false vectorvectorchar novamatriznl vectorcharnc Cria uma nova matriz para armazenar o estado da matriz após um passo do fogo for int i 0 i nl i for int j 0 j nc j if matrizij i 0 matrizi1j o Verifica se há uma árvore queimada na posição acima i nl1 matrizi1j o Verifica se há uma árvore queimada na posição abaixo j 0 matrizij1 o Verifica se há uma árvore queimada na posição à esquerda j nc1 matrizij1 o Verifica se há uma árvore queimada na posição à direita novamatrizij o Se a árvore pode queimar ela é marcada como queimada na nova matriz queimou true Houve uma árvore queimando neste passo else novamatrizij matrizij Copia o conteúdo da matriz original para a nova matriz matriz novamatriz A matriz original é atualizada para o estado da nova matriz for int i 0 i nl i for int j 0 j nc j cout matrizij Imprime a matriz após a queimada cout endl return 0