Консультации

Помогите.

Помогите.

от Никита Пушкин -
Number of replies: 4
Почему ответом будет n+1 число Фибоначчи?
In reply to Никита Пушкин

Re: Помогите.

от Никита Пушкин -
Тем более, что это не так. Шестое число Фибоначчи — 8, а ответ на тест 5 — число 13. Получает, ответ — это n+2 число Фибоначчи.
In reply to Никита Пушкин

Re: Помогите.

от Peter Cherepanov -
Эту задачу можно протестировать полностью, так как при данных ограничениях возможно только 100 тестов. Итак,

Существуют 2 последовательности длины 1: 0 и 1
Существуют 3 последовательности длины 2: Последовательность 11 запрещена по условию.

Пусть количество последовательностей длины n равно F(n). Если последний элемент равен 0, то предыущие n-1 элементов могут быть любой правильной последовательностью. Их -- F(n-1).

Если последний элемент равен 1, то предпоследний элемент должен быть равен 0, а остальные элементы образуют правильную последовательность длины n-2. Их -- F(n-2)

Итого:
F(1) = 2
F(2) = 3
F(n) = F(n-1) + F(n-2)