Технологія створення програми

Спочатку був спроектований вигляд HTML-меню проекту в графічному редакторі Adobe Photoshop CS5.

Потім був написаний код шаблону графічної оболонки з використанням мови гіпертекстової розмітки HTML та каскадних таблиць стилів CSS в редакторі Adobe Dreamweaver CS5.

Наступним етапом було створення проекту в середовищі програмування Microsoft Visual Studio 2008 для кожної прикладної задачі. Були створені такі проекти :

• “EightQueens” – Задача про 8 ферзів, з кодом в файлі: “EightQueens.cpp”

• “Knight ” – Обхід конем шахової дошки, з кодом в файлі: “Knight.cpp”

• “Labyrinth” – Задача про лабіринт, з кодом в файлі: “Labyrinth.cpp”

• “Salesman” – Задача комівояжера, з кодом в файлі: “Salesman.cpp”

• “Parlament” – Задача про парламент, з кодом в файлі: “Parlament.cpp”

• “GasStation” – Задача про автозаправку, з кодом в файлі: “ GasStation.cpp”

В кожному з цих проектів був послідовно написаний код для реалізації поданої прикладної задачі, під час цього було виконане налагодження програм та виправлення помилок. Був виконаний процес перевірки правильності роботи програм на вхідних тестах [2].

Був створений проект для багатофайлової програми з іменем “backtrack”, що містить всі виконані прикладні задачі як модулі. Було додано срр файли всіх виконаних задач та заповнено головний файл “backtrack.срр” викликами даних модулів. Також був створено header-файл, з ім’ям “backtrack.h”. Був виконаний процес виправлення помилок та налагодження роботи програми.

На цьому етапі було додано теоретичну інформацію про алгоритм та розв’язані задачі в HTML-меню. А також посилання на коди програм, ехе-файли та архіви з проектами Microsoft Visual Studio 2008.

Застосування алгоритмів для прикладних задач

Задача про вісім ферзів

Умова задачі [2]

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

Вхідні та вихідні тести

Дана задача не містить вхідних даних.

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

Опис алгоритму методу

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

Алгоритм програми

1. Позначити всі клітинки шахової дошки вільними.

2. Виконати пункт 3 для рядку .

3. Поставити ферзя на даний рядок:

   1. Продивитися клітинки даного рядка:

      1. Якщо дана клітинка вільна, то:

         1. Розмітити ферзя на даній клітинці:

            1. Позначити рядок, стовпець, та діагоналі що проходять через клітинку в якій розмістили ферзя, як клітинки які б’є ферзь.

         2. Запам’ятати позицію розміщеного ферзя.

         3. Якщо кількість розміщених ферзів , тоді:

            1. Вивести варіант розстановки ферзів на екран.

            2. Прибрати щойно доданого ферзя з шахової дошки

         4. Інакше виконати пункт 3 для наступного рядка.

   2. Якщо не було додано ферзя в даний рядок, або був знайдений розв’язок там ми знаходимося не на нульовому рядку:

      1. Прибрати ферзя з попереднього рядку

      2. Виконати пункт 3 для попереднього рядку

Відеокопії екрана

Аналіз достовірності результатів

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

Обхід конем шахової дошки

Умова задачі [2]

Знайти спосіб обходу конем шахової дошки розміром , так щоб на кожній клітинці побувати лише один раз.

Вхідні та вихідні тести

Вхідні дані – це два цілих числа та , що відповідають розміру шахової дошки.

Під час виконання програма знаходить та виводить на екран користувачу спосіб обходу шахової дошки у вигляді зображення номеру кроку на кожній клітинці дошки. Якщо задача розв’язку не має, то виводиться повідомлення про відсутність розв’язку.

Приклад 1:

Розмір дошки

Знайдений спосіб обходу:

1 14 19 24 3

20 25 2 9 18

15 8 13 4 23

12 21 6 17 10

7 16 11 22 5

Приклад 2:

Розмір дошки

Знайдений спосіб обходу:

1 28 31 54 3 60 33 64

30 53 2 27 32 63 4 59

19 26 29 52 55 58 61 34

42 51 18 25 62 49 56 5

17 20 43 50 57 24 35 48

44 41 14 21 38 47 6 9

13 16 39 46 11 8 23 36

40 45 12 15 22 37 10 7