Considere uma loja online que possui duas estruturas de dados relacionadas por índice:
  • Um vetor ordenado contendo os preços dos produtos:
\text { Preço }=[10,15,20,25,30,35,40,45,50,55,60,65,70]ç
  • Um vetor paralelo contendo os nomes ou IDs dos produtos:
\text { Produto }=\left[P_{1}, P_{2}, P_{3}, P_{4}, P_{5}, P_{6}, P_{7}, P_{8}, P_{9}, P_{10}, P_{11}, P_{12}, P_{13}\right]
O índice i corresponde ao mesmo produto em ambos os vetores, isto é, o produto P_{i} tem preço \operatorname{Preço}_{i}̧.
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
\text{Preço} = [10,15,20,25,30,35,40,45,50,55,60,65,70]ç
e um vetor paralelo de produtos
\text{Produto}=[P_{1},P_{2},\dots,P_{13}].
Queremos encontrar o produto cujo preço é exatamente R$ 70,00 usando busca de Fibonacci e, em seguida, exibir seus detalhes.

Passo 2

Definimos n=13. Calculamos a sequência de Fibonacci até o menor F_{k} tal que F_{k}\ge n:
F_1=1,\;F_2=1,\;F_3=2,\;F_4=3,\;F_5=5,\;F_6=8,\;F_7=13.
Aqui F_7=13\ge13, então tomamos k=7 e inicializamos o deslocamento \text{offset}=-1. Usamos indexação base zero (índices vão de 0 a 12).

Passo 3

Enquanto F_k>1 fazemos:
calcule
i = \min(\text{offset} + F_{k-2},\,n-1).
Na 1ª iteração: i=\min(-1+F_5,12)=\min(4,12)=4.
Comparamos Preço[4]=30ç com o alvo 70. Como 30<70, jogamos fora a parte esquerda e atualizamos
k \leftarrow k-1 =6,\quad \text{offset} \leftarrow 4.

Passo 4

2ª iteração: i=\min(4+F_4,12)=\min(4+3,12)=7. Preço[7]=45<70ç ⇒ atualizamos
k\leftarrow5,\quad \text{offset}\leftarrow7.

Passo 5

3ª iteração: i=\min(7+F_3,12)=\min(7+2,12)=9. Preço[9]=55<70ç
k\leftarrow4,\quad \text{offset}\leftarrow9.

Passo 6

4ª iteração: i=\min(9+F_2,12)=\min(9+1,12)=10. Preço[10]=60<70ç
k\leftarrow3,\quad \text{offset}\leftarrow10.

Passo 7

5ª iteração: i=\min(10+F_1,12)=\min(10+1,12)=11. Preço[11]=65<70ç
k\leftarrow2,\quad \text{offset}\leftarrow11.

Passo 8

Agora F_k=F_2=1\le1, saímos do laço e fazemos o teste final:
se F_{k-1}=F_1=1 e
Preço[\text{offset}+1]=Preço[12]=70,çç
então encontramos o alvo no índice 12.

Passo 9

O índice 12 no vetor de produtos corresponde a P_{13}. Logo, o sistema recupera e exibe os detalhes de P_{13} com preço R$ 70,00.

Resposta

Produto: P_{13}
Preço: R$ 70,00

Exercícios relacionados