По вопросам приобретения обращаться
 Скачать 5.46 Mb.
|
|
Пятая задача. По размещению определить его номер (раз- мещения упорядочены в лексикографическом порядке). Поясним идею решения на примере. Дано размещение 345. Количество свободных элементов, меньших 3, равно 2 (12*2=24). Количество свободных номеров, меньших 4, также 2 — 24+3*2=30. И наконец, меньших пяти, также 2. Ответ: 12*2+3*2+1*2=32. Function {*Используется процедура вычисления количества Var LongInt; Of {*Множество элементов Begin = [] ; =0 ; For i : = 1 To Do {*i - номер позиции {*Счетчик числа незанятых элементов.*} For A [ i ] - 1 Do If Not (j In ws) Then (num); {*Если элемента j нет в ws, то увеличиваем значение счетчика числа незанятых которые встречаются до значения A[i].*} 46 2. Комбинаторные алгоритмы A[i] задействован в размещении.*} счетчика умножаем на количество приходящихся на одно значение в позиции с номером i.*} End; End; 2.2.3. Сочетания Между k-элементными подмножествами мно- жества и возрастающими последовательностями длины k с эле- ментами из множества целых чисел от 1 до N (сочетаниями) су- ществует взаимно однозначное соответствие. Так, например, подмножеству [2, 6, 1, 3] соответствует последовательность чи- сел 1, 2, 3, Таким образом, решая задачи подсчета и генера- ции всех сочетаний, мы решаем аналогичные задачи для k-эле- ментных подмножеств. Лексикографический порядок на множестве последовательностей определяется так же, как и для перестановок. Пример, 1234 1235 1236 1245 1246 1256 1345 1346 1356 1456 2345 2346 2356 2456 3456 Первая задача. Попробуем подсчитать количество сочета- ний для данных значений N и k. Использование формулы явно не продуктивно. Факториал представля- ет собой быстровозрастающую функцию, поэтому при вычисле- нии числителя и знаменателя дроби может возникнуть пере- полнение, хотя результат — число сочетаний — не превышает, например, значения Воспользуемся для подсчета чис- ла сочетаний формулой Получаем знаменитый треугольник Паскаля (см. с. 47). Про- сматривается явная схема вычислений. Очевидно, что если в за- даче не требуется постоянно использовать значения для раз- личных значений N и k, а требуется только подсчитать одно значение , то хранить двумерный массив в памяти компьюте- ра нет необходимости. Приведем процедуры вычисления для того и другого слу- чая. Подсчет всех значений C kN . Const Var Of LongInt; {*Нулевой столбец и нулевая строка необходимы, это позволяет обойтись без анализа на выход за пределы массива.*} Procedure FillSmallSc; Var i,j Begin FillChar For To N Do SmallSc For To N Do For To k Do If Then Else {*Умножение на 1.0 переводит целое число в поэтому переполнения при сложении не Стандартный прием, обязательный при "игре" на границах диапазона целых чисел.*} End; Второй вариант реализации процедуры. Type Of LongInt; Function LongInt; Var A,B:SmallSc; 48 2. Комбинаторные алгоритмы Begin (A),0) ; ; For To N Do Begin B[0] B[1] :=1; For k Do В [j]:=A[j]+A[j-1]; {*Если число больше максимального значения типа LongInt, то необходимо работать с арифметикой. Данная операция должна быть изменена - вызов процедуры сложения двух "длинных" чисел.*} А:=В; End; End; Вторая задача. Перейдем к алгоритму генерирования всех сочетаний в лексикографическом порядке, но прежде пример при и k=5. Число сочетаний равно 21. 0 1 2 3 4 5 6 12345 12346 12347 12357 12367 12456 7 8 9 10 11 12 13 12467 12567 13456 13457 13467 13567 14 15 16 17 18 19 20 14567 23456 23457 23467 23567 24567 34567 Начальное сочетание равно 1, 2, ..., k, последнее — ..., N. Переход от текущего сочетания к другому осуще- ствляется по следующему алгоритму. Просматриваем сочета- ние справа налево и находим первый элемент, который можно увеличить. Увеличиваем этот элемент на единицу, а часть соче- тания (от этого элемента до конца) формируем из чисел натура- льного ряда, следующих за ним. Procedure что текущее сочетание (хранится в массиве С) не является последним.*} Var i,j:Integer; Begin 2. Комбинаторные алгоритмы 49 While (C[i]+k-i+1>N) элемент, который можно {*Увеличиваем на единицу.*} For k Do {*Изменяем стоящие справа элементы.*} End; Третья задача. По номеру L определяем соответствующее сочетание. Для решения этой задачи необходимо иметь (вычис- лить) массив SmallSc, т. е. использовать первую схему вычис- ления числа сочетаний (первая задача) для данных значений N и k. Порядок на множестве сочетаний лексикографический. В таблице, приведенной выше, номера с 0 по 14 имеют сочета- ния, в которых на первом месте записана единица. Число та- ких сочетаний — («израсходован» один элемент из N и один элемент из Сравниваем число L со значением Если зна- чение L больше , то на первом месте в сочетании записана не единица, а большее число. Вычтем из L значение и продол- жим сравнение. Procedure (L:LongInt); Var Begin sc:=n; For i:=1 k Do {*i - номер элемента в сочетании; k-i - число элементов в сочетании.*} j:=1; {*sc-j - число элементов (п), из которых формируется сочетание.*} While Do Веgiп {*Для данной позиции в сочетании и числа элементов в сочетании находим тот элемент массива SmallSc, который превышает текущее значение L.*} Dec ; Inc {*Невыполнение условия цикла While говорит о том, что мы нашли строку таблицы т.е. то количество из которых формируется очередное сочетание, или тот интервал номеров сочетаний (относительно предыдущей цифры), в котором находится текущее значение номера 50 2. Комбинаторные алгоритмы End; цифра плюс приращение.*} Inc(ls,j); {*Изменяем зна чение текущей цифры Dec {*Изменяем количество элементов, из которых формируется остаток End; End; Пример (N=7, Для полного понимания логики выполните ручную трасси- ровку при N=9, Ответ — 23479. Однако достаточно, пора и честь знать. 2. Комбинаторные алгоритмы 51 Четвертая задача. Требуется по сочетанию получить его номер. Как и в предыдущей задаче, необходимо иметь массив Эта задача проще предыдущей. Требуется аккуратно просмотреть часть массива Эта часть массива опреде- ляется сочетанием, для которого ищется номер. Например, на первом месте в сочетании стоит цифра 3 k=4). Ищется сумма — количество сочетаний, в которых на пер- вом месте записана цифра 1, цифра 2 и цифра 3. Аналогично для следующих цифр сочетания. Предполагаем, что С[0] равно 0 — технический прием, позволяющий избежать лишних про- верок условий. Function Var sc:LongInt; j; Integer; Begin sc:=1; For к Do For j:=C[i-1]+1 To C[i]-1 Do Inc(sc, ; ; End; Пример (N=9, k=5, i 1 2 3 4 5 j 1 от З до 2, цикл j не работает от 4 до 3, цикл по j не работает 5 6 8 SC старое 1 71 71 71 75 78 SmallSc[N-j,k-i] 70 - 4 3 1 SC новое 71 - - 75 78 79 Пример (N=7, i 1 3 4 5 j 1 от 3 до 2, цикл по j не работает от 4 до 3, цикл по j не работает 5 от 7 до 6, цикл по j не работает SC старое 1 16 16 16 18 15 - - 2 - SC новое 16 - - 18 - Обратите внимание на то, что нумерация сочетаний в зада- чах 3 и 4 различна. В задаче 3 сочетания нумеруются с 0, а в задаче 4 — с 1. 52 2. Комбинаторные алгоритмы Пятая задача. Выберем для представления сочетания дру- гой вид — последовательность из 0 и 1. Последовательность храним в массиве (С) из N элементов со значениями 0 или 1, при этом С[i]=1 говорит о том, что элемент есть в соче- тании (подмножестве). Пусть N=7, В таблице представле- ны последовательности в той очередности, в которой они гене- рируются, и соответствующие им сочетания. 0 1 2 3 4 5 6 0011111 0101111 0110111 0111011 0111101 0111110 1001111 12346 12356 12456 13456 23456 12347 7 9 10 11 12 13 1010111 1011011 1011101 1011110 1100111 1101011 1101101 12357 12457 13457 23457 12367 12467 13467 14 15 16 17 18 19 20 1101110 1110011 1110101 1110110 1111001 1111010 1111100 23467 12567 13567 23567 14567 24567 34567 Принцип генерации последовательностей. Начинаем с конца последовательности. Находим пару C[i]=0 и C[i+1]=1. Если та- кой пары нет, то получена последняя последовательность. Если есть, то заменяем на месте i нуль на единицу и корректируем последовательность справа от i. Последовательность должна быть минимальна с точки зрения введенного порядка, поэтому вначале записываются 0, а затем 1, при этом количество 1 в по- следовательности должно быть сохранено. Опишем основные фрагменты реализации этой логики. Const Type Of 0. .1; Var Curr, MyArray; и последняя k: Begin ... For i : = 1 To N Do Begin For i:=1 To k Do Begin End; {*Формируем начальную и последнюю While Not Do Begin While (i>0) And Not ((Curr [i]=0) And (Curr [i + 1] =1) ) Do Dec (i); пару она так как последовательность не Num:=0; 2. Комбинаторные алгоритмы 53 For n Do (Num,Curr ); количество единиц.*} For j : = i + 1 Do {*Записываем нули.*} For To n Do {*3аписываем End; End; 2.2.4. Разбиение числа на слагаемые Дано натуральное число N. Его можно записать в виде сум- мы натуральных слагаемых: где a 1 ..., бо- льше нуля. Будем считать суммы эквивалентными, если они отличаются только порядком слагаемых. Класс эквивалентных сумм приведенного вида однозначно представляется последова- тельностями b 1 ..., упорядоченными по невозрастанию. Каждую такую последовательность b 1 ..., назовем разбиени- ем числа N на слагаемых. Как обычно, решаем четыре задачи: подсчет количества раз- личных разбиений числа; генерация разбиений относительно определенного отношения порядка, введенного на множестве разбиений; получение разбиения по его номеру и задача, обрат- ная третьей. Первая задача. пример для N=8, а затем рассуж- дения, позволяющие написать программный код. 1 2 3 4 5 6 7 8 11111111 2222 311111 3221 9 10 11 12 13 14 15 16 3311 332 41111 4211 422 431 44 5111 17 19 20 21 22 521 53 611 62 71 8 Число разбиений числа N на слагаемых обозначим через P(N,k), общее число разбиений — P(N). Очевидно, что значение равно сумме P(N,k) по значению Считаем, что Известен следующий факт. 54 2. Комбинаторные алгоритмы Теорема. Число разбиений числа N на слагаемых равно числу разбиений числа N с наибольшим слагаемым, равным Теорема доказывается простыми рассуждениями на основе диаграмм Феррерса. Пример такой диаграммы приведен ниже. Главное, что следует из этого факта, — реальный путь под- счета числа разбиений. Число разбиений P(i,j) равно сумме по значению k, где k изменяется от 0 до j. Другими сло- вами, j «выбрасывается» из i и подсчитывается число способов разбиения числа i-j на k слагаемых. Проверьте эту логику с помощью следующей таблицы. 1 2 3 4 5 6 7 8 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 2 0 1 1 2 2 3 3 4 3 0 0 1 1 2 .3 4 5 4 0 0 0 1 1 2 3 5 5 0 0 0 0 1 1 2 3 6 0 0 0 0 0 1 1 2 7 0 0 0 0 0 0 1 1 8 0 0 0 0 0 0 0 1 2 3 5 7 11 15 22 Например, Р(8,3)=Р(5,0)+Р(5,1)+Р(5,2)+Р(5,3). Определим данные. Const Var N:LongInt; SmallSc:Array[0..MaxN, Of LongInt; Procedure FillSmallSc; Var Begin For i:=1 To N Do For To i Do 2. Комбинаторные алгоритмы 55 For k:=0 j Do j ] , End; Таблица значений сформирована, она нам потребуется для решения других задач. Для подсчета же числа разбиений оста- лось написать простую процедуру. Procedure Var Begin For i:=2 To N Do [N , i ] ; End; Вторая задача. Генерация разбиений. Во-первых, необхо- дима структура данных для хранения разбиения. По традиции используем массив. Var Of Integer; В будем хранить длину разбиения, т. е. число задей- ствованных элементов массива Now. Возьмем из первой табли- цы одно из разбиений числа 8, например «41111», следующее «4211». В каком случае можно увеличить Видим, что Now[1] должно быть больше Now[2], т. е. в текущем разбиении находится «скачок» - Now[i-1]>Now[i], увеличивается на единицу, а все следующие элементы разбиения берутся ми- нимально возможными. Всегда ли возможна данная схема из- менения разбиения? Например, разбиение «44», следующее — «5111». Таким образом, или «скачок», или i равно 1. Кроме того, изменяемый элемент не может быть последним, ибо уве- личение без уменьшения невозможно. Procedure GetNext; Var Begin элемент {*B sc накапливаем сумму, это число представляется затем минимально возможными While (i>1) And Do Begin 56 2. Комбинаторные алгоритмы End; Inc {*Увеличиваем найденный элемент на единицу.*} {*Изменяем длину For j :=1 sc Do :=1; минимально возможные элементы, End; А будет ли работать данная логика для последнего разбие- ния (в нашем примере для «8»)? Оказывается, что нет. Прове- рьте. Считаем, что в Now хранится первое разбиение, а в массиве Last — последнее. Они формируются, например, в процедуре типа In.it. И схема генерации.... While ) Do {*Фунция Eq дает если текущее распределение совпадает с последним, и в противном случае, можно сделать проще - While Now[0]<>1 Do ...*} GetNext; Print; {*Вывод End; Третья задача. По номеру разбиения получить само раз- биение (Now). Нумерация разбиений осуществляется относите- льно введенного отношения порядка. Пусть L равно 0. Сделаем «набросок» логики. {*sc - число, которое представлено разбиением, i - номер позиции в While scOO Do Begin {*Пока число не исчерпано.*} которое должно записываться на место i в разбиении.*} ??????????? j определяется по L, пока не знаем как.*} {*Формируем текущую позицию разбиения и готовимся к переходу для формирование новой.*} End; Как это ни странно, но если вместо знаков «???» оставить пустое место («заглушку»), то при L, равном 0, данный набро- 2. Комбинаторные алгоритмы 57 сок будет работать — на выходе логики мы получим начальное разбиение, состоящее из единиц. Пусть L равно 1. Обратимся ко второй таблице данного материала. Проверяем SmallSc[8,1]. Если L больше или равно этому значению, то мы уменьшим значение L на SmallSc[8,1], увеличим значение j на единицу и, в конечном итоге, получим разбиение 2111111. Итак, что нам необходимо сделать? Да просто просмотреть строку массива SmallSc с номером sc и определить последний элемент строки, его номер в j, который меньше текущего значе- ния L. Мы последовательно отсекаем разбиения числа sc, начи- нающиеся с чисел j. Ниже приведен полный текст процедуры. Procedure Var Begin sc:=N; While sc<>0 Do Begin j:=1; Do Begin Inc(j); End; (i); End; :=i-1; {*Корректируем длину End; |