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

• Em uma usina, cada estado de uma turbina é registrado com um código de dois bits: | Estado | Código | |---|---| | Parada…
• No controle de um satélite, um gráfico de barras descrito pela equipe registra: com o sistema operacional iniciado, o…
• O clube de jogos da escola vai usar um programa simples para registrar cada participante. Em cada cadastro, a pessoa…
• Na horta da escola, uma estação simples registra a temperatura informada por um sensor. O programa deve mostrar essa…
• Pesquisadores acompanham o funcionamento de um robô que cuida de seis placas solares em uma estação de pesquisa. O robô…
• Por que alguns tablets de um centro cultural aparecem como disponíveis, embora estejam guardados para conserto? Para…

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