Escreva em pseudocódigo um algoritmo que, dada uma matriz M com m linhas e n colunas e um inteiro x, conte…

Questão

Escreva em pseudocódigo um algoritmo que, dada uma matriz M com m linhas e n colunas e um inteiro x, conte quantas vezes x aparece em M usando loops aninhados e uma variável contador. Explique por que o algoritmo está correto, indique sua complexidade temporal em função de m e n e descreva como modificá-lo para interromper a busca assim que o contador atingir um limiar k.

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

Resposta esperada

Pseudocódigo (versão completa): contador := 0 para i de 1 até m faça para j de 1 até n faça se M[i][j] = x então contador := contador + 1 fim se fim para fim para retornar contador Correção: os loops aninhados visitam cada célula M[i][j] exatamente uma vez; portanto, incrementar contador ao encontrar M[i][j] = x contabiliza todas as ocorrências. Complexidade: no pior caso são verificadas m·n células, logo tempo O(m·n). Modificação para interrupção ao atingir k: contador := 0 para i de 1 até m faça para j de 1 até n faça se M[i][j] = x então contador := contador + 1 se contador >= k então retornar contador fim se fim se fim para fim para retornar contador Comentário sobre modificação: a alteração permite saída antecipada reduzindo o tempo médio quando k é pequeno; entretanto, no pior caso (quando ocorrem menos que k ocorrências) a complexidade continua O(m·n).

Explicação

O algoritmo percorre cada elemento da matriz uma única vez, garantindo que todas as ocorrências do número x sejam contadas. A complexidade O(m·n) reflete o fato de que, no pior cenário, todas as células precisam ser verificadas. A modificação para interromper a busca ao atingir o contador k otimiza o processo sem alterar a complexidade no pior caso.

Raio-X da questão

Questões parecidas com resolução

• Descreva em pseudocódigo um algoritmo que, dada uma matriz M de inteiros com m linhas e n colunas, conte quantas linhas…
• 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 um algoritmo em pseudocódigo que, dada uma matriz M de inteiros com dimensões m x n, encontre o maior valor…
• 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[m][n] de inteiros e um inteiro t (1 = t = min(m,n))…
• Projete um algoritmo em pseudocódigo que, dada uma variável inteira positiva n, construa uma matriz M n×n com M[i][j] =…

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