Номер числа Фибоначчи
Генерируем числа Фибоначчи, пока не достигнем или не превысим A.
Как к ней подойти
Разберитесь, как повторять действие, пока выполняется условие, и вовремя остановить цикл.
Цикл while продолжается, пока условие истинно. Продумайте, какое значение меняется на каждом шаге и почему цикл когда-нибудь завершится. Проверяйте как обычный ввод, так и случай, когда тело цикла выполняется ноль раз.
Последовательность не убывает и затем строго растёт. При превышении числа дальнейший поиск бесполезен. Для A=1 выбран допустимый индекс 1.
Проверьте перед запуском
- F(0)=0, F(1)=1, F(2)=1: для единицы индекс неоднозначен.
- Не используйте приближённую формулу с вещественными числами для проверки равенства.
Сравните свой подход
Ниже - готовое решение, другой способ, если он есть, и важные детали проверки.
Ваше принятое решение
Рекомендуемое решение: Два соседних числа
Последовательность не убывает и затем строго растёт. При превышении числа дальнейший поиск бесполезен. Для 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)²) бит.