Номер числа Фибоначчи
Вы решили задачу. Теперь можно сравнить подходы.
Генерируем числа Фибоначчи, пока не достигнем или не превысим A.
Авторский разбор для локальной версии на основе условия задачи. Это не выгрузка чужих посылок и не официальное решение исходного сайта.
Ваше принятое решение
Рекомендуемое решение: Два соседних числа
Последовательность не убывает и затем строго растёт. При превышении числа дальнейший поиск бесполезен. Для A=1 выбран допустимый индекс 1.
a = int(input())
previous, current = 0, 1
index = 1
while current < a:
previous, current = current, previous + current
index += 1
print(index if current == a else -1)
Время: O(log A) сложений больших целых. Память: O(log A) бит для нескольких чисел.
Другой способ: Таблица чисел с поиском
Сохраняем полученные значения и находим индекс в таблице. Память больше, зато таблицу можно использовать для других запросов.
a = int(input())
fib = [0, 1]
while fib[-1] < a:
fib.append(fib[-1] + fib[-2])
print(fib.index(a) if fib[-1] == a else -1)
Время: O(log A) сложений и сравнений. Память: O(log A) чисел, суммарно O((log A)²) бит.
На что обратить внимание
- F(0)=0, F(1)=1, F(2)=1: для единицы индекс неоднозначен.
- Не используйте приближённую формулу с вещественными числами для проверки равенства.
Рекомендация учитывает сложность и читаемость для этой задачи. Единственного самого быстрого решения для всех размеров входа и всех компьютеров может не быть.