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

• “Quando dois barcos chegam juntos, preciso consultar os horários previstos, a quantidade de pescado e o espaço livre em…
• Pesquisadores acompanham a catalogação digital de objetos de um centro cultural. Para reduzir registros duplicados, o…
• Durante uma feira de produtos da agricultura familiar, uma estudante utiliza uma planilha digital para registrar os…
• Considere três instâncias de um mesmo problema de cálculo de imposto municipal sobre venda: instância A (região urbana…
• Projete a assinatura de um algoritmo que calcula o desvio padrão de uma coleção de dados numéricos e aceite uma variável…
• Dadas três instâncias do problema de distribuição de kits de informática a escolas (A:10 kits, rede lenta, técnico…

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