Комбинаторные алгоритмы для программистов



             

Другой метод доказательства


В предыдущем разделе непосредственно установлена связь между задачей Фибоначчи и комбинаторной задачей. Эту связь можно установить и иначе, непосредственно доказав, что число

T(n)
решений комбинаторной задачи удовлетворяет тому же рекуррентному соотношению
T(n + 1) = T(n) + T(n - 1),

(7.5)

что и числа Фибоначчи. В самом деле, возьмем любую

(n+1)
-последовательность нулей и единиц, удовлетворяющую условию, что никакие две единицы не идут подряд. Она может оканчиваться или на 0, или на 1. Если она оканчивается на 0, то, отбросив его, получим
n
-последовательность, удовлетворяющую нашему условию. Если взять любую
n
- последовательность нулей и единиц, в которой подряд не идут две единицы, и приписать к ней нуль, то получим
(n + 1)
-последовательность с тем же свойством. Таким образом доказано, что число последовательностей, оканчивающихся на нуль, равно
T(n)
.

Пусть теперь последовательность оканчивается на 1. Так как двух единиц подряд быть не может, то перед этой единицей стоит нуль. Иными словами, последовательность оканчивается на 01. Остающаяся же после отбрасывания 0 и 1

(n - 1)
-последовательность может быть любой, лишь бы в ней не шли подряд две единицы. Поэтому число последовательностей, оканчивающихся единицей, равно
T(n - 1)
. Но каждая последовательность оканчивается или на 0, или на 1. В силу правила суммы получаем, что
T(n + 1) = T(n) + T(n - 1)
.

Таким образом, получено то же самое рекуррентное соотношение. Отсюда еще не вытекает, что числа

T(n)
и
F(n)
совпадают.




Содержание  Назад  Вперед