Еврістичне створення головоломки

32

КУРСОВА РОБОТА

на тему: «Еврістичне створення головоломки»

• Вступ
• Темою курсового проекту є «Еврістичне створення головоломки».
• Евристика (грец. heurisko - знаходжу, відшукую, відкриваю) - наука, яка вивчає творчу діяльність, методи, які використовуються у відкритті нового і в навчанні. Евристичні методи (друга назва Евристики) дозволяють пришвидшити процес вирішення задачі. Значний інтерес до їх дослідження виник у звязку з можливістю вирішення ряду задач (розпізнавання обєктів, доведення теорем і т.д.), в яких людина не може дати точний алгоритм вирішення, з допомогою технічних засобів. Метою Евристики є побудова моделей процесу вирішення якої-небудь нової задачі.
• Існують наступні типи моделей:
• 1. модель сліпого пошуку, яка спирається на так званий метод проб і помилок;
• 2. лабіринтна модель, в якій вирішувана розглядається як лабіринт, а процес пошуку рішення - як прохід по лабіринту;
• 3. структурно-семантична модель, яка рахується на даний час найбільш повною і яка відображає семантичні відношення між обєктами, які складають область задачі.
• Евристика повязана з психологією, фізіологією вищої нервової діяльностю, кібернетикою і т.д.
• Найпершою задачею еврістичного пошуку була головоломка, яка передбачала пересування гральних фішок по горизонталі або вертикалі на порожню ділянку до тих пір, доки отримана конфігурація не буде відповідати цільовій конфігурації.
• Програма, виконана у курсовій роботі, є комп'ютерною версією відомої «П'ятнашки». Це логічно нескладна і достатньо проста у керуванні і використанні програма.
• Актуальність теми полягає у тому, що на сьогоднішній день комп'ютер став досить важливою частиною життя суспільства, а комп'ютерні ігри набувають більшого поширення.
• Метою курсової роботи є поглиблення знань і розширення навиків по розробці алгоритмів та їх реалізації на персональному комп'ютері. Вона виконана в середовищі Турбо Паскаль з використанням графічних можливостей мови у роботі із масивами і графікою.

Пятнашки - популярна головоломка, що являє собою набір однакових квадратних кісточок з нанесеними числами, ув'язнених у квадратну коробку.

Суть самої гри полягає в наступному:

Гравець на екрані бачить табло, яке розбито на 16 кліток. У п'ятнадцяти з них розташовані неповторювані цифри, у випадковому порядку від 1 до 15 і одна порожня.

У загальному виді дане табло можна представити у вигляді таблиці 1:

Таблиця 1. Зразок табло

Гравець повинен переміщати по одній клітинці із цифрою на порожнє місце.

Так відбувається доти, доки користувач не вибудує послідовну комбінацію цифр (Таблиця 2), і лише після цього гравець уважається переможцем.

Таблиця 2. Правильне заповнення табло

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

2. Проектування

2.1 Розробка функціональної схеми

Незважаючи на простоту даної програми, написання алгоритму виявилося досить не простим завданням. У зв'язку із цим довелося розділити його, з метою його читаності й доступності.

Основний алгоритм програми розбитий на два розділи;

1. Керування;

2. Гра;

Рис. 2.1.1. Функціональна схема

1. Ініціалізація графічного режиму;

2. Заповнення в пам'яті комп'ютера табло випадковими цифрами;

3. Вивід табло на екран;

4. Уведення напрямку переходу;

5. Пошук порожнього елемента;

6. Переміщення елементів табло;

7. Вихід з режиму гри:

У програмі використовуються наступні вхідні дані (див. табл. 2.1.1.).

Таблиця 2.1.1. Імена та типи даних

Алгоритм даної гри (Рис. 2.2.1. Алгоритм гри.) реалізований за допомогою процедури Game15 і полягає в наступному:

Ініціалізація графічного режиму;

Заповнення в пам'яті комп'ютера табло випадковими цифрами;

Виведення табло на екран;

Введення напряму переходу;

Пошук порожнього елементу;

Переміщення елементів табло;

Вихід з режиму гри;

Схематично, даний алгоритм виглядає наступним чином:

Рис. 2.2.1. Алгоритм гри

1) Ініціалізація графічного режиму

Ініціалізація графічного режиму здійснюється в процедурі Game15. Перехід до графічного режиму здійснюється, за допомогою процедури Initgraph (grdriver, grmode, grpath), де grdriver - це використовувані програмою драйвер відеоадаптера (VGA), grmode - режим роботи відеосистеми (Vgahi), grpath - це місце знаходження файлу EGAVGA.BGI на диску (як і у випадку з файлами, пишемо тільки ім'я й розширення файлу, а не повний шлях, для того щоб у майбутньому можна було переміщати файли програми).

2) Заповнення табло випадковими числами

У пам'яті комп'ютера створюється табло, в якому, надалі проводитимуться перестановки. Табло складається з 16 (4 рядки і 4 три стовпці), яке заповнюється п'ятнадцятьма, цифрами, що не повторюються, від 1 до 15 і однією порожньою кліткою.

Даний розділ реалізований за допомогою процедури Tablo. Фактично табло, яке описується раніше це двовимірний масив з цифрами від 1 до 15 і порожня клітинка.

Наступному моментом реалізації даної процедури, є заповнення табло випадковими цифрами. Для заповнення табло випадковими цифрами використовується функція random, яка є генератором випадкових цифр, але працює відповідно тільки з цифрами, а у нас рядковий двовимірний масив.

Проаналізувавши вище сказане, приходимо до того, що необхідно створити два масиви. Один одномірний із шістнадцяти елементів типу integer, другий двовимірний, чотири на чотири, типу string. Спочатку одномірний масив, у випадковому порядку, заповнюється цілими неповторюваними цифрами від 1 до 16, а потім залежно від розташування цифр, заповнюється двовимірний строковий масив. ПРИМІРОМ, якщо перший елемент одномірного масиву дорівнює цифрі 11 тоді першому елементу двовимірного масиву буде привласнено рядок «11».

Загальний алгоритм (Рис. 2.2.2. Алгоритм заповнення табло випадковими числами.) полягає в наступному:

Вибір випадкового числа;

Перевірка на наявність збігів в масиві;

Заповнення двовимірного масиву;

Рис. 2.2.2. Алгоритм заповнення табло випадковими числами

Вибір випадкового числа;

Деякій змінній b привласнюється випадкове число, за допомогою функції random. При чому функція random обмежена інтервалом від 1 до 16.

Перевірка, чи є співпадання;

Змінна b порівнюється з кожним елементом масиву bs[і], за допомогою інструкцій For і if. Якщо такий елемент уже присутній в одномірному масиві, тоді змінної b, знову привласнюється випадкове число. Так відбувається доти, поки змінної b не буде привласнена цифра, якої ще немає в масиві.

Страницы: 1, 2, 3