Como obter os índices de uma subsequência de Fibonacci que está ordenada?

Question

Suponha que você receba um vetor de ordem \(n\) ordenado e você deseja checar se esse vetor contêm somente uma parte da série de fibonacci. Você deve retornar os valores dos índices do primeiro elemento e do último elemento da série de fibonacci que aparecem no vetor e pertence a série de fibonacci. Se o vetor não possuir uma subsequência da série de fibonacci, então retorne -1. Por exemplo, se o vetor for \([34, 55, 89, 144, \ldots, 2584]\), a função deve retornar \(10,19\). No caso do vetor \([34, 56, 89, 144, \ldots, 2584]\) ou \([34, 89, 144, \ldots, 2584]\), a função deve retornar -1. Qual a complexidade do algoritmo?

Answer 1

def indices_subsequencia_fibonacci(X):
    if (X[0] < 0):
        return -1
    n = len(X)
    fib1, fib2 = 0, 1
    indice_fib = 1

    while (X[0] >= fib1):
        if (X[0] == fib1):
            j = 0
            indice_fib_inicial = indice_fib
            while ((j < n) and (X[j]==fib1)):
                fib1, fib2, indice_fib = fib2, fib1+fib2, indice_fib+1
                j = j + 1

            if (j == n):
                return indice_fib_inicial, indice_fib-1
            else:
                return -1
        fib1, fib2, indice_fib = fib2, fib1+fib2, indice_fib+1

    return -1

if __name__ == '__main__':
    X1 = [34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584]
    print X1
    print indices_subsequencia_fibonacci(X1)

    X2 = [34, 56, 89, 144, 233, 377, 610, 987, 1597, 2584]
    print X2
    print indices_subsequencia_fibonacci(X2)

    X3 = [34, 89, 144, 233, 377, 610, 987, 1597, 2584]
    print X3
    print indices_subsequencia_fibonacci(X3)

Algum erro? Favor me avisar. Dúvidas e sugestões são sempre bem-vindos!

Comments

Saulo, aparentemente você não precisa do laço while. Você pode estimar o termo de interesse da série de fibonacci invertendo a solução da equação em diferenças dada pela sequencia de Fibonacci. Nesse caso, a complexidade é simplesmente O(n).

---

Nossa! É verdade! E a solução fica BEM mais elegante!

Answer 2

Solução usando gerador:

def fibonacci_generator(x1=0, x2=1):
    a, b = x1, x2
    while True:
        yield a
        a, b = b, a+b


def check(my_list):

    if len(my_list) == 0:
        return -1

    list_index = 0

    begin, end = -1, -1

    for (fib_index, fib_number) in enumerate(fibonacci_generator()):

        if list_index >= len(my_list):
            return begin + 1, end + 1

        my_number = my_list[list_index]

        if begin == -1:
            if fib_number < my_number:
                continue
            if fib_number == my_number:
                begin, end = fib_index, fib_index
                list_index += 1
                continue
            if fib_number > my_number:
                return -1
        else:
            if fib_number == my_number:
                end = fib_index
                list_index += 1
                continue
            if fib_number != my_number:
                return -1


listaTest = [34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584]
print(check(listaTest))