Proponha um algoritmo em pseudocódigo que, dada uma lista A de n inteiros e um inteiro k>0, determine o…

Questão

Proponha um algoritmo em pseudocódigo que, dada uma lista A de n inteiros e um inteiro k>0, determine o comprimento do maior subvetor contíguo cuja soma é múltipla de k. Use laços (repetições) aninhados e explique como as variáveis de controle são inicializadas e atualizadas durante a execução.

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

Resposta esperada

Pseudocódigo (solução ingênua com laços aninhados): algoritmo MaiorSubvetorMultiplo(A[1..n], k) max_len <- 0 for i de 1 até n faça soma <- 0 // reinicia soma para cada novo início i for j de i até n faça soma <- soma + A[j] se (soma mod k = 0) e ((j - i + 1) > max_len) então max_len <- j - i + 1 fimse fimfor fimfor retorne max_len fimalgoritmo Inicializações e atualizações: max_len começa em 0 e guarda o maior comprimento encontrado; para cada i a variável soma é zerada e acumulada no laço interno; j varia até o fim do vetor, e a condição soma mod k = 0 verifica múltiplos de k. Complexidade temporal: O(n^2). Espaço extra: O(1).

Explicação

O algoritmo proposto utiliza laços aninhados para explorar todos os subvetores contíguos da lista, garantindo que cada soma seja verificada quanto à sua divisibilidade por k. A variável max_len é atualizada sempre que um subvetor com soma múltipla de k é encontrado, permitindo rastrear o comprimento máximo. A abordagem tem complexidade O(n^2), o que é aceitável para listas de tamanho moderado, e utiliza espaço extra constante, já que apenas algumas variáveis são necessárias.

Raio-X da questão

Questões parecidas com resoluçã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…
• Projete um algoritmo em pseudocódigo que, dado um vetor A[1..n] de inteiros, encontre o comprimento do maior subvetor…
• 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…
• Descreva um algoritmo em pseudocódigo que, dada uma matriz quadrada A[n][n] de inteiros e um inteiro k>0, percorra os…
• Projete um algoritmo em pseudocódigo que, dado um vetor V de n inteiros e um inteiro k, determine se existem índices i <…
• Escreva um pseudocódigo que, dada uma lista A de n inteiros, percorra pares ordenados (i,j) com i<j usando loops…

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