Dados
e dois números inteiros positivos,
e
, diferentes de 0 , imprimir em ordem crescente os
primeiros naturais que são múltiplos de
ou de
e ou de ambos. Exemplo: Para
e
a saída deverá ser:
.
Passo 1
Resumo do enunciado: dado um inteiro positivo n e dois inteiros positivos i e j, queremos listar em ordem crescente os n primeiros números naturais (incluindo 0) que são múltiplos de i ou de j (ou de ambos). O conteúdo principal envolve progressões aritméticas e união de conjuntos ordenados.
Passo 2
Entendendo as progressões: os múltiplos de i formam a sequência 0,i,2i,3i,… e os múltiplos de j formam 0,j,2j,3j,…. A ideia é fazer a união ordenada dessas duas sequências sem repetições, até coletarmos n elementos.
Estratégia de mesclagem (merge): vamos manter dois ponteiros que percorrem cada uma das duas sequências de múltiplos. A cada passo, comparamos o próximo múltiplo de i com o próximo múltiplo de j e acrescentamos o menor (ou apenas um se forem iguais) na lista de resultados, avançando o ponteiro correspondente.
Critério de término: repetimos o processo de mesclagem até termos coletado exatamente n elementos. Garantimos que 0 aparecerá apenas uma vez (quando ambos ponteiros estiverem em zero).
Estratégia de mesclagem (merge): vamos manter dois ponteiros que percorrem cada uma das duas sequências de múltiplos. A cada passo, comparamos o próximo múltiplo de i com o próximo múltiplo de j e acrescentamos o menor (ou apenas um se forem iguais) na lista de resultados, avançando o ponteiro correspondente.
Critério de término: repetimos o processo de mesclagem até termos coletado exatamente n elementos. Garantimos que 0 aparecerá apenas uma vez (quando ambos ponteiros estiverem em zero).
Passo 3
Impressão do resultado: ao final, imprimimos a lista resultante de tamanho n, já em ordem crescente e sem duplicatas.
Resposta
// Pseudocódigo para obter os n primeiros múltiplos de i ou j
função gerarMultiplos(n, i, j):
lista ← lista vazia
múltA ← 0 // próximo múltiplo de i
múltB ← 0 // próximo múltiplo de j
passoA ← i // incremento para i
passoB ← j // incremento para j
contador ← 0
enquanto contador < n faça
se múltA < múltB então
lista.adicionar(múltA)
múltA ← múltA + passoA
senão se múltB < múltA então
lista.adicionar(múltB)
múltB ← múltB + passoB
senão
// múltA == múltB
lista.adicionar(múltA)
múltA ← múltA + passoA
múltB ← múltB + passoB
fim se
contador ← contador + 1
fim enquanto
retornar lista
função gerarMultiplos(n, i, j):
lista ← lista vazia
múltA ← 0 // próximo múltiplo de i
múltB ← 0 // próximo múltiplo de j
passoA ← i // incremento para i
passoB ← j // incremento para j
contador ← 0
enquanto contador < n faça
se múltA < múltB então
lista.adicionar(múltA)
múltA ← múltA + passoA
senão se múltB < múltA então
lista.adicionar(múltB)
múltB ← múltB + passoB
senão
// múltA == múltB
lista.adicionar(múltA)
múltA ← múltA + passoA
múltB ← múltB + passoB
fim se
contador ← contador + 1
fim enquanto
retornar lista