O maior e o segundo maior
Relembre o problema de
Mover o maior elemento para a última posição
e mover o segundo maior elemento para a penúltima posição da lista
E relembre a seguinte estratégia para resolver o problema
B. Localizar o maior e o segundo maior elementos - (simultaneamente) e colocá-los em suas respectivas posições
Apresente um programa que implementa essa estratégia
Dica: Tome cuidado com a situação em que o segundo maior elemento se encontra na última posição da lista.
Relembre o problema de
e mover o segundo maior elemento para a penúltima posição da lista
E relembre a seguinte estratégia para resolver o problema
B. Localizar o maior e o segundo maior elementos - (simultaneamente) e colocá-los em suas respectivas posições
Apresente um programa que implementa essa estratégia
Dica: Tome cuidado com a situação em que o segundo maior elemento se encontra na última posição da lista.
Passo 1
Beleza, vamos lá! O enunciado pede um programa que, dada uma lista, faça duas coisas de uma vez só: colocar o maior elemento na última posição e o segundo maior na penúltima. Isso é um assunto de Algoritmos sobre vetores (listas) e operações básicas de busca (procurar o maior e o segundo maior) e troca (swap). Para resolver precisamos:
- Percorrer a lista uma vez só (para eficiência),
- Manter dois índices: onde está o maior e onde está o segundo maior,
- Depois, trocar esses elementos com as posições finais certas, cuidando da ordem pra não estragar nenhum valor.
Passo 2
Primeiro, como a gente acha o maior e o segundo maior num único passeio?
- A gente inicializa dois índices, digamos
i_max = 0
ei_seg = 0
. - Varre a lista de
i = 1
atén-1
:- Se
A[i] > A[i_max]
, então o antigo maior vira segundo maior (i_seg = i_max
) e o novo maior éi_max = i
. - Senão, se
A[i] > A[i_seg]
(ei
não é igual ai_max
), aí atualiza só o segundo maior:i_seg = i
.
Isso garante que, no fim,i_max
aponta pro maior ei_seg
pro segundo maior.
- Se
Passo 3
Agora vem a parte delicada: fazer as trocas sem bagunçar os índices.
Imagine que
Imagine que
i_seg
(segundo maior) possa estar antes ou depois de i_max
na lista. Dependendo disso, se a gente trocar primeiro o maior, podemos deslocar o segundo maior sem perceber. A solução é:- Se
i_seg < i_max
, a gente primeiro move o maior pra última posição e depois o segundo maior pra penúltima. - Se
i_seg > i_max
, a gente inverte a ordem: primeiro troca o segundo maior pra penúltima, e só depois o maior pra última.
Dessa forma nenhuma troca “esconde” o índice que ainda falta.
Passo 4
Traduzindo tudo em Python (que é quase pseudocódigo):
def mover_dois_maiores(A):
n = len(A)
if n < 2:
return # não tem dois elementos pra trocar
# 1) achar índices do maior e do segundo maior
i_max = 0
i_seg = 0
for i in range(1, n):
if A[i] > A[i_max]:
i_seg = i_max
i_max = i
elif A[i] > A[i_seg]:
i_seg = i
# 2) trocar nas posições finais na ordem certa
if i_seg < i_max:
# primeiro maior, depois segundo
A[i_max], A[n-1] = A[n-1], A[i_max]
A[i_seg], A[n-2] = A[n-2], A[i_seg]
else:
# primeiro segundo, depois maior
A[i_seg], A[n-2] = A[n-2], A[i_seg]
A[i_max], A[n-1] = A[n-1], A[i_max]
Resposta
O programa acima implementa a estratégia B: em uma única varredura identificamos o maior e o segundo maior e então, na ordem cuidadosa, colocamos o maior em
A[n-1]
e o segundo maior em A[n-2]
, tratando corretamente o caso em que o segundo maior começa na última posição.