RU
EN
RU
EN
🎉 Поздравляем! 🎉
Ты отлично справился с задачей! Это был непростой вызов, но ты нашёл правильное решение. Ты на шаг ближе к мастерству в программировании! Продолжай в том же духе, ведь каждый пройденный этап делает тебя ещё сильнее.
Занятие 5. Цикл while
Уровень сложности:
Задача«Леонардо Пизанский»
Великий математик Леонардо Пизанский, известный под псевдонимом Фибоначчи, оставил нам в наследие знаменитую числовую последовательность. Каждый её элемент, начиная с третьего, является суммой двух предыдущих.
Последовательность Фибоначчи определяется так:
φ₀ = 0
φ₁ = 1
φₙ = φₙ₋₁ + φₙ₋₂ для n > 1
Начало последовательности выглядит так: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
Вам дано натуральное число A. Ваша задача — определить, является ли это число частью последовательности Фибоначчи. Если да, то выведите его порядковый номер n (индекс), такой что φn = A. Если число 1 встречается в последовательности, считать, что его индекс равен 1. Если число A не является числом Фибоначчи, выведите -1.
Формат ввода
Вводится одно целое неотрицательное число A (0 ≤ A ≤ 10¹⁸).
Формат Вывода
Выведите одно целое число: порядковый номер n, для которого φn = A. Если такого номера не существует, выведите -1.
Пример
Ввод
55
Вывод
10
Подсказка
Тут подсказки не будет, решай сам!
main.py
Тест 1
Тест 2
Тест 3
Тест 4
Тест 5
Тест 6
Тест 7
Тест 8
Тест 9
Тест 10
Решение разработчика
# Получаем на вход число A
a = int(input())
# Обрабатываем частный случай для 0
if a == 0:
print(0)
else:
# Инициализируем первые два члена последовательности и их индекс n.
# f0 соответствует φ(n-1), f1 соответствует φ(n)
f0, f1 = 0, 1
n = 1
# Используем цикл while для генерации чисел Фибоначчи,
# пока текущее число f1 меньше искомого числа a.
while f1 < a:
# Это "магия" Python для параллельного присваивания.
# Новое значение f0 становится старым f1,
# а новое f1 становится суммой старых f0 и f1.
# Это эквивалентно:
# temp = f1
# f1 = f0 + f1
# f0 = temp
f0, f1 = f1, f0 + f1
n += 1
# После выхода из цикла проверяем, почему он завершился.
# Если f1 равно a, значит, мы нашли число.
if f1 == a:
print(n)
# Если f1 стало больше a, значит, мы "проскочили" искомое число,
# и его нет в последовательности.
else:
print(-1)
