Розв’язання простих лабіринтів
Правила проходу по лабіринту. Розв'язання лабіринтів, що містять замкнені петлі і розгалуження. Розробка структури програмного забезпечення. Опис призначення полів і методів класів. Розробка алгоритму функціонування. Перевірка коректності лабіринту.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | контрольная работа |
| Язык | украинский |
| Дата добавления | 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Визначення і розв’язання задачі Коші для звичайних диференціальних рівнянь першого порядку методом Ейлера, алгоритм розв’язання, похибка при вирішенні. Складання блок-схеми. Реалізація алгоритму у середовищі Borland Pascal. Результат роботи програми.
курсовая работа [264,0 K], добавлен 20.08.2010Аналіз системи збору первинної інформації та розробка структури керуючої ЕОМ АСУ ТП. Розробка апаратного забезпечення інформаційних каналів, структури програмного забезпечення. Алгоритми системного програмного забезпечення. Опис програмних модулів.
дипломная работа [1,9 M], добавлен 19.08.2012Метод розв’язків рівнянь більш високих порядків. Вибір методу розв'язання задачі Коші. Методи розв'язання крайових задач розглядаються на прикладі звичайного диференціального рівняння другого порядку. Вибір методу інструментальних засобів вирішення задач.
курсовая работа [132,0 K], добавлен 03.12.2009Розробка програмного забезпечення для управління транспортними платформами на базі програмованого логічного контролера S7-300 в Simatic STEP-7. Аналіз програмного забезпечення, розрахунок показників його надійності. Опис алгоритму функціонування системи.
дипломная работа [2,1 M], добавлен 17.05.2012Огляд та аналіз методів розв’язання системи диференціальних рівнянь та вибір методів рішення. Алгоритми методів Ейлера. Вибір методу рішення задачі Коші. Рішення диференціальних рівнянь. Отримання практичних навиків програмування на мові Паскаль.
курсовая работа [174,3 K], добавлен 06.03.2010Стандартний спосіб розв’язання задачі Коші для звичайного диференціального рівняння першого порядку чисельними однокроковими методами. Геометричний зміст методу Ейлера. Побудова графіку інтегральної кривої. Особливість оцінки похибки за методом Рунге.
курсовая работа [112,9 K], добавлен 30.11.2009Види рівнянь та методи їх розв’язань. Чисельні методи уточнення коренів, постановка задачі. Рішення нелінійного рівняння методом простих та дотичних ітерацій. Використання програмних засобів. Алгоритми розв’язку задач. Програми мовою С++, їх тестування.
курсовая работа [232,2 K], добавлен 12.02.2013В роботі розглянуто наближені методи розв’язку нелінійних рівнянь. Для вказаних методів складено блок-схеми та написано програму, за якою розв’язується задане рівняння. Аналіз як самого рівняння і методів його розв’язання так і результатів обрахунку.
курсовая работа [302,8 K], добавлен 03.12.2009Розв'язання задач мовою програмування VBA з використанням алгоритмів лінійної, розгалуженої та ітераційної циклічної структури. Розробка блок-схеми алгоритму, таблиці ідентифікаторів та тексту програми. Створення власної панелі інструментів користувача.
практическая работа [1012,6 K], добавлен 19.02.2010Розробка програмного забезпечення для розв'язку системи лінійних рівнянь за формулами Крамера, головні особливості мови Turbo Pascal. Методи розв'язування задачі, архітектура програми та її опис. Контрольний приклад та результат машинного експерименту.
курсовая работа [47,7 K], добавлен 23.04.2010
