Projete um algoritmo em pseudocódigo que, dada uma matriz M de inteiros com m linhas e n colunas, construa e…

Questão

Projete um algoritmo em pseudocódigo que, dada uma matriz M de inteiros com m linhas e n colunas, construa e retorne uma matriz S de dimensão (m-1)×(n-1) em que S[i][j] é a soma dos elementos da submatriz 2×2 de M com canto superior esquerdo em M[i][j]. Explique o uso de repetições simples e aninhadas, justifique a correção e analise a complexidade em função de m e n.

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

Resposta esperada

Pseudocódigo: 1. Criar S de tamanho (m-1)×(n-1) 2. para i de 1 até m-1 faça 3. para j de 1 até n-1 faça 4. S[i][j] := M[i][j] + M[i][j+1] + M[i+1][j] + M[i+1][j+1] 5. fim para 6. fim para 7. retornar S Correção: cada S[i][j] soma exatamente os quatro elementos da submatriz 2×2 com canto em M[i][j]; os índices cobrem todos os cantos superiores possíveis (1..m-1 e 1..n-1). Repetições: utiliza-se um loop externo sobre linhas e um loop interno sobre colunas (aninhados). Complexidade: cada par (i,j) realiza operação constante, logo tempo T((m-1)(n-1)) = T(m·n). Espaço adicional é T(m·n) para S (mais armazenamento para saída).

Explicação

O pseudocódigo apresenta uma abordagem clara para calcular a soma dos elementos de cada submatriz 2×2, garantindo que todos os índices necessários sejam percorridos. A estrutura de repetição aninhada permite que cada elemento de S seja calculado a partir dos quatro elementos correspondentes de M, assegurando a cobertura completa da matriz. A análise de complexidade mostra que o tempo e o espaço utilizados são proporcionais ao tamanho da matriz original, refletindo a eficiência do algoritmo.

Raio-X da questão

Questões parecidas com resolução

• Projete um algoritmo em pseudocódigo que, dada uma variável inteira positiva n, construa uma matriz M n×n com M[i][j] =…
• Projete um algoritmo em pseudocódigo que, dada uma matriz M[m][n] de inteiros e um inteiro t (1 = t = min(m,n))…
• Projete um algoritmo em pseudocódigo que, dada uma matriz M com m linhas e n colunas de inteiros, determine quantos…
• Dada uma matriz m×n de inteiros (representando pontos de um mapa), escreva em pseudocódigo um algoritmo recursivo que…
• Descreva em pseudocódigo um algoritmo que, dada uma matriz m×n de inteiros, calcule a soma de cada coluna usando…
• Descreva um algoritmo em pseudocódigo que, dada uma matriz quadrada A[n][n] de inteiros e um inteiro k>0, percorra os…

Todas as questões de Programação - Linguagem de programação