Projete um algoritmo em pseudocódigo que, dado um vetor A[1..n] de inteiros e um inteiro k (1 = k = n)…

Questão

Projete um algoritmo em pseudocódigo que, dado um vetor A[1..n] de inteiros e um inteiro k (1 = k = n), calcule a maior soma de k elementos contíguos usando repetições simples e aninhadas de forma eficiente. Inclua inicialização de variáveis e estruturas de loop.

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

Resposta esperada

Pseudocódigo (janela deslizante): se n = 0 ou k > n então retornar erro soma := 0 para i de 1 até k faça soma := soma + A[i] fim para max := soma para i de k+1 até n faça soma := soma + A[i] - A[i-k] se soma > max então max := soma fim se fim para retornar max Complexidade O(n); usa uma variável de acumulação e um loop simples após inicialização.

Explicação

O algoritmo utiliza a técnica da janela deslizante para calcular a soma de k elementos contíguos de forma eficiente, evitando a necessidade de recalcular a soma de cada subvetor repetidamente. Ao inicializar a soma com os primeiros k elementos e, em seguida, ajustar essa soma ao adicionar o próximo elemento e subtrair o que saiu da janela, o algoritmo mantém a complexidade em O(n). Essa abordagem garante que todos os elementos sejam processados uma única vez, resultando em um desempenho otimizado.

Raio-X da questão

Questões parecidas com resolução

• Um sistema de uma estufa analisa cinco leituras de umidade do solo: 19, 22, 24, 27 e 20. O algoritmo conta as leituras…
• Na montagem de um boletim digital da escola, as seções estão nesta ordem: capa, entrevista, fotos e agenda. A equipe…
• Em um aplicativo da escola, a lista de representantes da turma aparece nesta ordem: Ana, Bia, Caio, Davi e Elisa. Caio…
• Enquanto agentes de manutenção acompanham pedidos de reparo de bicicletas públicas, o painel registra os chamados em uma…
• — O livro de Marina Souza está disponível? — perguntou uma visitante ao balcão da biblioteca municipal. No computador…
• — O kit 47 já foi devolvido? — perguntou a técnica responsável pela campanha itinerante de vacinação. Antes do uso de…

Todas as questões de Programação - Algoritmos clássicos