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

[wpoms.]

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

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

Comments

[Adjirranirr]

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

int __fastcall evil (int z) {
	__asm {	
		xor		eax, eax
		mov		ebx, 7h
		mov		edx, 1	
		shl		edx, cl
		xchg		ecx, edx
$start:			
		mov		edx, ecx
		jmp		$go
$found:
		inc		eax		
		loop		$start
		jmp		$end
$go:
		mov		esi, edx
		and		edx, ebx
		cmp		edx, ebx
		mov		edx, esi
		je		$found
		shr		edx, 1
		jnz		$go
		loop		$start
$end:
	}
}

#include <stdio.h>

void main () {
	_iobuf *f;
	freopen_s(&f, "out.txt", "w", &__iob_func()[1]);
	int k = 1;
	for (int i = 0; i <= 31; i++, k <<= 1) {
		printf_s ("%d ", k - evil(i));
	}
	fclose (f);
}

Вывод:

1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 5768 10609 19513 35890 66012 121415 223317 410744 755476 1389537 2555757 4700770 8646064 15902591 29249425 53798080 98950096 181997601 

По решению. Пусть `\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`.