Первое домашнее задание. Лабиринт (1127051)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Домашнее задание 1.ЛабиринтОбщее описание заданияЗадание направленно на проверку знаний основ языка C++ у студентов и знакомствос основными алгоритмами на графах. Задание состоит из следующих этапов:1.написание программы на языке С++, решающую задачу поискаминимального пути в лабиринте (см. описание ниже);2.проведение тестирования написанной программы с точки зрениякорректности работы программы;3.теоретический анализ времени работы используемого алгоритма и замерыпроизводительности полученной реализации указанного алгоритма;4.написание отчета, описывающего результаты всех указанных этапов.Выполненное задание разместить в соответствующей именной папке в Dropbox вотдельной папке с названием «Autumn 2014 - Homework 1» (Приглашения в ближайшеевремя придут по почте, имя папки совпадает с Вашим login-ом, который Вы указали вАнкете).

Любые вопросы (в том числе, если у Вас есть возражения, связанные сиспользованием Dropbox) по заданию присылать по электронной почте на следующийадрес: mikle.shupletsov@gmail.com. Тема письма имеет следующий формат: [318][Фамилия Имя] [Вопрос].ЛабиринтЛабиринт состоит из нескольких уровней.

Соседние уровни соединены при помощилестниц. Каждый уровень в лабиринте представляет собой квадрат из N на N клеток, гдекаждая клетка может быть одной из следующих типов: ‘.’ – пустое пространство (по нему можно передвигаться); ‘#’ – стены лабиринта (клетки по которым нельзя перемещаться); ‘U’ – лестница на верхний уровень (из данной клетки можно перейти только науровень выше); ‘D’ – лестница на нижний уровень (из данной клетки можно перейти только науровень ниже); ‘P’ – портал (выход из лабиринта); ‘S’ – начальная точка.Передвигаться можно только вверх(‘n’), вниз (‘s’), влево (‘w’) и вправо (‘e’).Границы лабиринта можно считать непроходимыми, даже если они не окружены стенами(клетки ‘#’).Формат входных данных.Описание лабиринта считывается программой либо со стандартного потока ввода (cin),либо из файла.

При этом программа должна корректно обрабатывать следующие дваосновных формата описания лабиринта:1. «карта» - описание карты лабиринта по уровням (M);2. «координаты» - список координат элементов лабиринта (L).Каждая строка в указанных описаниях непосредственно относится к описанию форматаили является комментарием в стиле языка С (например, “//строка с комментарием”Формат «карта» (M)Первая строка содержит символ «M», указывающий тип входного формата. На второйстроке указывается одно целое число N – размер стороны любого из уровней лабиринта.На третьей строке указывается число K – число уровней в лабиринте (уровни лабиринтанумеруются с нулевого). Далее, следует описание всех клеток каждого из уровнейлабиринта, начиная с нулевого.Пример корректного входного описания лабиринта в формате «карта» (M):M42//level 0....#....#..#...//level 1.P.........S#.D#Формат «координаты» (L)Первая строка содержит символ «L», указывающий тип входного формата.

На второйстроке указывается одно целое число N – размер стороны любого из уровней лабиринта.На третьей строке указывается число K – число уровней в лабиринте (уровни лабиринтанумеруются с нулевого). Далее, следует описание лабиринта, в котором указываютсякоординаты всех элементов (кроме, возможно, клеток ‘.’, описывающих пустоепространство лабиринта). При этом каждая строка описывает координаты одной клетки иимеет следующий формат: (‘строка’, ‘столбец’, ‘уровень’, ‘символ’). Клетки лабиринтаописываются в произвольном порядке. Не исключается возможность, что описаниесодержит координаты пустого пространства.Пример корректного входного описания лабиринта в формате«координаты» (L):L42(1,0,0,#)(2,1,0,#)(3,0,0,#)(0,1,1,P)(2,3,1,S)(3,0,1,#)(3,2,1,D)(3,3,1,#)Формат выходных данныхРезультат поиска минимального пути передается программой либо в стандартный потоквывода (cout), либо в файл.

При этом программа должна корректно обрабатыватьследующие два основных формата описания результата:1. «карта» - минимальный путь на карте лабиринта (Map);2. «координаты» - список координат минимального пути (List).Формат «карта» (M)Первая строка содержит символ «M», указывающий тип входного формата. На второйстроке указывается одно целое число N – размер стороны любого из уровней лабиринта.На третьей строке указывается число K – число уровней в лабиринте (ровни лабиринтанумеруются с нулевого). Если путь не существует, то более никакой информации невыдается. В противном случае выдается описание всех клеток каждого из уровнейлабиринта, начиная с нулевого с указанием минимального пути от клетки ‘S’ до клетки‘P’.

Путь указывается следующим образом: символы всех клеток пустого пространства,которые находятся на минимальном пути, заменяются на символы ‘n’, ‘e’, ‘s’, ‘w’,‘d’ и ‘u’, которые указывают направление движения (изменения начинаются с клетки‘S’, при этом клетка портала ‘P’ не должна меняться).

Описание каждого уровняпредваряется строкой с комментарием, указывающим на уровень лабиринта (например,“//level 0”). Других комментариев выходной формат содержать не должен.Пример корректного выходного описания лабиринта в формате «карта»(M):M42//level 0....#....#..#...//level 1.Pww...n...n#.d#Формат «координаты» (L)Первая строка содержит символ «L», указывающий тип входного формата. На второйстроке указывается одно целое число N – размер стороны любого из уровней лабиринта.На третьей строке указывается число K – число уровней в лабиринте (уровни лабиринтанумеруются с нулевого).

Если путь не существует, то более никакой информации невыдается. В противном случае на следующей строке выдается целое число, котороехарактеризует длину минимального пути от клетки ‘S’ до клетки ‘P’(считаетсясуммарное число клеток в найденном пути, за исключением клетки с порталом (клетка‘P’)) и с новой строки выдается описание минимального пути, в котором указываютсякоординаты всех элементов задействованных в этом пути. При этом каждая строкаописывает координаты одной клетки и имеет следующий формат: (строка, столбец,уровень, направление), где направление один из следующих символов: ‘n’, ‘e’, ‘s’,‘w’, ‘d’ и ‘u’, указывающий направление движения из клетки. Клетки лабиринтаописываются в порядке прохождения пути, то есть от начальной клетки, в которой былсимвол ‘S’ до последней клетки пути, которая указывает на клетку с порталом (клетка ссимволом ‘P’).

Описание не должно содержать комментариев.Пример корректного входного описания лабиринта в формате«координаты» (L):L424(2,3,1,n)(1,3,1,n)(0,3,1,w)(0,2,1,w)Параметры командной строки.Программа должна поддерживать следующие параметры командной строки:1. –-help, -h – при передаче этого параметра программа должна вывести краткуюсправку о работе с программой, которая включает краткое описание программы, атакже все параметры командной строки и их назначение;2. –-input (M|L), -i (M|L) – параметр определяет тип входного формата (вскобках указаны возможные типы входного формата);3.

–-input_file “filename.txt”, -I “filename.txt” – если указан этотпараметр, то программа считывает вход из файла с именем “filename.txt”,если параметр не указан, то считывание происходит со стандартного потока ввода(cin);4. –-output (M|L), -o (M|L)– параметр определяет тип выходного формата (вскобках указаны возможные типы выходного формата);5. –-output_file “filename.txt”, -O “filename.txt”, -O - еслиуказан этот параметр, то программа записывает результат работы в файл с именем“filename.txt”, если параметр не указан, то запись происходит в стандартныйпоток вывода (cout);Примеры корректного задания параметров командной строкиMaze.exe --help //вывод краткой справки о работе программыMaze.exe –i M –o M /*программа считывает со стандартного потокаввода карту в формате М выдает результат своей работы встандартный поток вывода в формате М.*/Maze.exe --input M --output L -I test.txt –O result.txt//*программа считывает карту в формате М из файла test.txt изаписывает результат своей работы в файл result.txt в форматеL.*/Примеры некорректного задания параметров командной строкиMaze.exe –h –i M //не согласованные параметры коммандной строкиMaze.exe –i –o M //пропущен обязательный параметр при “-i”Maze.exe --input M -I test.txt –O result.txt /*не задан выходнойформат представления лабиринта.*/Maze.exe -o M -I test.txt /*не задан входной форматпредставления лабиринта.*/Тестирование программы и замеры производительности.Программа должна быть протестирована на предмет корректного решенияпоставленной задачи, корректного считывания входного и генерации выходного форматовпредставления лабиринта и минимального пути в нем.Должно быть проведено тестирование программы на случайно сгенерированныхлабиринтах разного размера.

Установить максимальные значения параметров лабиринта,при которых программа работает за приемлемое время (меньше одной минуты) и непревышает заданных ограничений по памяти (например, память Вашего компьютера) дляразных форматов описания лабиринта. Сравнить полученные данные с теоретическойоценкой времени работы реализованного Вами алгоритма поиска пути.Требования к отчетуОтчет по заданию должен содержать следующие основные разделы:1 Введение.2 Описание алгоритма.3 Результаты тестирования и замеры производительности.4 Список литературы.Раздел «Введение» содержит постановку задачи и краткое описание полученныхрезультатов.Раздел «Описание алгоритма» содержит описание реализованного алгоритма поискаминимального пути и теоретическую оценку времени его работы.Раздел «Результаты тестирования и замеры производительности» содержитописания того, как написанная программа тестировалась с точки зрения корректностирешения задачи, и результаты сравнения скорости работы программы на различныхвходных данных с теоретической оценкой времени работы алгоритма.

Для наглядноститребуется привести не только таблицы, но и графики. Кроме того, в этом разделе долженбыть приведен анализ полученных замеров производительности.Раздел «Список литературы» содержит ссылки на статьи и электронные ресурсы,если таковые были упомянуты в тексте отчета.Критерии оценкиРезультаты выполнения домашнего задания оцениваются по следующим основнымкритериям:1 корректность и качество реализации алгоритма поиска минимального пути;2 правильность считывания входных форматов и генерации выходного форматапредставления лабиринта и найденного минимального пути в нем;3 качество оформления кода (styleguide);4 тестирование программы и анализ производительности;5 структура и содержание отчета..

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов учебной работы