Читаем Чистый код. Создание, анализ и рефакторинг полностью

Вычисление возможных вариантов упорядочения

Из сообщения электронной почты, отправленного Дядюшкой Бобом Бретту:

При N шагов и T потоков общее количество в итоговой последовательности шагов равно T * N. Перед каждым шагом происходит переключение контекста, в ходе которого производится выбор между T потоками. Каждый путь может быть представлен в виде последовательности цифр, обозначающей переключение контекстов. Так, для шагов A и B с потоками 1 и 2 возможны шесть путей: 1122, 1212, 1221, 2112, 2121 и 2211. Если использовать в записи обозначения шагов, мы получаем A1B1A2B2, A1A2B1B2, A1A2B2B1, A2A1B1B2, A2A1B2B1 и A2B2A1B1. Для трех потоков последовательность вариантов имеет вид 112233, 112323, 113223, 113232, 112233, 121233, 121323, 121332, 123132, 123123, . . . .

Одно из свойств этих строк заключается в том, что каждый поток должен присутствовать в строке в N экземплярах. Таким образом, строка 111111 невозможна, потому что она содержит шесть экземпляров 1 и нуль экземпляров 2 и 3.

Итак, нам нужно сгенерировать перестановки из N цифр 1, N цифр 2… и N цифр T. Искомое число равно числу перестановок из N * T объектов, то есть (N * T)!, но с удалением всех дубликатов. Таким образом, задача заключается в том, чтобы подсчитать дубликаты и вычесть их количество из (N * T )!.

Сколько дубликатов содержит серия для двух шагов и двух потоков? Каждая строка из четырех цифр состоит из двух 1 и двух 2. Цифры каждой пары можно поменять местами без изменения смысла строки. Мы можем переставить две цифры 1 и/или две цифры 2. Таким образом, каждая строка существует в четырех изоморфных версиях; это означает, что у каждой строки имеются три дубликата. Три варианта из четырех повторяются, то есть только одна перестановка из четырех НЕ ЯВЛЯЕТСЯ дубликатом. 4! * 0.25 = 6. Похоже, наша схема рассуждений работает.

Как вычислить количество дубликатов в общем случае? Для N = 2 и T = 2 можно переставить 1 и/или 2. Для N = 2 и T = 3 можно переставить 1, 2, 3, 1 и 2, 1 и 3 или 2 и 3. Количество вариантов равно количеству перестановок N. Допустим, существует P разных перестановок N. Количество разных вариантов размещения этих перестановок равно P**T.

Таким образом, количество возможных изоморфных версий равно N!**T. Соответственно, количество путей равно (T*N)!/(N!**T). Для исходного случая T = 2, N = 2 мы получаем 6 (24/4).

Для N = 2 и T = 3 количество путей равно 720/8 = 90.

Для N = 3 и T = 3 получается 9!/6^3 = 1680.

Перейти на страницу:

Все книги серии Библиотека программиста

Программист-фанатик
Программист-фанатик

В этой книге вы не найдете описания конкретных технологий, алгоритмов и языков программирования — ценность ее не в этом. Она представляет собой сборник практических советов и рекомендаций, касающихся ситуаций, с которыми порой сталкивается любой разработчик: отсутствие мотивации, выбор приоритетов, психология программирования, отношения с руководством и коллегами и многие другие. Подобные знания обычно приходят лишь в результате многолетнего опыта реальной работы. По большому счету перед вами — ярко и увлекательно написанное руководство, которое поможет быстро сделать карьеру в индустрии разработки ПО любому, кто поставил себе такую цель. Конечно, опытные программисты могут найти некоторые идеи автора достаточно очевидными, но и для таких найдутся темы, которые позволят пересмотреть устоявшиеся взгляды и выйти на новый уровень мастерства. Для тех же, кто только в самом начале своего пути как разработчика, чтение данной книги, несомненно, откроет широчайшие перспективы. Издательство выражает благодарность Шувалову А. В. и Курышеву А. И. за помощь в работе над книгой.

Чед Фаулер

Программирование, программы, базы данных / Программирование / Книги по IT

Похожие книги

1С: Бухгалтерия 8 с нуля
1С: Бухгалтерия 8 с нуля

Книга содержит полное описание приемов и методов работы с программой 1С:Бухгалтерия 8. Рассматривается автоматизация всех основных участков бухгалтерии: учет наличных и безналичных денежных средств, основных средств и НМА, прихода и расхода товарно-материальных ценностей, зарплаты, производства. Описано, как вводить исходные данные, заполнять справочники и каталоги, работать с первичными документами, проводить их по учету, формировать разнообразные отчеты, выводить данные на печать, настраивать программу и использовать ее сервисные функции. Каждый урок содержит подробное описание рассматриваемой темы с детальным разбором и иллюстрированием всех этапов.Для широкого круга пользователей.

Алексей Анатольевич Гладкий

Программирование, программы, базы данных / Программное обеспечение / Бухучет и аудит / Финансы и бизнес / Книги по IT / Словари и Энциклопедии
1С: Управление торговлей 8.2
1С: Управление торговлей 8.2

Современные торговые предприятия предлагают своим клиентам широчайший ассортимент товаров, который исчисляется тысячами и десятками тысяч наименований. Причем многие позиции могут реализовываться на разных условиях: предоплата, отсрочка платежи, скидка, наценка, объем партии, и т.д. Клиенты зачастую делятся на категории – VIP-клиент, обычный клиент, постоянный клиент, мелкооптовый клиент, и т.д. Товарные позиции могут комплектоваться и разукомплектовываться, многие товары подлежат обязательной сертификации и гигиеническим исследованиям, некондиционные позиции необходимо списывать, на складах периодически должна проводиться инвентаризация, каждая компания должна иметь свою маркетинговую политику и т.д., вообщем – современное торговое предприятие представляет живой организм, находящийся в постоянном движении.Очевидно, что вся эта кипучая деятельность требует автоматизации. Для решения этой задачи существуют специальные программные средства, и в этой книге мы познакомим вам с самым популярным продуктом, предназначенным для автоматизации деятельности торгового предприятия – «1С Управление торговлей», которое реализовано на новейшей технологической платформе версии 1С 8.2.

Алексей Анатольевич Гладкий

Финансы / Программирование, программы, базы данных