18:46 

Злые множества

wpoms.
Step by step ...

Множество, состоящее из натуральных чисел, назовем злым, если в нем не содержится трех последовательных чисел. Будем рассматривать пустое множество, которое не содержит элементов, как злое множество. Найдите количество злых подмножеств множества `{1,2,3,4,5,6,7,8,9,10}`.



@темы: Комбинаторика

Комментарии
2013-09-24 в 20:05 

Adjirranirr
Только дурак нуждается в порядке — гений господствует над хаосом.
Каждому подмножеству множества `{i}_{i = 1}^{N}` поставим в соответствие число `k` такое, что если в подмножестве содержится число `i`, то `i`-й бит числа `k` равен единице, и равен нулю в противном случае. Таким образом, искомых подмножеств ровно столько же, сколько чисел двоичной длины `N`, в двоичной записи которых не встречаются три подряд идущие единицы. Таких чисел всего... (VS C++ 2012, оптимизация кода по скорости выполнения, /O2)

Вывод:


По решению. Пусть `\text{evil}(N)` — искомое количество злых подмножеств.
Из них злых подмножеств, не содержащих число `N`, `\text{evil}(N - 1)`, содержащих `N`, и не содержащих `N - 1`, `\text{evil}(N - 2)`, содержащих `N` и `N - 1`, и не содержащих `N - 2`, `\text{evil}(N - 3)`. Это, очевидно, все злые подмножества, поэтому `\text{evil}(N) = \text{evil}(N - 1) + \text{evil}(N - 2) + \text{evil}(N - 3)`. При этом, `\text{evil}(0) = 1,\ \text{evil}(1) = 2,\ \text{evil}(2) = 4`, и (мне считать было лень, беру сразу готовый ответ =)) `\text{evil}(10) = 504`.

   

Не решается алгебра/высшая математика?.. ПОМОЖЕМ!

главная