Легко Решено: 0 Процент решений: 0%

Lucas Numbers

Return the nth Lucas number, the Fibonacci-like sequence that starts 2, 1.

Чему вы научитесь

  • Compute a Fibonacci-like sequence
  • Use the right starting values
  • Avoid computing one term past the answer

Условие

Показать перевод

The Lucas numbers follow the same rule as the Fibonacci numbers, each term being the sum of the two before it, but they start differently: L(0) = 2 and L(1) = 1. The sequence goes 2, 1, 3, 4, 7, 11, 18, 29, …

Implement lucas_numbers(n).

Input

n: The index of the term, starting at 0.

Output

Return L(n).

Ограничения

0 ≤ n ≤ 90

Примеры

Пример 1
Ввод:
n = 6

Ожидаемый вывод:
expected = 18
Ввод:
long long n = 6;

Ожидаемый вывод:
long long expected = 18;
Ввод:
long n = 6;

Ожидаемый вывод:
long expected = 18;

Пояснение

The terms are 2, 1, 3, 4, 7, 11, 18, so L(6) = 18.

Пример 2
Ввод:
n = 0

Ожидаемый вывод:
expected = 2
Ввод:
long long n = 0;

Ожидаемый вывод:
long long expected = 2;
Ввод:
long n = 0;

Ожидаемый вывод:
long expected = 2;

Пояснение

The sequence starts with L(0) = 2.

Как подступиться

Сначала попробуйте сами, затем открывайте подсказки по одной.

Подсказка 1

Keep the current and next terms in two variables.

Подсказка 2

The only difference from Fibonacci is the start: 2 and 1.

Подсказка 3

For n = 90 the next term would not fit in 64 bits, so stop the loop at n.

Ожидаемая сложность

O(n) time, O(1) extra space

Ссылки

Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

Принятых решений пока нет. Решите задачу и займите первое место.

Учитесь у других

Решения сообщества

Пока нет опубликованных решений. Решите задание, чтобы поделиться первым.