Considere uma lista A de tal modo que o
  • Vetor A é ordenado crescente A=\left(a_{0}, a_{1}, \ldots, a_{n-1}\right) \in \mathbb{R}^{n}.
  • Valor alvo x \in \mathbb{R}.
Queremos determinar um índice i \in\{0,1, \ldots, n-1\} tal que a_{i}=x, ou concluir que tal índice não existe. Para isto
(a) Defina a sequência de Fibonacci:
F_{0}=0, \quad F_{1}=1, \quad F_{k}=F_{k-1}+F_{k-2} \quad \text { para } k \geq 2 .
(b) Seja m o menor inteiro tal que F_{m} \geq n.
(c) Inicialize:
f \leftarrow F_{m}, \quad f_{1} \leftarrow F_{m-1}, \quad f_{2} \leftarrow F_{m-2}, \quad o \leftarrow-1 .
(d) Enquanto f>1, repita:
i. Defina:
i \leftarrow \min \left(o+f_{2}, n-1\right) .
ii. Compare x \operatorname{com} a_{i} :
  • Se x>a_{i}, então:
f \leftarrow f_{1}, \quad f_{1} \leftarrow f_{2}, \quad f_{2} \leftarrow f-f_{1}, \quad o \leftarrow i .
  • Se x<a_{i}, então:
f \leftarrow f_{2}, \quad f_{1} \leftarrow f_{1}-f_{2}, \quad f_{2} \leftarrow f-f_{1} .
  • Se x=a_{i}, então o índice procurado é i.
    (e) Após o laço acima, se:
f_{1}=1, \quad o+1<n, \quad \text { e } \quad a_{o+1}=x,
então o índice procurado é o+1.
(f) Caso contrário, conclui-se que x \notin A.
Utilizando o algoritmo descrito acima, determine o índice referente ao valor 72 na lista
12,17,24,25,28,29,32,35,41,47,52,58,59,62,64,65,69,70,72,85,86,96,98,100,103,110

Passo 1

O enunciado pede localizar o valor 72 em um vetor ordenado usando busca Fibonacci. O conteúdo envolve gerar a sequência de Fibonacci, determinar o menor m tal que F_m \ge n, manter três variáveis f, f_1, f_2 e um deslocamento o, e iterar reduzindo o intervalo pelo deslocamento dado pelos números de Fibonacci até encontrar o elemento ou concluir que ele não existe.

Passo 2

Calcular o tamanho do vetor n e a sequência de Fibonacci até achar m com F_m \ge n. Temos n=26. A sequência é
F_0=0,\;F_1=1,\;F_2=1,\;F_3=2,\;F_4=3,\;F_5=5,\;F_6=8,\;F_7=13,\;F_8=21,\;F_9=34.
O menor m com F_m\ge 26 é m=9.

Passo 3

Inicializar
f \leftarrow F_9 = 34,\quad f_1 \leftarrow F_8 = 21,\quad f_2 \leftarrow F_7 = 13,\quad o \leftarrow -1.

Passo 4

Primeira iteração f=34>1:
Calcular
i = \min(o + f_2,\;n-1) = \min(-1 + 13,\;25) = 12.
Comparar x=72 com a_{12}=59. Como 72>59, atualizar
f \leftarrow f_1 = 21,\quad f_1 \leftarrow f_2 = 13,\quad f_2 \leftarrow f - f_1 = 21 - 13 = 8,\quad o \leftarrow 12.

Passo 5

Segunda iteração f=21>1:
Calcular
i = \min(o + f_2,\;25) = \min(12 + 8,\;25) = 20.
Comparar x=72 com a_{20}=86. Como 72<86, atualizar
f \leftarrow f_2 = 8,\quad f_1 \leftarrow f_1 - f_2 = 13 - 8 = 5,\quad f_2 \leftarrow f - f_1 = 8 - 5 = 3.

Passo 6

Terceira iteração f=8>1:
Calcular
i = \min(12 + 3,\;25) = 15.
Comparar x=72 com a_{15}=65. Como 72>65, atualizar
f \leftarrow f_1 = 5,\quad f_1 \leftarrow f_2 = 3,\quad f_2 \leftarrow f - f_1 = 5 - 3 = 2,\quad o \leftarrow 15.

Passo 7

Quarta iteração f=5>1:
Calcular
i = \min(15 + 2,\;25) = 17.
Comparar x=72 com a_{17}=70. Como 72>70, atualizar
f \leftarrow f_1 = 3,\quad f_1 \leftarrow f_2 = 2,\quad f_2 \leftarrow f - f_1 = 3 - 2 = 1,\quad o \leftarrow 17.

Passo 8

Quinta iteração f=3>1:
Calcular
i = \min(17 + 1,\;25) = 18.
Comparar x=72 com a_{18}=72. Como 72=a_{18}, encontramos o índice procurado i=18.

Resposta

18

Exercícios relacionados