Задача. Сколькими способами из группы в 17 человек можно сформировать 6 коалиций по 2 человека и 1 коалицию из 5 человек?

Решение. Требуется разбить множество из 17 человек на непересекающиеся и неупорядоченные группы людей. Откуда искомое число равно N(0 6 03,04,15,06,07,...,0 )= 17!

(2!)6(5!)16!1!

Задача. Сколькими способами можно разделить колоду из 36 карт пополам так, чтобы в каждой пачке было по два туза?

Решение. 4 туза можно разбить на JL - = 3 различные коалиции

(2!)22!

по две карты в каждой (неупорядоченные разбиения), т.е. только 3 способами можно разделить тузы пополам. Далее, каждая половина любого из этих трех разбиений тузов выполняет роль различных двух корзин , куда необходимо разложить пополам оставшиеся 32 карты. Разложение 32 оставшихся карт уже будет упорядоченным, так как корзины различные, число разложений равно 16! 16! Согласно правилу прямого произведения, общее число вариантов

41 321 3-321

колоду пополам .

V. lb! It)! 11)! Ш

1.11. Полиномиальная формула

Формула

(*, +х1+...+хкГ = х . ,*№ <* о ИД)

называется полиномиальной, где суммирование выполняется по всем решениям уравнения + л2 + + а = п в целых неотрицательных числах, я, 0, = 1, 2,..., к. Для доказательства выполним умножение

(.v, KV;+.. +.v. )(л-;-t-.v>-h.. +хк)...(х +

Чтобы привести подобные в полученном выражении, необходимо подсчитать количество одночленов видах 1 х 2.. .х к каждо-

1 2 К

го разбиения щ + п2 + ... +пк = п. Для получения же одночлена х [хп22...х кк необходимо выбрать щ в качестве множителя в щ

1.12. Бином Ньютона 19

скобках при раскрытии выражения (xj + х2 + ... хк)п. Это можно сделать С^1 способами. Из оставшихся п - л j не раскрытых скобок необходимо выбрать х2 в качестве множителя в п2 скобках. Это можно сделать Спп1п способами и т. д. Тогда количество одночленов х 1х 1.. .х к' при раскрытии выражения

(х, +х2+...+хк)(х1 + х2+...+хк)...(х{ +х2+...+хк)

п

Сбудет равно числу Qс- ...С\ , --- - упорядо-

1 i. к

ченных разбиений.

1.12. Бином Ньютона

Частный вид полиномиальной формулы (1.11.1):

ia + Ь) =ТС,какЬ - (1.12.1)

называется биномом Ньютона.

Рассмотрим несколько задач, в основе решения которых лежит бином Ньютона.

п

Задача 1. Доказать тождество £с* =2 .

Ш

Решение. Воспользуемся формулой (1.12.1) бинома Ньютона,

в которой положим а = 1 и Ъ = 1, тогда (1+1) = УСк -1* -1 -*.

(И

и

Задача 2. Доказать тождество £С* (/и-1) -*= /и .

Решение. Воспользуемся формулой (1.12.1), где положим а = 1 иЬ=т - 1.

111 ги

Задача 3. Доказать тождество YCn = £ с =2 *

Решение. Воспользуемся формулой (1.12.1), в которой положим а=1и* = тогда 0-1) = У(-1>А С* =0. Группируя положите-

льные и отрицательные члены равенства, установим

111 111 I 1 I л

С2* 1. Так как С2* 1 = С. =2 , то каж-

*=0 к=\ к=0 к=1 к=0

дая из сумм составляет половину числа 2 .

Задача 4. Доказать тождествоf]к -С* = /j2 -1.

Решение. Воспользуемся формулой (1.12.1), из которой, пола-

гая а = 1 и Ъ = получим + = £ С *хк Дифференцирование

последнего равенства дает n(\ + x) ~l = ]T/tС^хк~] Пусть = 1 ,

и

тогда л(1+1) = УЧ - С* 1 * 1 что доказывает искомое тождество.

Jt=0

1.13. Инверсии

Перестановки особенно важны при изучении алгоритмов сортировки, так как они служат для представления неупорядоченных исходных данных. Чтобы исследовать эффективность различных методов сортировки, нужно уметь подсчитывать число перестановок, которые вынуждают повторять некоторый шаг алгоритма определенное число раз.

Пусть (flj ,а2,.... ап ) - перестановка элементов множества (1, 2,..., п}. Если i < j, a fl; > щ, то пара (а,-, а;)называется инверсией перестановки. Например, перестановка 3142 имеет три инверсии (3, 1), (3, 2), (4, 2). Каждая инверсия - это пара элементов, нарушающих порядок ; следовательно, единственная перестановка, не содержащая инверсий, - это отсортированная перестановка (1, 2,..., л).

Таблицей инверсии перестановки (а{, а2,..., а„) называется последовательности где d - число элементов, больших j и расположенных левее/Другими словами, ау - число инверсий, у которых второй элемент равен/ Например, таблица инверсий перестановки 591826473 будет 23640221 0, поскольку 5 и 9 расположены левее 1; 5, 9, 8 - левее 2 и т. д. Всего 20 инверсий. По определению

О <d{ < п - 1, 0<d2<n-2,О 1, = 0.

1.14. Обратные перестановки

М. Холл установил, что таблица инверсий единственным образом определяет соответствующую перестановку. Из любой таблицы инверсий можно однозначно восстановить перестановку, которая порождает данную таблицу, путем последовательного определения относительного расположения элементов п - (в этом порядке). Например, перестановку, соответствующую таблице инверсий (2,3,6,4,0,2,2,1,0) = dddd-jd, можно построить следующим образом: выпишем число 9; так как d% = I, то 8 стоит правее Поскольку = то 7 стоит правее 8 и 9. Так как г/6 = 2, то 6 стоит правее двух уже выписанных чисел; таким образом, получили расположение 9,8,6,7. Припишем теперь 5 слева, потому что с/с = 0; помещаем 4 вслед за четырьмя из уже записанных чисел, 3 - после шести выписанных чисел (т. е. в правый конец) и получаем 5,9,8,6,4,7,3. Вставив аналогичным

образом 2 и 1, придем к перестановке (5,9,1,8,2,6,4,7,3).

Такое соответствие между перестановками и таблицами инверсий важно, потому что часто можно заменить задачу, сформулированную в терминах перестановок, эквивалентной ей задачей, сформулированной в терминах таблиц инверсий. Рассмотрим, например, еще раз вопрос: сколько существует перестановок множества Ответ должен быть равен числу всевозмож-

ных таблиц инверсий, а их легко пересчитать, так как можно выбрать п различными способами, можно независимо от выбрать п - 1 способами и т.д., dn - одним способом. Тогда различных таблиц инверсий п(п - 1)...1 = п\ . Таблицы инверсий пересчитать легко, потому что все независимые, в то время какэлементы перестановки должны все быть различными.

1.14. Обратные перестановки

Не следует путать инверсии перестановок с обратными перестановками. Пусть [. <ь..... ап - различные шары, индексы

которых свяжем с номерами шаров. Тогда исходное расположение шаров однозначно определяется тождественной перестановкойе = (1,2,..., и). Пустьп = (т^, jt2,..., кп) - произвольная перестановка номеров 1, л, где лА - номер шара на fc-м месте. Такая перестановка отвечает расположению шаров ак ,ак ,...,ап . Вспомним (см. п. 1.5), что перестановка

л = ( 2 * и| можетбытьзаписанавматричномвиде.Данная

форма записи позволяет рассматривать перестановку в качестве оператора, который заменяет старые номера шаров - верхняя строка матрицы - на новые номера - нижняя строка матрицы. Тогда результат двух последовательных изменений л = (я я2,..., л„) и ст = (щ, ст2,..., ст ) исходной последовательности 1,2,..., п номеров шаров можно рассматривать как операцию

умножения перестановок р = пс,= п : ... п

Упорядочим столбцы перестановки а в соответствии с переста-новкойл = (я1,я2,...,я ),т.е.ст=Г 1 J Ш - \

Тогда можно записать, что р=яа= 1 9 V % , 112 П 1 =

V4 2 лу у я, стл2 стк„ j

с.

2-\ ... л [ ... п

Этой перестановке отвечает

расположение шаров ар , aPiаРп где значение рд =стя - это

номер шара на месте.

Обратной к перестановке я = и называется пере-

становкая-1 /I2 ,= , х которая получает-\ 1 2 ... п J {.щ л2 ... пп f г

ся, если в исходной перестановке поменять местами строки, а затем упорядочить столбцы в возрастающем порядке по верхним элементам, т.е. я1 =(яГ1, п~21 ,...,п~ 1). Ясно, что последовательное

изменение порядка шаров согласно перестановкам л = (ль я2,..., л„) и обратной я-1 = (яГ1 приводит к исходному их рас-

положению, т.е. к тождественной перестановке

перестановке (5,9,1,8,2,6,4,7,3) будет перестановка (3,5,9,7,

1 * 8 А 91 таккя/.г59 182647 3\ (12345678 9 ) 1,6,8,4,2), >к|2 3 4 5 6 7 8 9J =з5 9 7 1 6 8 4 2/

Сортированную последовательность элементов перестановки л = (я1, я2,..., я ) можно получить, заполнив в цикле вектор еь е2,...,

far к =lto п do ея = пк или е[я J = я

1.14. Обратные перестановки

Ясно, что результирующие значения е{, е2,-, еп будут соответственно 1,2,...,п. В цикле каждый элемент пк встает на свое упорядоченное место ея (см. п.5.7). Подобным образом выполним заполнение элементов перестановки однако в

упорядоченное место элемента будем размещать его номер

в исходной перестановке я =

for к=\ to п do л:1 =кшш п~1[пк]=к.

Результирующий вектор будет обратной

перестановкой к я =

X. А. Роте впервые установил связь между обратными перестановками и инверсиями: обратная перестановка содержит ровно столько же инверсий, сколько исходная.

--Глава 2-=

Представление абстрактных объектов

Рассматривая решение задачи с абстрактной точки зрения, как правило, избегают каких бы то ни было предположений относительно того, как мы намерены автоматизировать ее решение.

В идеале структура вычислительной машины должна соответствовать естественной структуре задачи, однако это требование

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

2.1. Представление последовательностей

Любой заданный класс абстрактных объектов может иметь несколько возможных представлений, и выбор наилучшего из них решающим образом зависит от того, каким образом объект будет использован, а также от типа производимых над ним операций.

2.1.1. Смежное представление

В алгоритмах на дискретных структурах часто приходится встречаться с представлением конечных последовательностей и операциями с ними. С вычислительной точки зрения простейшим представлением конечной последовательности ... , является точный список ее членов, расположенных по порядку в смежных ячейках памяти. В языках высокого уровня - это одномерные, двухмерные и т. д. массивы данных. Наряду с очевидными преимуществами последовательное представление имеет и некоторые значительные недостатки. Смежное представление становится

лым, если требуется изменить последовательность путем включения новых и исключения имеющихся там элементов. Включение между SjH sj+1 нового элемента требует сдвигаSj+ j, Sj+2, ...,sn вправо на одну позицию; аналогично исключение 5, требует сдвига тех же элементов на одну позицию влево, как показано в алгоритме 2.1.

Алгоритм 2.1. Включение и исключение элементов при последовательном размещении

{Включипи. элемент z на i-e место }

п=п + 1;

for j-n- 1 to iby-l do sj+l = Sj, = z.

{Исключи/т элемент с i-го места } fori = i to n - I do Sj = sJ+l; n = n - 1.

В обоих случаях включение или удаление элементов при смежном представлении требует перемещения многих элементов. С точки зрения времени обработки такое перемещение элементов может оказаться дорогостоящим из-за сложности операций включения и удаления 0(п).

2.1.2. Характеристические векторы

Важной разновидностью смежного размещения является случай, когда такому представлению подвергается подпоследовательность sk ,sk ,...,sk некоторой основной последовательности В этом случае подпоследовательность можно представить более удобно, используя характеристический вектор - последовательность из нулей и единиц, где разряд равен единице, если принадлежит рассматриваемой подпоследовательности.

Например, для последовательности (1,2,3,4,5,6,7,8,9) характеристический вектор подпоследовательности чисел, кратных 3, имеет вид (0,0,1,0,0,1,0,0,1).

Характеристические векторы полезны в том случае, когда формирование нужной подпоследовательности вьтолняется путем последовательного удаления из основной последовательности элементов, которые не входят в подпоследовательность. Главное неудобство характеристических векторов состоит в том, что они не экономичны.

2.1.3. Связанное размещение

Неудобство включения и исключения элементов при смежном представлении происходит того, что порядок следования

элементов задается неявно требованием, чтобы смежные элементы последовательности находились в смежных ячейках памяти. В результате многие элементы последовательности во время включения или исключения должны передвигаться.

Если требование последовательного размещения элементов опущено, то операции включения и исключения можно выполнить без того, чтобы передвигать элементы. При любом размещении элементов необходимо сохранять информацию о способе их упорядочения. При связанном размещении последовательности V Sl,..., s каждому ставится в соответствие указатель / который указывает на следующую подобную пару элементов /(+) по списку. Вводится начальный указатель /0, который указывает на первый элемент последовательности. Последний указатель в списке является пустым или нулевым, это признак конца списка. Графическое представление связанного списка можно изобразить следующим образом:

Здесь каждый элемент связанного списка состоит из двух полей. В поле DATA размещен сам элемент последовательности, а в поле NEXT - указатель на следующий за ним элемент. Связанное представление последовательностей облегчает операции

включения и удаления элементов из списка. Например, для исключения второго элемента достаточно переустановить указатели NEXT(/,) = NEXT(/2). Графически это изображается следующим образом:

Чтобы в последовательность включить новый элемент после необходимо установить указатели: = и

= начальное значение указателя установлено на новый включаемый элемент. Графически включение нового элемента изображается так:

включения

осле включения

С помощью связанных распределений мы добились большей гибкости, но потеряли возможность работать с элементами последовательности как с массивами, когда по номеру можно непосредственно обратиться к элементу 5,. В связанном размещении такой возможности не существует, и доступ к элементам последовательности не является прямым и эффективным. Например, при поиске среднего элемента последовательности, даже

при известной ее длине, требуется просмотреть по связанному

списку половину последовательности. В алгоритмах 2.2 и 2.3 приводятся программы, реализованные на языках Pascal и С, связанного формирования списка элементов последовательности. В программы включены операции работы со списком: печать элементов списка, включение новых элементов в список и удаление элементов из списка.

Существуют различные модификации представления последовательностей в виде связанных списков. Следующие два примера позволят, при желании, читателю самостоятельно продолжить получение и других модификаций связанных распределений, отличных от приводимых ниже.

Циклическая форма представления позволяет эффективно возвращаться с последнего элемента списка к первому.

Рис. 2.1. Циклический список

Еще большая гибкость достигается, если использовать дважды связанный список, когда каждый элемент последовательности вместо одного имеет два связанных с ним указателя. В таком списке для любого элемента имеется мгновенный прямой доступ к

предыдущему и последующему элементам. Следует помнить, что