Математичні та алгоритмічні основи рішення задачі

Для того щоб приступити до побудови та аналізу математичної моделі гри, необхідно визначити ймовірності виявлення кораблів при різному їх розташуванні і різних системах пошуку.

На полі з n клітин розташований одноклітинний корабель. Визначимо ймовірність попадання в корабель k-им пострілом, тобто його знищення.

В якості простору елементарних фіналів вибору гравця У розглянемо безліч стратегій обстрілу ігрового поля, кожна стратегія складається з n пострілів,

,

де – номер обраної клітини, тобто розглянемо безліч всіх вибірок з n по n клітин. Очевидно, що цей простір містить елементів і всі ці стратегії рівноможливі. Кількість стратегій з успішним результатом, тобто кількість вибірок, що містять на k-му місці шукану клітку:

.

Ймовірність попадання:

.

Визначимо ймовірність знищення корабля за k пострілів. Ця подія полягає в тому, що корабель може бути знищений або першим пострілом, або другим і т.д., тобто сприятлива вибірка з k клітин містить шукану клітку з кораблем. Кількість сприятливих стратегій визначиться як число невпорядкованих вибірок з безлічі n - 1 клітин по k - 1 (одна клітина, зайнята кораблем не враховується при вибірці), помножене на число перестановок в самій вибірці k! і число перестановок клітин залишилися за вибіркою (n - k)!. Ймовірність влучення в одноклітинний корабель за k пострілів:

. (1)

Ускладнимо завдання. На полі з n клітин розташований двухклітинний корабель. Визначимо ймовірність першого попадання в корабель (в одну з його клітин) пострілом з номером k. Повне число всіляких стратегій, як і в попередньому випадку, одне , а число сприятливих стратегій визначається як сума сприятливих стратегій попадання в одну клітину і попадання в другу клітину, тобто . Ймовірність влучення k-им пострілом дорівнює .

Очевидно, що при обстрілі m-клітинного корабля або m одноклітинних кораблів, ймовірність потраплення k-им пострілом дорівнює:

.

Визначення ймовірності попадання в двохклітинний корабель за k пострілів, зведеться до визначення кількості стратегій, що містять шукані клітини в перших k пострілах. Число таких стратегій буде обчислюватися як наступна сума:

,

де – вибірки, що містять або першу клітку, або другу клітку, – вибірки, що містять одночасно дві клітини.

Отже

і після перетворень отримаємо:

. (2)

Зауважимо, що аналогічним чином можна визначити ймовірність попадання за k пострілів у корабель з m клітин. Завдання потрапляння за k пострілів у багатоклітинний корабель хоча б один раз є завданням пошуку корабля. Очевидно, що якщо врахувати геометрію корабля, то можна запропонувати систему його пошуку, при якій ймовірність виявлення стає вище. Дійсно, при пошуку двухклітинного корабля можна розглянути підмножину всіх стратегій, що містять обстріл, наприклад, клітин тільки з парними або з непарними номерами. Пошук двохклітинного корабля зведеться до пошуку одноклітинного корабля на цій підмножині. Вважаючи n парних, для оптимальної ймовірності попадання за k пострілів отримаємо

. (3)

Знайдене значення ймовірності більше ймовірності, отриманої вище

,

при всіх значеннях .

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

Ймовірність влучення в грі «Морський бій».

Всього клітин 100.

а) ймовірність потрапити в який-небудь корабель: ;

б) ймовірність потрапити в чотирьохпалубний: ;

в) ймовірність потрапити в однопалубний ;

Всього кораблів 10, що не однопалубних 6, «клітинок» 16.

а) ймовірність потрапити в чотирьохпалубний: ;

б) ймовірність потрапити в трьохпалубний: ;

в) ймовірність потрапити в двохпалубний: .

Висновок

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

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