суббота, 30 января 2010 г.

Задача “Двоичные числа” (Рекуррентное соотношение с одним параметром )

Условие задачи: ссылка
Основная идея: Чтобы прочувствовать решение задачи предлагаю начать с более простого случая, когда K=2. Обозначим K(n) – количество n битных чисел без 2-ых подряд идущих единиц. K(1) = 2 – факт очевидный. Найдем решение для n=2. На вторую позицию можно поставить либо ноль, либо единицу. Ноль можно ставить смело, а вот единица может образовать запрещенную комбинацию, если на первой позиции также стояла единица. Проанализируем таблицу:

комбинация количество
*0 K(1)
01 1
11 0

Делаем вывод, что K(2) = K(1) + 1. Двигаемся дальше. По такой же схеме получают таблицу для n=3

комбинация количество
**0 K(2)
*01 K(1)
*11 0


K(3) = K(2)+K(1). Придерживаясь этой логики получаем универсальную формулу K(n) = K(n-1) + K(n-2). Если обозначить K(0) = 1, то терминальное условие для K(2) можно отдельно не прописывать.
Двигаемся дальше. Рассмотрим решение первоначальной задачи для K=3. Ход рассуждений не меняется. На первую позицию смело ставим ноль и единицу, значит K(1) = 2, на вторую позицию можно также смело ставить и ноль и единицу, т.е. запрещенная комбинация из 3 подряд единиц не может быть достигнута на текущем шаге , значит K(2) = K(1) + K(1) = 2K(1)=4. Первое слагаемое – это количество решений, если поставим на вторую позицию ноль, второе слагаемое – если поставим единицу. Как быть если n = 3 и k=3? Очевидно, что запрещенная комбинация может быть только одна. Общее количество всех комбинаций будет 8, следовательно K(3) = 2K(2)-1. Мы пришли к самому интересному: n=4, k=3. Рисуем таблицу

комбинация количество
***0 K(3)
**01 K(2)
**11 0
*011 K(1)
*111 0

Поясню, почему в комбинации “**11” стоит 0. Эта комбинация является общим случаем комбинаций “*011” и “*111”, которые рассмотрены в таблице.
Получили K(4) = K(3)+K(2)+K(1). Для общего случая имеем K(n)=сумма K(i) для i из [n-k,n-1] (Когда прикручу Tex, формулы обретут свои заслуженные очертания). Не забываем про терминальные условия: если i<n, то K(i) = 2^i; если i=1, то K(i) = 2^i-1. Во всех остальных случаях работает наша формула.
Исходный код:  здесь

2 комментария:

  1. Спасибо большое за подробное объяснение. Тут можно получить и более простую рекуррентную формулу: K(i)=2*K(i-1)-K(i-k-1)

    ОтветитьУдалить