Considere uma lista A de tal modo que o
- Vetor A é ordenado crescente
.
- Valor alvo
.
Queremos determinar um índice
tal que
, ou concluir que tal índice não existe. Para isto
(a) Defina a sequência de Fibonacci:
(b) Seja
o menor inteiro tal que
.
(c) Inicialize:
(d) Enquanto
, repita:
i. Defina:
ii. Compare
:
- Se
, então:
- Se
, então:
- Se
, então o índice procurado é
.
(e) Após o laço acima, se:
então o índice procurado é
.
(f) Caso contrário, conclui-se que
.
Utilizando o algoritmo descrito acima, determine o índice referente ao valor 72 na lista
(a) Defina a sequência de Fibonacci:
(c) Inicialize:
i. Defina:
(e) Após o laço acima, se:
(f) Caso contrário, conclui-se que
Passo 1
O enunciado pede localizar o valor
em um vetor ordenado usando busca Fibonacci. O conteúdo envolve gerar a sequência de Fibonacci, determinar o menor
tal que
, manter três variáveis
,
,
e um deslocamento
, 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
e a sequência de Fibonacci até achar
com
. Temos
. A sequência é
O menor
com
é
.
Passo 3
Inicializar
Passo 4
Primeira iteração
:
Calcular
Calcular
Comparar
com
. Como
, atualizar
Passo 5
Segunda iteração
:
Calcular
Calcular
Comparar
com
. Como
, atualizar
Passo 6
Terceira iteração
:
Calcular
Calcular
Comparar
com
. Como
, atualizar
Passo 7
Quarta iteração
:
Calcular
Calcular
Comparar
com
. Como
, atualizar
Passo 8
Quinta iteração
:
Calcular
Calcular
Comparar
com
. Como
, encontramos o índice procurado
.
Resposta
18