Дистанционная подготовка: Помогите.
Помогите.
от Никита Пушкин - Среда 30 Апрель 2014, 20:34
207. Последовательность из 0 и 1
  Почему ответом будет n+1 число Фибоначчи?
Re: Помогите.
от Никита Пушкин - Среда 30 Апрель 2014, 21:01
  Тем более, что это не так. Шестое число Фибоначчи — 8, а ответ на тест 5 — число 13. Получает, ответ — это n+2 число Фибоначчи.
Re: Помогите.
от Никита Пушкин - Среда 30 Апрель 2014, 21:29
  У меня еще вопрос. Вот я написал программу, а она не проходит первый тест. Что это за тест и почему он не проходит?
Re: Помогите.
от Peter Cherepanov - Пятница 2 Май 2014, 09:37
  Эту задачу можно протестировать полностью, так как при данных ограничениях возможно только 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)
Re: Помогите.
от Никита Пушкин - Пятница 2 Май 2014, 18:30
  Спасибо, Вы все очень толково расписали. Сдал задачу.