Нахождение всех вариантов составления массива из последовательностей с общим числом повторяющихся элементов k
Предположим, мы используем только 1 и 0 при составлении массива длины N. Нужно найти количество способов разместить k единиц так, чтобы они входили как последовательности с длиной большей двух. Пример подходящих последовательностей для N = 6, k = 3. 001011 - не подходит, так как присутствует изолированная единица. 000111 - подходит
Ответы (2 шт):
Сначала нужно создать массив из нулей длиной N. Затем в цикле разместить k единиц с помощью счетчика. На каждой итерации цикла увеличиваем счетчик, пока он не станет равен N - 1, чтобы убедиться, что последовательность из единиц имеет длину больше 2
Пусть f(n, k) искомое число. Тогда
f(n, k) = f(n-1, k) + f(n-3, k-2) + (n-4, k-3) + f(n-5, k-4) + ... + f(n-(n-3), k-(n-4)) + f(n-(n-2), k-(n-3)) + f(n-(n-1), k-(n-2)) + f(n-n, k-(n-1)) + f(n-n, k-n).
Формулы выводится из рассмотрения того как могут быть устроены старшие цифры последовательности. Рядом с шаблоном строки приведено количество строк соответствующих шаблону:
шаблон число вариантов шаблона 0XXXXX...XX - f(n-1 , k ) 110XXXX..XX - f(n-3 , k-2 ) 1110XXX..XX - f(n-4 , k-3 ) 11110XX..XX - f(n-5 , k-4 ) ... 11...110XXX - f(n-(n-3), k-(n-4)) 11...1110XX - f(n-(n-2), k-(n-3)) 11...11110X - f(n-(n-1), k-(n-2)) 11...111110 - f(n-n , k-(n-1)) 11...111111 - f(n-n , k-n )
Чтобы формула и таблица хорошо работали нужно доопределить f для маленьких k и n:
f(n, 0) = 1, f(n, k<0) = 0, f(n<0, k) = 0.