Descreva um algoritmo em pseudocódigo que, dada uma matriz quadrada A[n][n] de inteiros e um inteiro k>0…

Questão

Descreva um algoritmo em pseudocódigo que, dada uma matriz quadrada A[n][n] de inteiros e um inteiro k>0, percorra os elementos em faixas concêntricas (camadas) a partir da borda até o centro usando loops aninhados, calcule a soma de cada faixa e retorne a lista S com cada soma reduzida modulo k. Explique a estratégia adotada.

✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.

Resposta esperada

Resposta modelo (pseudocódigo e explicação): pseudocodigo: S := lista vazia para camada de 0 até floor((n-1)/2) faça soma := 0 inicio := camada fim := n - 1 - camada // percorre linha superior da faixa para j de inicio até fim faça soma := soma + A[inicio][j] fim para // percorre coluna direita (exclui canto superior já contado) para i de inicio+1 até fim faça soma := soma + A[i][fim] fim para // percorre linha inferior (se diferente da superior) se fim > inicio então para j de fim-1 decrescente até inicio faça soma := soma + A[fim][j] fim para fim se // percorre coluna esquerda (se diferente da direita) se fim > inicio então para i de fim-1 decrescente até inicio+1 faça soma := soma + A[i][inicio] fim para fim se anexar (soma mod k) a S fim para retornar S Explicação: o algoritmo percorre cada camada usando quatro segmentos (topo, direita, base, esquerda) com loops aninhados que visitam cada elemento da faixa exatamente uma vez, evitando duplicar cantos. Para n ímpar, a camada central (inicio=fim) é tratada pela primeira soma (apenas um elemento). Complexidade temporal: O(n^2) porque cada célula da matriz é visitada no máximo uma vez. Espaço adicional: O(m) onde m=ceil(n/2) para armazenar S. Variáveis usadas: camada, inicio, fim, i, j, soma, S.

Explicação

O algoritmo utiliza uma abordagem sistemática para percorrer a matriz em camadas, garantindo que todos os elementos de cada faixa sejam somados sem repetições. A divisão da matriz em segmentos facilita a implementação dos loops aninhados, permitindo um cálculo eficiente da soma. A complexidade temporal e o uso de espaço adicional são adequados para o problema, assegurando que a solução seja escalável para matrizes maiores.

Raio-X da questão

Questões parecidas com resolução

• Proponha um algoritmo em pseudocódigo que, dada uma lista A de n inteiros e um inteiro k>0, determine o comprimento do…
• Projete um algoritmo em pseudocódigo que, dada uma matriz M de inteiros com m linhas e n colunas, construa e retorne uma…
• Projete um algoritmo em pseudocódigo que, dado um vetor A[1..n] de inteiros e um inteiro k (1 = k = n), calcule a maior…
• Descreva em pseudocódigo um algoritmo que, dada uma matriz m×n de inteiros, calcule a soma de cada coluna usando…
• Descreva como um algoritmo com repetição aninhada pode ser utilizado para somar todos os elementos de uma matriz e…
• Projete um algoritmo em pseudocódigo que, dada uma lista A[1..n] de inteiros e um inteiro k (1 = k = n), calcule a lista…

Todas as questões de Estratégias de solução de problemas - Decomposição