Однак слід зазначити, що у результаті виконання такої програми ми не отримаємо виведення всіх можливих варіантів у лексикографічному порядку.
Тестування алгоритму одержання всіх можливих розмі щень на М місцях із N різних предметів аналогічне тестуванню попередніх алгоритмів.
Завдання
1.Розробити і реалізувати у вигляді програми алгоритм визна чення кількості всіх можливих розміщень.
2.Розробити і реалізувати у вигляді програми алгоритм гене рації всіх можливих варіантів розміщень.
3.Виконати завдання 1 та 2 для множини елементів 1, 2, 3, 4, 5 та М = 3, вивівши результат виконання програми у файл.
4.Модифікувати програми у завданнях 2-3 для множини різних символів.
5.Модифікувати програми у завданнях 2-3 для множини різних слів,
6.Зробити письмовий аналіз виконання завдань 1-5.
Повна вибірка
Повною вибіркою назвемо всі можливі вибірки по М елементів (1 < М ^ N) із N заданих. Хоча на перший погляд для розв'язан ня даної задачі можна застосувати розглянуті вище алгоритми, але насправді є ефективніший та простіший алгоритм.
Розглянемо випадок, коли N = 4. Давайте визначимо, які є варіанти вибірки по одному елементу: 1000, 0100, 0010, 0001. Якщо зробимо вибірку будь-яких двох елементів з чотирьох за даних, то одержимо: 1100, 1010, 1001, 0110, 0101, 0011. Вибірка по три елементи виглядатиме так: 1110, 1101, 1011, 0111. Вибірка чотирьох елементів з чотирьох можливих буде такою: 1111. А тепер давайте розмістимо всі ці значення у лек сикографічному порядку:
0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011,1100,1101, 1110,1111.
Мабуть, відповідь на поставлене запитання вже зрозуміла! Ми отримали чотиризначні двійкові числа у порядку зростан ня. Отже, для одержання всіх можливих вибірок із заданих N елементів необхідно реалізувати алгоритм додавання чис ла 1 у двійковій системі числення до двійкового числа, розрядність якого складає N. Стартовим числом має бути двійкове число розрядності ./V зі значенням 1: 0~Л)1-
J V - 1
34
Неважко також підрахувати і кількість таких вибірок. Як що у N позиціях різними способами розміщувати два елементи 0 та 1, то кількість варіантів таких розміщень буде визначати ся формулою К - 2N.
Цей зовсім нескладний алгоритм можна представити таким фрагментом Pascal-програми:
procedure binary; |
|
|
|
var і, с: byte; |
|
|
|
begin |
|
|
|
с := 1; і := n; |
|
|
|
while (с = 1) and (І >= 1) do |
|
{Додавання відбувається допоки с = 1.} |
|
begin |
|
|
|
а[і] := а[і] + с; С := 0; |
{Одержання нового значення в /'-му розряді.} |
||
if а[і] = 2 then |
|
|
{Переведення результату додавання} |
begin а[і] := 0; с := 1 end; |
{у двійкову систему числення.} |
||
dec(i) |
|
{Перехід до нового розряду двійкового числа.} |
|
end; |
|
|
|
end; |
|
|
|
Наведену процедуру можна використати в основній про |
|||
грамі таким чином: |
|
|
|
f •= 1" |
|
|
|
for і := 1 to n do |
|
|
{Підрахунок кількості варіантів.} |
f : = f * 2 ; |
|
|
|
for І := 1 to n do |
{Ініціалізація стартового значення двійкового числа.} |
||
а[і]:=0; |
|
|
|
for І := 1 to f - 1 do |
{Організація визначення всіх варіантів повної вибірки,} |
||
begin |
|
|
{окрім варіанта 00...0.} |
binary; |
|
|
|
for j := 1 to П do |
|
|
{Виведення поточного варіанта вибірки.} |
if a[j] = 1 then write(f_out, b[j], " ) ; writeln(fout);
end;
Трапляються задачі, в яких можна використовувати цей алгоритм у дещо іншому призначенні. Наприклад, відомо, що необхідно визначити, скількома способами можна розмістити квіти трьох видів у 4 вазах. Якщо позначити види квітів циф рами 1, 2, 3, то варіанти будуть такими: 0001, 0002, 0003, 0010, 0011, 0012, 0013, 0020, 0021, 0022, 0023, 0030, 0031, 0032, 0033, 1000, 1001, 1002, ..., 3333. Із наведеної послідовності можна зробити висновок, що йдеться про додавання цифри 1 у трійковій системі числення. Тобто наведений вище алгоритм необхідно модифікувати для варіанта такого додавання, а кіль кість можливих варіантів становитиме 3^.
Так само, як ми це робили у попередніх випадках, протес туємо алгоритм одержання всіх можливих вибірок для N = 4.
2* |
35 |
Відповідь, що буде виведена у вихідний файл, може бути візу ально перевірена. Будь-які інші тести для великих N усклад нюються як перевіркою кількості одержаних вибірок, їх зна ченнями, так і часом виконання самого алгоритму.
І насамкінець ще раз нагадаємо, що переважна більшість розглянутих алгоритмів має факторіальну оцінку ефектив ності їх роботи 0(п\), що ускладнює їх використання для вели кої кількості елементів.
Завдання
1.Розробити і реалізувати у вигляді програми алгоритм визна чення кількості повних вибірок.
2.Розробити і реалізувати у вигляді програми алгоритм гене рації повних вибірок.
3.Виконати завдання 1 та 2 для множини елементів 1, 2, 3, 4, 5, вивівши результат виконання програми у файл.
4.Модифікувати програми у завданнях 2-3 для множини різних символів.
5.Модифікувати програми у завданнях 2-3 для множини різних слів.
6.Зробити письмовий аналіз виконання завдань 1-5.
/ |
Запитання для самоконтролю |
1.Що вивчає комбінаторика як розділ математики?
2.Які основні поняття комбінаторики ви можете назвати?
3.Що визначають основні поняття комбінаторики?
4.Які алгоритмічні задачі називають комбінаторними? Наведіть власні приклади комбінаторних алгоритмічних задач.
5.Запишіть формули для обчислення кількості перестановок для N елементів, розміщень та сполучень для М елементів з N мож ливих.
6. Як вивести формулу для обчислення кількості перестановок
N елементів?
7.Що називається лексикографічним порядком на множині всіх перестановок? Наведіть власні приклади.
8.Який алгоритм можна застосувати для отримання всіх варіантів перестановок на множині заданих значень у лексикографічному порядку? Продемонструйте свою відповідь графічно.
9.Запишіть процедуру мовою Pascal, яка реалізує алгоритм ви значення всіх перестановок.
10.Як організувати виклик процедури одержання всіх перестановок в основній програмі? Запишіть фрагмент Pascal-програми.
11.Яким є алгоритм визначення всіх вибірок М елементів із N за даних?
12.Як необхідно модифікувати алгоритм одержання всіх пере становок, щоб використати його для визначення вибірок? Запи шіть цю процедуру мовою Pascal.
36
13.Яким чином можна підрахувати кількість вибірок М елементів із Л/ заданих?
14.Запишіть фрагмент Pascal-програми, яка, використовуючи про цедуру формування всіх перестановок, дає можливість одержа ти всі вибірки М елементів із N заданих.
15.Як одержати всі розміщення М елементів із N заданих? Які алго ритми для цього можна застосувати?
16.Запишіть фрагмент Pascal-програми, що реалізує алгоритм одержання всіх розміщень М елементів із N заданих.
17.Що розуміється під повною вибіркою?
18.Який алгоритм можна застосувати для одержання повної вибір ки з N заданих елементів? Обґрунтуйте свою відповідь, навівши власні приклади.
19.Запишіть процедуру, що реалізує алгоритм одержання повної вибірки з N заданих елементів, мовою Pascal.
20.Запишіть мовою Pascal фрагмент програми, що використовує процедуру одержання повної вибірки з N заданих елементів.
21. У яких алгоритмічних задачах можна застосувати ідею побудови алгоритму, що визначає повні вибірки з N заданих елементів? Наведіть власний приклад такої задачі.
37
Розділ III
INP-ПОВНІ ЗАДАЧІ
0 |
0 0 |
9 1 1 0 1 |
|
|
||
|
1 0 1 0 0 |
J, |
0,1 |
|
|
|
|
|
|
|
• - • ' • • • • • • • • • • < • • - • • • • ' • ' |
• • • - • • • • |
••••••••••••-•••- |
1 0 1 1 |
0 |
0 |
1 |
|
|
|
а |
й о |
|
і |
|
|
|
1 |
о |
|
1 |
|
|
|
Розглядаючи різні методи сортування масивів, ми нама галися досягнути створення найоптимальніших алгоритмів, щоб вирішувати це завдання. Крім цього, ми надавали перева гу тим з них, які розв'язують поставлену задачу за найменший час, і аналізували при цьому кількість виконуваних ними дій.
Пошукові алгоритми та алгоритми сортування, що розгля далися раніше, відносяться до алгоритмів класу Р, тобто алго ритмів, що виконуються за поліноміальнии час. Нагадаємо, що поліномом називається вираз а^р" + ап _ хрп х + ... + агр + а0 . Так, ми вже знаємо, що всі зазначені вище алгоритми мають оцінку ефективності 0(п), 0(п2) тощо. А це і є поліноміальною складністю алгоритму. Оскільки час виконання таких алго ритмів досить невеликий, то такі задачі ще називають практич но розв'язуваними.
Але чи для всіх задач можна віднайти такі алгоритми? Чи для розв'язання будь-яких задач існують алгоритми, час ви конання яких на комп'ютері можна виміряти секундами або хоча б хвилинами? Виявляється, що ні. Існують задачі, для яких на сьогоднішній день невідомі алгоритми, що визначають результат за реально вимірюваний час, або, як ще кажуть, за розумний час. Такий клас задач носить назву NP, і з ним ми ознайомимося у даному розділі.
Задачі, що відносяться до класу NP, мають недетерміновану поліноміальну складність виконання. Розтлумачимо поняття «недетерміновані поліноміальні», що характеризують задачі класу NP. Процес пошуку розв'язку таких задач можна роз бити на два етапи.
Перший етап передбачає пошук можливого розв'язку за дачі. Подекуди цей пошук зводиться до банального вгадування шуканого розв'язку або ж обміркованого вибору одного із мож ливих його варіантів. Другий - перевірку того, чи справді цей розв'язок є шуканою відповіддю до поставленої задачі. Кож ний з обох кроків окремо вимагає поліноміального часу. Однак, на жаль, ми не знаємо, скільки разів нам необхідно буде повто рити ці спроби, щоб отримати шуканий розв язок.
38