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

Questão

Projete um algoritmo em pseudocódigo que, dada uma lista A[1..n] de inteiros e um inteiro k (1 = k = n), calcule a lista B onde B[i] é a média aritmética dos k elementos contíguos A[i..i+k-1]. Use loops (pode usar loops aninhados) e variáveis.

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

Resposta esperada

Pseudocódigo (versão ingênua O(n·k)): B := vetor vazio de tamanho n-k+1 para i de 1 até n-k+1 faça soma := 0 para j de i até i+k-1 faça soma := soma + A[j] fim para B[i] := soma / k fim para Explicação: o loop externo posiciona a janela de tamanho k; o interno soma os k valores. Complexidade O(n·k). Otimização possível: usar soma deslizante (subtrair A[i-1], somar A[i+k-1]) para obter O(n).

Explicação

O algoritmo apresentado utiliza dois loops para calcular a soma dos k elementos contíguos da lista A, permitindo que a média aritmética seja armazenada na lista B. O primeiro loop controla a posição inicial da janela de k elementos, enquanto o segundo loop realiza a soma dos elementos dessa janela. A complexidade O(n·k) é resultante do fato de que, para cada posição da janela, é necessário somar k elementos, mas uma otimização pode ser aplicada para reduzir essa complexidade.

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