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

• Em um laboratório escolar, os alunos precisam registrar o resultado de 20 medições. Fazer isso manualmente aumenta o…
• Num ponto de bicicletas compartilhadas perto da orla, o sistema precisa registrar cada devolução sem gerar erro. Quando…
• — Por que o aplicativo me obriga a passar pelo "Caso de Uso 1" para chegar ao "Caso de Uso 2"? — reclamou um morador ao…
• Uma rotina chamada mostrarLinha(texto) imprime exatamente uma linha na tela. Em um programa, ela é chamada 1 vez antes…
• Considere o pseudocódigo: 'Se nota >= 60 então situacao <- "aprovado" senão situacao <- "reprovado"'. Qual será o valor…
• Leia o enunciado em linguagem oral: 'Se a rua estiver molhada, use capa; caso contrário, não use.' Que tipo de seleção…

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