Практическое использование алгоритмов для нахождения минимального пути в лабиринте. Разработка программы на языке С и в среде Visual C . Основные способы поиска пути: метод волны и приоритетов. Описание разработанных функций и инструкция пользователя.
Аннотация к работе
В одном энциклопедическом словаре по поводу того, что такое язык, сказано следующее: "ЯЗЫК, 1) естественный язык, важнейшее средство человеческого общения. Я. неразрывно связан с мышлением; является социальным средством хранения и передачи информации, одним из средств управления человеческим поведением. Я. возник одновременно с возникновением общества в процессе совместной трудовой деятельности первобытных людей. Возникновение членораздельной речи явилось мощным средством дальнейшего развития человека, общества и сознания. Я. мира различаются строением, словарным составом и др., однако всем Я. присущи некоторые общие закономерности, системная организация единиц языка (например, парадигматические и синтагматические отношения между ними) и др.Цель работы - разработать программу которая бы наглядно продемонстрировала 2 метода поиска пути в лабиринте.1) "Метод волны" - нахождение минимально пути между точками в лабиринте, предпологается что лабиринт известен.Существует большое количество трассировщиков (программ для разводки платы), основанных на не меньшем количестве различных методов, занимающихся соединением двух контактов единым проводником.Но мы рассмотрим только один из них, самый простой (a значит,самый надежный и самый популярный) - волновой трассировщик. Поставим перед волновым трассировщиком задачу в терминах решаемой нами задачей: Имеется игровое поле Р(MXN),где M и N, соответственно, размер поля по вертикали и горизонтали.Годится он для всех карт, но без учета типа местности (вода, лес, болото ), но работает даже с неизвестной картой и никогда не зацикливается, кроме случая, когда нет выхода. Координаты выхода не требуются, главное, чтобы было ясно, что является выходом. Этот язык, сохранив средства ставшего общепризнанным стандартом для написания системных и прикладных программ языка С (процедурно-ориентированный язык), ввел в практику программирования возможности нового технологического подхода к разработке программного обеспечения, получившего название "объектно-ориентированное программирование". Внедрение в практику программирования объектно-ориентированной парадигмы дает развитие новых областей информатики, значительное повышение уровня технологичности создаваемых программных средств, сокращение затрат на разработку и сопровождение программ, их повторное использование, вовлечение в процесс расширения интеллектуальных возможностей ЭВМ. Во многих случаях программы, написанные на С , сравнимы по скорости с программами, написанными на языке ассемблера.В данной программе реализованы 2 метода поиска пути в либиринте, "метод волны" и "метод приоритетов". Создается массив для хранения лабиринта labirint и массив для прорисовки лабиринта LABSET. С помощью функции Volna создается массив lb и ряд вспомогательных переменных для вычисления минимального пути, "методом волны", между заданными точками в лабиринтемассив. В обе эти функции передается адрес исходного лабиринта и количество входов-выходов. После реализации каждого из методов результат работы этих функций выводится на экран с помощью функции LABOUT, в которую передается исходный лабиринт и массив для его прорисовки.Для начала работы с программой надо запустить фаил Find.exe после чего на экране появятся сведения о том что программа сама сгенирирует лабиринт после нажатия клавиши "ENTER".Результаты вычисления пути двумя методами предоставлены на рисунке ниже.bool Volna(int* lab,int kol); //Ф-ция алгоритма "волны" bool Prior(int* lab,int kol);//ф-ция алгоритма "метод приоритета".
План
СОДЕРЖАНИЕ
Вступление
1. Постановка задачи и сфера ее использования
2. Теоретическая часть
2.1 Метод волны
2.2 Метод приоритетов
3. Особенности работы в среде Visual C
4. Программная реализация
4.1 Описание алгоритма и структуры программы
4.2 Описание использованных программных средств
4.3 Описание разработанных функций
5. Инструкция пользователя
Выводы
Список литературы
Приложение Текст программы алгоритм лабиринт программа пользователь
Вывод
На рисунке видно что данная программа корректно решает поставленую перед нами задачу. Результаты вычисления пути двумя методами предоставлены на рисунке ниже.
Рис.1 -Результаты выполнения программы
Список литературы
Павловская Т.А. С/С .Программирование на языке высокого уровня-СПБ:Издательство "Питер",2008.-464с.
Керниган Б., Ритчи Д. Язык программирования Си: Пер. с англ.-М.: Финансы и статистика,2008.-272 с.
Глушаков С.В., Коваль А.В., Черпнин С.А. Программирование на Visual C 6.0: Издательство "Фолио", 2007. -721с. -(Учебный курс).