Ímpar-ímpar
Imagine que nós temos uma lista de números armazenada na memória.
Por exemplo,
L
1 2 cdots
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
1 2 cdots
Apresente um programa que realiza essa tarefa.
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:
  • 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.
  1. Inicializa
    maxVal ← L[1]    // supõe que índice 1 existe e é ímpar
    posMax ← 1
    
  2. 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:
  1. Guarda o valor a mover:
    temp ← L[posMax]
    
  2. 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]
    
  3. 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

Exercícios relacionados