Теоретичні відомості

Лабораторна робота № 4

Тема:Складення графіку проведення тенісного турніру (алгоритм «поділяй та

володій»)

Мета:Навчитись складати графік проведення тенісного турніру, використовуючи

алгоритм «поділяй та володій».

Теоретичні відомості

Метод декомпозиції одержав широке застосування не тільки при розробці алгоритмів, але і в проектуванні електронних схем, побудові математичних доведень та в інших сферах. В якості ілюстрації наведемо лише один приклад. Розглянемо складення розкладу проведення тенісного турніру за круговою схемою для n = 2^k гравців. Кожен гравець повинен зіграти із всіма іншими гравцями, при цьому кожен гравець повинен зіграти по одному матчу в день протягом (n–1) днів – мінімальної кількості днів, необхідних для проведення всього турніру.

Розклад проведення турніру, таким чином, являє собою таблицю, яка складається з n рядків та n-1 стовпчиків; елементом на перетині рядка і та стовпчика j є номер гравця, з яким гравець і повинен провест матч в j-й день.

Метод декомпозиції дозволяє скласти розклад для половини гравців. Цей розклад складається на основі рекурсивного застосування даного алгоритму для половини цієї половини гравців і т.д. Коли кількість гравців зменшиться до двох, виникає «базова ситуація», в якій ми просто встановлюємо порядок проведення зустрічей між ними.

Допустимо, в турнірі беруть участь вісім гравців. Розклад для гравців 1 – 4 заповнює верхній лівий кут (4 рядки х 3 стовпчики) розкладу, який формується. Нижній лівий кут (4 рядки х 3 стовпчики) цього розкладу повинен звести між собою гравців з вищими номерами (5 – 8). Ця частина розкладу одержується шляхом додавання числа 4 до кожного елемента в верхньому лівому куті.

Тепер необхідно звести між собою гравців з низькими і вищими номерами. Зробити це неважко: потрібно на 4-й день звести в пари гравців, які мають номери 1 – 4, з гравцями 5 – 8 відповідно, а в наступні просто циклічно переставляти номери 5 – 8. Цей процес показано на Рис.4.1.

1 2 3 1 2 3 4 5 6 7

	2
	1

			3

Рис. 4.1. Організація кругового турніру для восьми гравців.

Обчислимо шанси на перемогу команд в спортивних турнірах.

Допустимо, дві команди А і В проводять між собою турнір. Переможцем вважається той, хто першим виграє n матчів. Можна припустити, що сили команд А і В приблизно рівні, тобто у кожної з них є 50% шансів виграти черговий матч. Припустимо, P(i, j) – ймовірність того, що якщо А для перемоги потрібно провести і матчей, тоді в кінцевому рахунку перемогу на турнірі одержить А. Наприклад, якщо в турнірі команда А виграла два матчі, а команда В – один, то і = 2, j = 3 і, як ми переконаємося пізніше, Р(2, 3) =11/16.

Для того, щоб обчислити P(i, j), можна скористатися рекурентним рівнянням з двома змінними. По-перше, якщо і = 0 і j > 0, то команда А вже виграла турнір, тому P(0, j) = 1. Аналогічно, P(i, 0) = 0 для всіх і > 0. Якщо, як і, так і j більші за нуль, командам прийдеться провести, принаймні, ще один матч з рівними шансами виграти цю гру. Таким чином, P(i, j) повинно бути середнім значенням P(i - 1, j) та P(i, j - 1), перший з цих виразів є ймовірністю того, що команда А виграє турнір, навіть якщо програє наступний матч. Отже, отримаємо рекурентні співвідношення:

P(i, j) = 1, якщо і = 0 і j > 0,

P(i, j) = 0, якщо і > 0 і j = 0, (4.1)

P(i, j) = (P(i - 1, j) + P(i, j - 1)) /2, якщо і > 0 і j > 0.

Проблема з рекурентними обчисленнями заключається в тому, що потрібно періодично обчислювати одне і те ж значення P(i, j) декілька раз. Якщо, наприклад, потрібно обчислити Р(2, 3), то у відповідності з (4.1) необхідно спочатку обчислити Р(1, 3) і Р(2, 2). А для обчислення Р(1, 3) і Р(2, 2) потрібно обчислити Р(1, 2), тобто одне і те ж значення Р(1, 2) потрібно обчислити двічі.

Раціональнішим способом обчислення P(i, j) є заповнення спеціальної таблиці (див. Таблиця 4.1), в нижньому рядку якої присутні лише нулі, а крайній правий стовпчик повністю заповнений одиничками (це відповідає першим двом рядкам із (4.1)). Що ж до останнього рядка із (4.1), то всі інші елементи таблиці представляють собою середні значення елементів, які знаходяться знизу і справа від відповідного

Рис. 4.2.Шаблон

елемента.

обчислень

Таким чином, таблицю слід заповнювати, починаючи з її нижнього правого кута і рухатися вверх і вліво вздовж діагоналей, що представляють елементи з постійним значенням i + j, як показано на Рис.4.2.

Таблиця 4.1.

Таблиця ймовірностей

1/2	21/32	13/16	15/16
11/32	1/2	11/16	7/8
3/16	5/16	1/2	3/4	↑
1/16	1/8	1/4	1/2	j


← і

⇐ Предыдущая 2 3 4 5 6 789 10 11 Следующая ⇒