Ímpar-ímpar
Imagine que nós temos uma lista de números armazenada na memória.
Por exemplo,
L
Imagine que nós temos uma lista de números armazenada na memória.
Por exemplo,
L
1 | 2 |
|
|||||||
---|---|---|---|---|---|---|---|---|---|
8 | 21 | 2 | 9 | 16 | 12 | 17 | 19 | 6 | 10 |
A tarefa consiste em
Mover o maior elemento que aparece em uma posição ímpar para a última posição ímpar da lista
No exemplo acima, isso nos daria
L
No exemplo acima, isso nos daria
L
1 | 2 |
|
---|
Apresente um programa que realiza essa tarefa.
Nota: Utilize a numeração de posições natural nesse exercício.
Nota: Utilize a numeração de posições natural nesse exercício.
Passo 1
Beleza, a questão é a seguinte: temos uma lista L de tamanho n, indexada de 1 a n (numeração “natural”), e queremos “pegar” o maior valor que está em uma posição ímpar (1, 3, 5, …) e levá-lo para a última posição ímpar da lista (isto é, a maior posição ≤ n que seja ímpar).
Conteúdo: manipulação de vetores/arrays, índice 1-based, laço (loop), teste de paridade e deslocamento de elementos.
O que vamos precisar:
Conteúdo: manipulação de vetores/arrays, índice 1-based, laço (loop), teste de paridade e deslocamento de elementos.
O que vamos precisar:
- Percorrer o array em passos de 2 para achar o máximo em índices ímpares.
- Calcular se n é par ou ímpar (para achar a última posição ímpar).
- Fazer remoção/insersão simples (deslocar elementos) para mover o elemento.
Passo 2
Encontrar o maior elemento em posição ímpar.
- Inicializa
maxVal ← L[1] // supõe que índice 1 existe e é ímpar posMax ← 1
- Percorre todas as posições ímpares usando um loop de passo 2:
for i ← 1 to n step 2 do if L[i] > maxVal then maxVal ← L[i] posMax ← i
Aqui a gente compara cada L[i] com o maior já visto (maxVal). Se achar algo maior, grava no maxVal e guarda a posição i em posMax.
Passo 3
Calcular a última posição ímpar da lista.
- Se n é ímpar, a última posição ímpar é n.
- Se n é par, a última posição ímpar é n–1.
Em fórmula:
se (n mod 2) = 0 então
lastOdd ← n – 1
senão
lastOdd ← n
Passo 4
Mover o elemento de posMax para lastOdd.
Se posMax = lastOdd, não precisa mexer em nada. Caso contrário, fazemos assim:
Se posMax = lastOdd, não precisa mexer em nada. Caso contrário, fazemos assim:
- Guarda o valor a mover:
temp ← L[posMax]
- Desloca tudo que está entre posMax+1 e lastOdd para uma posição à esquerda:
for j ← posMax to lastOdd – 1 do L[j] ← L[j + 1]
- Escreve o valor guardado na última posição ímpar:
L[lastOdd] ← temp
Resposta
Pseudocódigo completo:
Programa MoverMaiorImparImpar
Entrada: L[1..n]
1. // Passo 2: acha o maior em índice ímpar
maxVal ← L[1]
posMax ← 1
for i ← 1 to n step 2 do
if L[i] > maxVal then
maxVal ← L[i]
posMax ← i
2. // Passo 3: determina a última posição ímpar
if (n mod 2) = 0 then
lastOdd ← n – 1
else
lastOdd ← n
3. // Passo 4: move de posMax para lastOdd
if posMax < lastOdd then
temp ← L[posMax]
for j ← posMax to lastOdd – 1 do
L[j] ← L[j + 1]
L[lastOdd] ← temp
4. // Saída: L já modificada
Retorna L