Данная задача, в общем-то не требует особого алгоритма. Я помещаю здесь ее решение, чтобы показать, как можно рассуждать, если не требуется напечатать все слова, а только узнать их число. Простой случай Элементы исходной последовательности-алфавита различны, слово зависит от порядка букв. Если в исходной последовательности есть одинаковые буквы, то надо будет кое-что подкорректировать (их-то порядок не важен будет в слове, если стоят рядом). Это сделаем потом. Каждый элемент алфавита мы можем использовать в слове один раз. По идее всего слов размера К из N букв будет... хмм... из 1-й буквы N возможных из двух N2... - для каждой первой буквы N возможных слов... в общем из К -> (1)        Nk. Из этого надо вычесть все последовательности, содержащие данную подпоследовательность. Сколько таких? Хмм... Што там у нас было на теорвере... Вай мозги не работают :(... Пусть длина плохой подпоследовательности m. Ищем все подпоследовательности длины к с фикс. частью длины m. Пусть фикс. часть в начале <--фиксированная часть слова--><--можем менять--> m букв k-m Возможностей для изменения - n^(k-m). Далее можно сдвинуть k-m раз вправо сию фикс. часть, получив таким образом еще (k-m)*n^(k-m) слов. Тогда всего возможно (2)       (k-m+1)*n^(k-m) слов длины К из Н букв, содержащих данную подпоследовательность длины м. Вычитаем (2) из (1) - получаем искомое число. Сложный случай Если же есть одинаковые буквы, то подсчет будет посложнее. Тебе понадобится подсчитать количество групп одинаковых букв и их количество в каждой (например, 3 буквы н и 2 буквы а в исходной последовательности - это 2 группы: по 3 и 2 элемента), затем для простоты сначала получить число (В)   -   ВСЕХ подпоследовательностей из К букв содержащих первую группу - то есть в которых она фиксирована. - поделить это число на число комбинаций элементов в группе - тогда увидишь число РАЗЛИЧНЫХ таких подпоследовательностей (то есть различных слов), вычесть это число РАЗЛИЧНЫХ из числа (В) ВСЕХ с первой группой - получили лишние слова, а затем вычесть результат из (1) - вообще всех слов. И так для всех групп. Окончательно получим нечто меньшее nk - число ВСЕХ РАЗЛИЧНЫХ слов из К букв N-буквенной последовательности-алфавита. Аналогичным образом поступить с числом слов, содержащих плохую подпоследовательность, превратив это число в число РАЗЛИЧНЫХ слов. И вычесть, как и в простом случае это число, уже меньшее (2) из всех чисел (1). Возможно, такое решение, где все подсчитывается отдельно несколько неоптимально, но оно просто, очевидно, а, главное, должно работать.  8  Комментарии к статье  8 8  Обсудить в чате