Міністерство освіти Республіки Білорусь
Установа освіти
В«Гомельський державний університет ім. Ф. Скорини В»
Математичний факультет
Кафедра МПУ
Реферат
Комбінаторні задачі
Виконавець:
Студентка групи М-42 Макарченко А.Ю.
Науковий керівник: Долинський М.С.
Гомель 2005
Зміст
Введення
Генерація k-елементних підмножин
Генерація всіх підмножин даної множини
Генерація всіх перестановок n-елементного безлічі
Розбивки безлічі
Висновок
Література
Введення
Завдання дискретної математики, до яким належить більшість олімпіадних завдань з інформатики, часто зводяться до перебору різних комбінаторних конфігурацій об'єктів і вибору серед них найкращого, з точки зору умови тієї або іншої задачі. Тому знання алгоритмів генерації найбільш поширених комбінаторних конфігурацій є необхідною умовою успішного вирішення олімпіадних завдань в цілому. Важливо також знати кількість різних варіантів для кожного типу комбінаторних конфігурацій, так як це дозволяє реально оцінити обчислювальну трудомісткість обраного алгоритму вирішення тієї чи іншої задачі на перебір варіантів і, відповідно, його прийнятність для вирішення розглянутої задачі, з урахуванням її розмірності. Крім того, при вирішенні завдань корисним виявляється вміння для кожної з комбінаторних конфігурацій виконувати наступні операції: за наявною конфігурації отримувати наступну за нею в лексикографічному порядку; визначати номер даної конфігурації в лексикографічній нумерації всіх конфігурацій; та, навпаки, за порядковим номером виписувати відповідну йому конфігурацію.
Генерація k-елементних підмножин
В комбінаториці такі підмножини називають поєднаннями з n елементів по k елементів і позначають C n k . Їх кількість виражається наступною формулою:
Однак при програмуванні набагато зручніше використовувати наступні рекурентні співвідношення:
Пояснюється це тим, що у формулі (1) чисельник і знаменник ростуть дуже швидко, тому в силу особливостей комп'ютерної арифметики не завжди можливо точно вирахувати значення C n k , навіть коли останнє не перевершує максимально представимое ціле число.
При фіксованому значенні n максимального значення число сполучень досягає при k = n /2 (вірніше, для парного n максимум один і він зазначений, а для непарного - максимум досягається на двох сусідніх значеннях k : [ N/ 2] і
[ n /2] +1). Тому особливо корисною виявляється наступна оцінка для парних n [4] (Очевидно, що при непарних n відмінності будуть мінімальними), заснована на формулою Стірлінга:
Якщо допустити, що за час, відведений для вирішення завдання, ми можемо перебрати близько 10 6 варіантів, то з формули (3) випливає, що генерацію всіх сполучень з n елементів для будь-якого фіксованого k можна проводити для n ВЈ 24.
Зазвичай генерацію всіх k -елементних підмножин проводять в лексикографічному порядку, тим більше що в даному випадку це не призводить ні до ускладнення алгоритму, ні до збільшення його обчислювальної трудомісткості. Нагадаємо, що порядок підмножин називається лексикографічним, якщо для будь-яких двох підмножин справедливо, що раннє повинно бути Згенеровано то з них, з індексів елементів якого можна скласти менше k -значне число в n -ричной системі числення (або в десятковій, для n <10). Так, для n = 6 і k = 3 поєднання з третього, першого та п'ятого елемента має бути Згенеровано раніше, ніж з другого, третього і четвертого, так як 135 <234.
Розглянемо рекурсивний алгоритм вирішення цієї задачі. Ідея відомості даної задачі до задачі меншої розмірності наступна. Першим елементом підмножини може бути будь-який елемент, починаючи з першого і закінчуючи ( n - k + 1)-м елементом. Після того, як індекс першого елемента підмножини зафіксований, залишилося вибрати k - 1 елемент з елементів з індексами, більшими, ніж у першого. Далі поступаємо аналогічно. Коли обраний останній елемент, то ми досягли кінцевого рівня рекурсії та вбрання підмножина можна обробити (Проаналізувати або роздрукувати). У запропонованій нижче програмі масив a містить значення елементів вихідного безлічі і може бути заповнений довільним чином. У масиві p будемо формувати чергове поєднання з k елементів.
const nmax = 24;
type list = array [1 .. nmax] of integer; var k, i, j, n, q : Integer; a, p: list; procedure print (k: integer);
var i: integer; beginfor j: = 1 to k dowrite (p [j]: 4); writelnend; {print}
procedure cnk (n, k: integer); procedure gen (m, L: integer); var i: integer; beginif m = 0 then print (k) elsefor i: = L to n-m +1 dobegin
p [k-m +1]: = a [i];
gen (m-1, i +1)
end
end; {gen}
begin {cnk} gen (k, 1) end; {cnk} begin {Main} readln (n, k); for i: = 1 to n doa [i]: = i; { заповнити масив можна і по - іншому }
cnk (n, k)
end.
Зауважимо, що власне генерація поєднань проводиться в рекурсивної підпрограмі gen. Вона має наступні параметри: m - скільки елементів з безлічі нам ще залишилося вибрати і L - починаючи з якого елементу вихідного безлічі, слід вибирати ці m елементів. Зверніть увагу, що саме вкладена структура опису процедур cnk і gen дозволяє не передавати при рекурсивних викликах значення n і k , а з основної програми звертатися до процедури cnk з параметрами, відповідними постановці завдання, не вдаючись у подробиці її вирішення. Такий спосіб будемо застосовувати і надалі.
Генерація всіх підмножин даної множини При вирішенні олімпіадних завдань найчастіше заздалегідь невідомо, скільки саме елементів вихідного безлічі повинно входити в шукане підмножина, тобто необхідний перебір всіх підмножин. Однак, якщо потрібно знайти мінімальне підмножина, тобто складається як можна з меншого числа елементів (або максимальне підмножина), то найефективніше організувати перебір так, щоб спочатку перевірялися всі підмножини, що складаються з одного елемента, потім з двох, трьох і т. д. елементів (для максимального підмножини - у зворотному порядку). У цьому випадку, перше ж підмножина, що задовольняє умові задачі і буде шуканим, і подальший перебір слід припинити. Для реалізації такого перебору можна скористатися, наприклад, процедурою cnk, описаної в попередньому розділі. Введемо в неї ще один параметр: логічну змінну flag, яка буде позначати, задовольняє поточне поєднання елементів умові завдання чи ні. При отриманні чергового поєднання замість його друку звернемося до процедури його перевірки check, яка і буде визначати значення прапора. Тоді початок процедури gen слід переписати так:
procedure gen ( m , L : integer );
var i: integer;
begin
if m = 0 then
begin
check (p, k, flag);
if flag then exit
end
else ...
Далі процедура дослівно збігається з попередньою версією. В основній же програмі єдине звернення до даної процедури слід замінити наступним фрагментом:
k: = 0;
