енти кожного з блоків розбиття окремо. Тому наведемо можливий варіант її реалізації (як і раніше, розподіляли по блоках ми індекси, а друкуємо або аналізуруем самі елементи вихідного масиву a):
procedure print (n: integer; var p: list);
var i, j, imax: integer;
begin
imax: = 1; {визначаємо кількість блоків в розбитті}
for i: = 2 to n do
if p [i]> imax then imax: = p [i];
for i: = +1 to imax do { цикл по блокам }
begin
for j: = 1 to n do
if p [j] = i then write (a [j]: 4);
write (' | ') {Блок надрукований}
end;
writeln {Розбиття надруковано}
end;
вкладених циклів можна уникнути, якщо потрібно, наприклад, підрахувати суму елементів у кожному з блоків. Тоді, використовуючи додатковий масив, ми, переглядаючи елементи масиву a послідовно, будемо збільшувати значення суми для блоку, відповідного розглядався елементу (Аналогічно операції, здійснюваної у алгоритмі сортування підрахунком). p> Якщо при цьому розглядати масив p як n -значне число n -річної системі числення, то можна ввести поняття лексикографічного порядку для розбиттів множини і ставити завдання визначення номера розбиття і зворотну їй. Як і раніше (див. [1-3]), вони вирішуються методом динамічного програмування і не використовують безпосередню генерацію всіх розбиттів.
Для повноти розгляду даної теми самостійно змініть процедуру partition так, щоб вона генерувала всі розбиття, які складаються не більш ніж з k блоків. Після цього напишіть процедуру розбиття безлічі вже на рівно k непорожніх частин.
Олімпіадні завдання, що використовують комбінаторні конфігурації
Приклад 1. На одному острові Нової Демократії кожен з його мешканців організував партію, яку сам і очолив. Зазначимо, що до загального здивування навіть у самої нечисленної партії виявилося не менше двох осіб. На жаль, фінансові труднощі не дозволили створити парламент, куди увійшли б, як Предпологалось за Конституцією острова, президенти всіх партій. Порадившись, Остров'яни вирішили, що буде достатньо, якщо в парламенті буде хоча б один член кожної партії. Допоможіть Остров'янам організувати такий, як можна більш малочисельний парламент, в якому будуть представлені члени всіх партій.
Вихідні дані: кожна партія і, відповідно, її президент мають однаковий порядковий номер від 1 до N (4 ВЈ N ВЈ 150). Вам дані списки всіх N партій Острови Нової Демократії. Виведіть пропонований Вами парламент у вигляді списку номерів його членів. ( Олімпіада країн СНД , м. Могильов, 1992 р.)
Рішення : з теоретичної точки зору, дана задача збігається із завданням генерації всіх підмножин з безлічі жителів острова нової демократії. Причому найбільш підходящим здається перший підхід до вирішення даної задачі, пов'язаний з генерацій різних сполучень, починаючи з одного мешканця. Для повноти викладу цього підходу, опишемо функцію сheck, яку слід застосувати в даній завданню. Вихідні дані слід записати в масив s: array [1 .. 150] of set of 1 .. 150, заповнивши кожен з n перших елементів цього масиву безліччю тих партій, в яких складається той чи інший житель. Тоді функція перевірки поєднання з елементів цього масиву прийме наступний вигляд:
function check (var p list ; k: integer): boolean;
var i: integer; ss: set of 1 .. 150;
begin
ss: = [];
for i: = 1 to k do ss: = ss + s [p [i]];
check : = ( ss = [1 .. n < i>])
end ;
Як видно з опису функції, використання типу "безліч", дозволяє не тільки спростити дану програму, але й істотно прискорити її виконання, по порівнянні з роботою з масивами. Однак велика розмірність даної завдання не дозволяє вважати наведене рішення задовільним у всіх випадках. Так, вже для n = 100, перебір всіх сполучень з 4-х і менше жителів призводить до розгляду близько 4-х мільйонів варіантів. Для побудови коду, придатного для вирішення даної задачі за будь-яких вхідних даних, кілька змінимо опис масиву s:
s: array [1 .. 150] of
record name, number: integer;
partys : set of 1 .. 150
end ;
Тут полі partys збігається за змістом з початковим описом масиву s, поле name Відповідне номеру (тобто фактично імені) жителя і спочатку дане поле слід заповнити числами від 1 до n cогласно індексом елемента в масиві записів, і поле number відповідає кількістю елеме...
