Проверьте, является ли N номером Серии Фибоначчи, начиная с чисел a и b вместо 0 и 1

Question

Я хочу проверить, является ли данное число «N» частью ряда Фибоначчи, начиная с целых чисел «a» и «b». Когда a = 0 и b = 1, мы имеем уравнения 5 * N ^ 2 + 4 или 5 * N ^ 2 - 4, чтобы быть идеальным квадратом. Как мы получаем эту формулу? Кроме того, возможно ли вывести такие уравнения для других значений a и b?

Подход грубой силы - вычисление всех чисел в серии до N. Я хочу оптимизировать его дальше.

Пример: N = 13, a = 2, b = 4 Серия Фибоначчи: 2, 4, 6, 10, 16, ... Выход: невозможно

Answer 1

Согласно этой статье в Википедии вы можете определить, входит ли число в ряд Фибоначчи, поскольку при помещении этого числа в упрощенную формулу Бине нам нужно получить целое n.Итак, что нам нужно сделать, чтобы проверить, входит ли число в общий ряд Фибоначчи, - это создать собственную общую формулу Бине и упростить ее.В той же статье в Википедии вы можете найти эту общую формулу (спасибо @fjardon), теперь при ее упрощении вы получаете условие:

5 * x^2 +- 4 * (U1 - U0 * (1 - sqrt(5)) / 2) * (U0 * (1 + sqrt(5)) / 2 - U1)

Требуется быть идеальным квадратом.Когда U0 и U1 являются первым и вторым элементами в серии.

Различные подходы

В вашем случае "подход грубой силы" может не подходитьэто плохо.Мы знаем, что отношение рядов Фибоначчи последовательных чисел Фибоначчи сходится к золотому отношению, в общем ряду Фибоначчи это будет другое отношение.Это означает, что числа становятся экспоненциально большими.Поэтому, если мы выполняем итерации по ряду Фибоначчи, мы достигнем N в течение log (ratio) (N) итераций (при условии, что вы используете динамическое программирование для генерации ряда).Так что это будет примерно в логарифмическом времени.

Если вы хотите улучшить это, вы можете сгенерировать общую формулу, используя martix form , которая выполняет экспоненциальный поиск в порядкенайти свой номер.Временная сложность здесь немного сложнее, поскольку N - это число, а не его индекс, но оно будет O(log log N).