Considere uma loja online que possui duas estruturas de dados relacionadas por índice:
- Um vetor ordenado contendo os preços dos produtos:
- Um vetor paralelo contendo os nomes ou IDs dos produtos:
O índice
corresponde ao mesmo produto em ambos os vetores, isto é, o produto
tem preço
.
Um cliente deseja obter detalhes do produto que custa exatamente R
70,00. Utilizando a busca de Fibonacci descreva como o sistema deve exibir estes detalhes para o cliente.
Passo 1
O enunciado nos dá um vetor ordenado de preços
e um vetor paralelo de produtos
Queremos encontrar o produto cujo preço é exatamente R$ 70,00 usando busca de Fibonacci e, em seguida, exibir seus detalhes.
Passo 2
Definimos
. Calculamos a sequência de Fibonacci até o menor
tal que
:
Aqui
, então tomamos
e inicializamos o deslocamento
. Usamos indexação base zero (índices vão de 0 a 12).
Passo 3
Enquanto
fazemos:
calcule
calcule
Na 1ª iteração:
.
Comparamos com o alvo
. Como
, jogamos fora a parte esquerda e atualizamos
Comparamos
Passo 4
2ª iteração:
.
⇒ atualizamos
Passo 5
3ª iteração:
.
⇒
Passo 6
4ª iteração:
.
⇒
Passo 7
5ª iteração:
.
⇒
Passo 8
Agora
, saímos do laço e fazemos o teste final:
se e
se
então encontramos o alvo no índice
.
Passo 9
O índice
no vetor de produtos corresponde a
. Logo, o sistema recupera e exibe os detalhes de
com preço R$ 70,00.
Resposta
Produto:
Preço: R$ 70,00
Preço: R$ 70,00