Связь и интернет Архив Программирование
   
Сделать стартовойСделать закладку            
   ПОИСК  
   
Главная / Алгоритмы / Математика / Комбинаторика и переборные задачи /
8  Perl
8  PHP
8  JavaScript
8  HTML
8  DHTML
8  XML
8  CSS
8  C / C++
8  Pascal и Delphi
8  Турбо Ассемблер
8  MySQL
8  CASE-технологии
8  Алгоритмы
8  Python
8  Обратная связь
8  Гостевая книга
Новости о мире


Подсчитать количество слов длины К из данных N букв, не содержащих данное подслово - Программирование от RIN.RU
Подсчитать количество слов длины К из данных N букв, не содержащих данное подслово

Данная задача, в общем-то не требует особого алгоритма. Я помещаю здесь ее решение, чтобы показать, как можно рассуждать, если не требуется напечатать все слова, а только узнать их число.


Простой случай


Элементы исходной последовательности-алфавита различны, слово зависит от порядка букв. Если в исходной последовательности есть одинаковые буквы, то надо будет кое-что подкорректировать (их-то порядок не важен будет в слове, если стоят рядом). Это сделаем потом. Каждый элемент алфавита мы можем использовать в слове один раз.


По идее всего слов размера К из 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  Обсудить в чате

 
  
  
    Copyright ©  RIN 2003 - 2004      * Обратная связь