Курсовая работа по предмету «Программирование»

На тему «Поиск пути в двумерном лабиринте с особенностью»

Задание:

Речь Комментарий: Основное задание приведено выше. Особенность – случайное заполнение с двумя стенами. Алгоритм генерации стартового поля 1. Все поле заполняется нулями 2. На поле случайно размещаются k единиц 3. В середине поля добавляются две горизонтальные линии длины w, одна прижата к левому краю, другая прижата к правому краю. Проварьировать: • количество единиц k – от 0 до n2, шаг не более 0.1 n2 • длину линий w – от 1 до n, шаг не более 0.1 n. Основы программирования предмет Поиск пути в двумерном лабиринте Дано двумерное поле размера n × n, содержащее лабиринт с толстыми стенками. Для простоты можно считать его просто массивом, заполненным значениями 0 и 1, где 0 соответствует пустому пространству, 1 – стенке. Поле генерируется случайно по правилам, определенным в индивидуальном задании. Требуется проверить, есть ли непрерывный путь из верхней левой ячейки в нижнюю правую. При этом соседними считаются ячейки, соединенные по горизонтали либо по вертикали, т.е у ячейки есть 4 соседа (окрестность фон Неймана). Размер поля считается фиксированным. Потренироваться можно на поле 10 × 10, но итоговый анализ лучше провести на поле побольше – 50 или 100 (выбрать можно в зависимости от длительности вычислений). Требуется провести исследование: изучить зависимость наличия/отсутствия пути в лабиринте от двух параметров модели (данных в индивидуальном задании): • процент заполнения поля или аналогичная величина; • параметр алгоритма генерации (ширина решетки, размер случайно генерируемых блоков или пустот, или что-то иное). Т.к. поле генерируется с элементом случайности, по одной генерации сделать вывод сложно, поэтому при анализе зависимости нужно для каждой комбинации параметров провести 10 расчетов (с разным стартовым распредлением) и усреднить результат. Поэтому на выходе для каждой пары значений входных параметров будет не булево значение «путь есть / пути нет», а вероятность существования пути. Если увеличить число повторов, вероятность будет определена точнее. Нужно определить зависимость от двух параметров, поэтому нужно будет проварьировать каждый параметр с некоторым шагом и провести расчеты для всех выбранных комбинаций. Например, если первый параметр – процент заполнения, то можно рассмотреть 0 %, 10 %, 20 %, … 100 % - т.е. 11 вариантов (на самом деле 9, т.к. 0 и 100 просчитывать бесполезно, но в некоторых вариантах границы имеют значение, и их нельзя будет отбросить). Второй параметр также задан на отрезке, и можно выбрать около 8-10 равноотстоящих точек. Суммарно комбинаций будет около 100, но их нужно считать в цикле, не нужно перебирать вручную и запускать каждый случай отдельно. Тогда на выходе у Вас будет квадратный массив значений, который надо будет как-то визуализировать (в виде набора двумерных графиков или одного трехмерного графика) и сделать вывод. Алгоритм, находящий путь в случайном двумерном лабиринте, следует разработать и протестировать отдельно – например, на поле различной размерности, просто случайно заполненным с вероятностью, например, 50%. Примеры можно посмотреть в приведенных в основном описании книгах. Основное задание приведено выше. Особенность – случайное заполнение с двумя стенами. Алгоритм генерации стартового поля 1. Все поле заполняется нулями 2. На поле случайно размещаются k единиц 3. В середине поля добавляются две горизонтальные линии длины w, одна прижата к левому краю, другая прижата к правому краю. Проварьировать: • количество единиц k – от 0 до n2, шаг не более 0.1 n2 • длину линий w – от 1 до n, шаг не более 0.1 n. вот это написано в личке