Нужно найти количество всех последовательностей из "0" и "1" длины N, таких, что ни какие две еденицы не стоят рядом.
Во входном текстовом файле число N.
В выходной файл вывести количество таких последовательностей.
Ещё одна задачка...
-
noname00.pas
Re: Ещё одна задачка...
Круто... 3 просмотра 
Ладно... А решать нужно было так.
Пусть F(X) - количество таких последовательностей длины X.
Пусть мы знаем F(X), для всех X < N, тогда как нам выразить F(N) через такие F(X)
У нас есть некоторая последовательность длины N. Если на первом месте стоит 0, то таких последовательностей F(N - 1).
А если на первом месте стоит 1, то на втором 1 стоит 0 (по условию). И таких последовательностей F(N - 2)
Получили: F(X) = F(X - 1) + F(X - 2)
F(1) = 2
F(2) = 3
А теперь просто вычисляем последовательно все F(X) для X от 3 до N.
Ладно... А решать нужно было так.
Пусть F(X) - количество таких последовательностей длины X.
Пусть мы знаем F(X), для всех X < N, тогда как нам выразить F(N) через такие F(X)
У нас есть некоторая последовательность длины N. Если на первом месте стоит 0, то таких последовательностей F(N - 1).
А если на первом месте стоит 1, то на втором 1 стоит 0 (по условию). И таких последовательностей F(N - 2)
Получили: F(X) = F(X - 1) + F(X - 2)
F(1) = 2
F(2) = 3
А теперь просто вычисляем последовательно все F(X) для X от 3 до N.