Projete um algoritmo em pseudocódigo que, dada uma matriz M[m][n] de inteiros e um inteiro t (1 = t =…

Questão

Projete um algoritmo em pseudocódigo que, dada uma matriz M[m][n] de inteiros e um inteiro t (1 = t = min(m,n)), verifique se existe alguma submatriz contígua de dimensão t×t composta apenas por zeros. Use repetições aninhadas e especifique a complexidade em termos de m, n e t.

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

Resposta esperada

Resposta modelo (pseudocódigo): para i de 1 até m - t + 1 faça para j de 1 até n - t + 1 faça todosZeros := verdadeiro para a de 0 até t-1 faça para b de 0 até t-1 faça se M[i+a][j+b] <> 0 então todosZeros := falso pare // sai do loop b fim se fim para se não todosZeros então pare // sai do loop a fim se fim para se todosZeros então retorne verdadeiro // encontrou submatriz t×t de zeros fim se fim para fim para retorne falso Complexidade: o algoritmo testa (m - t + 1)*(n - t + 1) posições possíveis; para cada posição verifica t*t elementos, logo complexidade O((m - t + 1)*(n - t + 1)*t^2), que no pior caso é O(m*n*t^2).

Explicação

O pseudocódigo apresentado percorre todas as possíveis posições onde uma submatriz t×t pode ser encontrada dentro da matriz M, garantindo que cada posição é verificada quanto à presença de zeros. Para cada posição, ele utiliza loops aninhados para checar todos os elementos da submatriz, resultando em uma análise completa. A complexidade final reflete o número total de verificações realizadas, que cresce com o aumento das dimensões da matriz e do tamanho da submatriz.

Raio-X da questão

Questões parecidas com resolução

• 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, dada uma matriz M com m linhas e n colunas de inteiros, determine quantos…
• Desenhe um algoritmo em pseudocódigo que, dada uma matriz M[N][M] com 0 (livre) e 1 (bloqueado), identifique todas as…
• 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 (valores 0/1) e um inteiro k>0, retorne o…
• Descreva em pseudocódigo um algoritmo que, dado um inteiro n>0, construa a matriz M[1..n][1..n] tal que M[i][j]=1 se i…

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