Розв’язання простих лабіринтів
Правила проходу по лабіринту. Розв'язання лабіринтів, що містять замкнені петлі і розгалуження. Розробка структури програмного забезпечення. Опис призначення полів і методів класів. Розробка алгоритму функціонування. Перевірка коректності лабіринту.
Рубрика | Программирование, компьютеры и кибернетика |
Вид | контрольная работа |
Язык | украинский |
Дата добавления | 07.08.2013 |
Размер файла | 4,9 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Вступ
Програма призначена для розв'язання простих лабіринтів, які складаються з клітин, які містять одиниці або нулі. Одиниці позначають зайняті клітини, на які заборонено заходити, а нулі - порожні.
Програма завантажує лабіринт із файлу, виконує побудову лабіринту, знаходить шлях до виходу (якщо він існує) і будує шлях розв'язання.
Постановка задачі
Лабіринт являє собою матрицю з одиниць і нулів і зберігається у файлі.
Для проходу по лабіринту існують наступні правила:
· Шлях починається у точці старту (позначається як «2»), а закінчується у точці фінішу (позначається як «3»).
· Клітина, що містить одиницю, вважається закритою, на неї заборонено входити.
· Ходи можливі лише на сусідні клітини, якщо вони вільні (містять нуль)
· Ходи по діагоналі заборонено
Програма повинна знаходити шлях від старту до фінішу, виводити попередження, якщо лабіринт не має розв'язання або введений невірно, а також графічно будувати лабіринт і шлях розв'язання.
Також необхідно передбачити перевірку вхідних даних на коректність і вивести попередження, якщо данні не відповідають необхідним умовам.
Алгоритм розв'язання повинен розв'язувати не лише лінійні лабіринти, а і лабіринти, що містять замкнені петлі і розгалуження.
Розробка структури програмного забезпечення
Програма містить чотири класи, які безпосередньо використовуються для виконання поставленої задачі
· Point - описує «клітину» лабіринту
· Labyrinth - описує матрицю лабіринту, яка складається з клітин
· Solver - наслідує клас Labyrinth, містить методи для розв'язання лабіринту
· vGraphics - містить методи для візуалізації роботи програми
Опис призначення полів і методів класів |
|||
Тип |
Назва |
Призначення |
|
Point |
|||
Поле |
value |
Містить значення клітини |
|
Поле |
x |
Містить x-координату клітини |
|
Поле |
y |
Містить y-координату клітини |
|
Метод |
Point |
Конструктор, створює нову клітину з заданими координатами і значенням |
|
Метод |
getvalue |
Повертає значення клітини |
|
Метод |
getx |
Повертає x-координату клітини |
|
Метод |
gety |
Повертає y-координату клітини |
|
Labyrinth |
|||
Поле |
M |
Містить кількість рядків лабіринту |
|
Поле |
N |
Містить кількість стовбців лабіринту |
|
Поле |
Maze |
Містить матрицю клітин (Point) розмірністю MxN |
|
Метод |
Labyrinth |
Конструктор, створює лабіринт, заповнюючи його даними з файлу |
|
Solver |
|||
Поле |
Start |
Містить клітину, з якої починається шлях |
|
Поле |
Finish |
Містить клітину, в якій закінчується шлях |
|
Поле |
IsSolved |
Містить "true", якщо лабіринт розв'язано |
|
Поле |
P_Solution |
Містить стек клітин, які є розв'язком лабіринту |
|
Поле |
VisitedPoints |
Містить масив клітин, які були відвідані під час розв'язання |
|
Метод |
Correct |
Повертає "true", якщо введено коректний лабіринт з одним стартом і фінішем |
|
Метод |
GetPath |
Повертає стек клітин, які є розв'язком для побудови |
|
Метод |
GetSolutionPath |
Виконує пошук шляху, повертає "true", якщо існує розв'язок |
|
Метод |
GetStartAndFinish |
Знаходить старт і фініш, присвоює їх відповідним полям |
|
Метод |
Solve |
Розв'язує лабіринт, або повертає "false", якщо розв'язку не існує |
|
Метод |
Solver |
Конструктор, створює новий екземпляр класу, завантажує лабіринт з файлу |
|
Метод |
Visited |
Перевіряє, чи була відвідана задана клітина |
|
vGraphics |
|||
Поле |
G |
Містить екземпляр System::Graphics для виконання функцій малювання |
|
Поле |
S |
Містить екземпляр Solver для візуалізації лабіринту і розв'язку |
|
Поле |
ln_w |
Містить товщину позначки шляху-розв'язку |
|
Поле |
sq_a |
Містить товщину клітини лабіринту |
|
Метод |
BuildMaze |
Будує лабіринт |
|
Метод |
BuildSolution |
Будує розв'язок лабіринту |
|
Метод |
vGraphics |
Конструктор, створює новий екземпляр класу, розраховує ln_w та sq_a |
Схема класів
Розробка алгоритму функціонування
лабіринт програмний алгоритм коректність
Блок-схема метода Solver::GetSolutionPath, який виконує пошук шляху розв'язання
Блок-схема метода Solver::Correct, який виконує перевірку коректності лабіринту
Блок-схема метода vGraphics::BuildSolution, який виконує побудову точок шляху
Розробка програмного забезпечення
Тестування програмного забезпечення
Для тестування програми було використано наступні файли:
· Maze_1.vmz, Maze_2.vmz, Maze_3.vmz - файли, які містять звичайні лабіринти.
· Maze_1_with_start_and_finish_error.vmz - лабіринт без старту і з двома фінішами
· Maze_1_without_exit.vmz - лабіринт, який не має виходу
· wrong_file.vmz - файл з розширенням лабіринту, який містить довільний текст, який не є лабіринтом
Тести звичайних лабіринтів:
Maze_1.vmz
Maze_2.vmz
Maze_3.vmz
Як видно з результатів тестування, програма коректно знаходить шлях розв'язку, не має за циклювань на петлях та розгалуженнях
Тестування файлів з помилками:
Maze_1_with_start_and_finish_error.vmz
Maze_1_without_exit.vmz
wrong_file.vmz
Отже, програма має захист від можливих помилок у вхідних даних, повідомляє про них користувача. Помилки у вхідних даних не впливають на правильність роботи програми
Інструкція користувача
Інтерфейс програми
Вікно програми складається з трьох областей:
1. Меню функцій
2. Інформація про відкритий лабіринт
3. Графічне зображення лабіринту
Кнопки в меню функцій стають активними при виконанні попередньої функції.
Для відкриття лабіринту необхідно натиснути кнопку загрузки лабіринту та вказати файл з розширенням .vmz.
Якщо файл було відкрито без помилок, з'являється інформація про розмір лабіринту, а також стане активною кнопка побудови.
При побудові лабіринту у графічній частині з'являється зображення, а також стає активною функція розв'язання, яка будує шлях-розв'язок.
У програмі можливі наступні помилки та попередження:
Виникає при спробі відкрити файл, що містить дані, які не можуть бути розпізнані як лабіринт
Виникає при спробі розв'язати лабіринт без старту/фінішу, або якщо їх більше ніж потрібно
Інформаційне попередження, з'являється при спробі розв'язати лабіринт, що не має жодного шляху від старту до фінішу.
Размещено на Allbest.ru
Подобные документы
Розв’язання нелінійних алгебраїчних рівнянь методом хорд. Опис структури програмного проекту та алгоритмів розв’язання задачі. Розробка та виконання тестового прикладу. Інші математичні способи знаходження коренів рівнянь, та опис виконаної програми.
курсовая работа [4,1 M], добавлен 28.09.2010Постановка та описання алгоритму розв’язання задачі про оптимальне призначення, формулювання вимог. Обґрунтування вибору засобів програмування. Розробка структури програми та системи її візуалізації, тестування та верифікація, оцінка ефективності.
курсовая работа [1,1 M], добавлен 12.05.2013Технологія візуального проектування. Аналітичне розв’язання задачі в загальному вигляді. Програмування в консольному режимі. Сценарій розв’язання задачі в Delphi та блок-схема алгоритму. Програмний код додатку та опис інтерфейсу з екранними копіями.
курсовая работа [2,4 M], добавлен 22.06.2009Виконання "ручного" розв'язування рівняння методом Ньоютона. Розробка програми на мові С#, яка реалізує введення вихідних даних, розв'язання заданого рівняння, виведення результатів у зручній формі на екран. Визначення початкового наближення кореня.
лабораторная работа [120,9 K], добавлен 19.01.2022Розробка програми для розв’язання квадратних рівнянь з текстовим та графічним інтерфейсами користувача без дублювання їх коду. Алгоритм розв’язання квадратного рівняння у програмах з будь-яким інтерфейсом користувача, а саме: "консольний" та "форма".
лабораторная работа [14,9 K], добавлен 14.05.2011Розв’язання нелінійних алгебраїчних рівнянь методом дихотомії. Вирішення задачі знаходження коренів рівняння. Розробка алгоритму розв’язання задачі і тестового прикладу. Блок-схеми алгоритмів основних функцій. Інструкція користувача програмою мовою С++.
курсовая работа [2,0 M], добавлен 24.09.2010Аналіз предметної галузі задачі моделювання пострілу балісти через стіну по мішені. Структури даних та діаграми класів для розв'язання задачі. Схеми взаємодії об’єктів та алгоритми виконання їх методів. Опис розробленої програми, інструкція користувача.
курсовая работа [1,0 M], добавлен 18.05.2014Оптимізація перевезення продуктів із пунктів відправлення до пунктів споживання. Зниження транспортних витрат, розробка і використання оптимальних схем вантажних потоків. Архітектура програмного забезпечення в середовищі Microsoft Visual Studio 2010.
курсовая работа [675,3 K], добавлен 10.03.2013Загальні відомості та геометричний зміст розв'язання задачі Коші. Використання методу Ейлера для розв'язання звичайних диференціальних рівнянь першого порядку. Розробка блок-схеми та реалізація алгоритму в середовищі програмування Borland Delphi 7.0.
курсовая работа [398,1 K], добавлен 14.10.2012Застосування симплекс-методу для розв’язання оптимізаційних задач лінійного програмування, що містять три змінні. Функції ітераційної обчислювальної процедури, що виконують приведення до зручного для розв’язання оптимального вигляду ЗЛП за кілька кроків.
курсовая работа [359,5 K], добавлен 18.09.2013