Числа Люка строятся по тому же правилу, что и числа Фибоначчи (каждый член равен сумме двух предыдущих), но начинаются по-другому: L(0) = 2 и L(1) = 1. Последовательность выглядит так: 2, 1, 3, 4, 7, 11, 18, 29, …
Реализуйте lucas_numbers(n).
Входные данные
n: номер члена, начиная с 0.
Выходные данные
Верните L(n).
Ограничения
0 ≤ n ≤ 90
Примеры
Ввод:
n = 6
Ожидаемый вывод:
expected = 18
Ввод:
long long n = 6;
Ожидаемый вывод:
long long expected = 18;
Ввод:
long n = 6;
Ожидаемый вывод:
long expected = 18;
Пояснение
Члены последовательности: 2, 1, 3, 4, 7, 11, 18, поэтому L(6) = 18.
Ввод:
n = 0
Ожидаемый вывод:
expected = 2
Ввод:
long long n = 0;
Ожидаемый вывод:
long long expected = 2;
Ввод:
long n = 0;
Ожидаемый вывод:
long expected = 2;
Пояснение
Последовательность начинается с L(0) = 2.
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Храните текущий и следующий члены в двух переменных.
Подсказка 2
Единственное отличие от Фибоначчи в начале: 2 и 1.
Подсказка 3
При n = 90 следующий член уже не поместится в 64 бита, поэтому останавливайте цикл на n.
Ожидаемая сложность
время O(n), доп. память O(1)
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.