Міністерство освіти Республіки Білорусь
Установа навчання
В«Гомельський державний університет ім. Ф. Скорини В»
Математичний факультет
Кафедра МПУ
Реферат
Комбінаторні задачі
Виконавець:
Студентка групи М-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. p> Розглянемо рекурсивний алгоритм розв'язання даної задачі. Ідея відомості даної задачі до завданню меншої розмірності наступна. Першим елементом підмножини може бути будь-який елемент, починаючи з першого і закінчуючи ( 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...
