ДВЕ лабораторные работы
ПОЛНОЕ ЗАДАНИЕ В ДЕМО ФАЙЛЕ
+ ДЛЯ ПОИСКА ДУБЛИРУЮ НИЖЕ
Лабораторная работа № 2. Тема: Графы и обходы
1. Практика «Поиск в ширину»
Скачайте проект Dungeon
На карте расположено несколько сундуков. Для тех сундуков, до которых существует
путь от точки start, необходимо найти путь от сундука до точки start в виде односвязного
списка SinglyLinkedList.
Для этого в классе BfsTask нужно реализовать поиск в ширину с указанной
сигнатурой. Кстати, он вам понадобится и для следующей задачи!
Проверить корректность своего решения можно запустив тесты в классе Bfs_Should.
Там же, по тестам, можно уточнить постановку задачи на различных крайних случаях.
После корректного выполнения задания, можно будет запустить проект. Кликнув на
пустую ячейку вы увидите найденный вашим алгоритмом путь.
Подсказки:
• Начните поиск в ширину из точки start и продолжайте, пока очередь поиска в ширину
не опустеет.
• Чтобы быстро проверять, содержит ли клетка лабиринта сундук, можно
воспользоваться уже знакомой структурой данных Dictionary или изучить более
подходящую для данной задачи структуру данных HashSet.
• Реализация поиска в ширину немного упростится, если хранить в очереди не просто
координаты точки, а объект SinglyLinkedList, сохраняющий ещё ссылку на
предыдущую точку пути.
• Односвязные списки путей до разных сундуков могут иметь общие «хвосты».
Примерно так же как было в задаче CVS в одной из предыдущих недель.
• Возвращать пути до всех достижимых сундуков можно «лениво» с помощью
оператора yield return
2. Практика «Вынести клад!»
Продолжайте в том же проекте Dungeon
Подготовка закончилась и вы в настоящем лабиринте с сокровищами! Сил хватит
только на один сундук и то еле-еле. Найдите кратчайший путь из начальной точки до выхода,
проходящий через хотя бы один сундук.
Решайте задачу в классе DungeonTask.
Детали реализации для граничных случаев можно найти в классе с тестами
Dungeon_Should. Сделайте так, чтобы все тесты проходили.
После выполнения этого задания, при запуске проекта можно увидеть визуализацию
пути. Наслаждайтесь найденными сокровищами!
Эту задачу можно элегантно решить без циклов, используя LINQ.
Подсказки:
• Придумайте, как можно наиболее экономно свести эту задачу к поиску кратчайших
путей
• Можно обойтись всего двумя поисками в ширину — одним от стартовой точки и ещё
одним от выхода
• Не забудьте о декомпозиции — разбейте ваше решение на логические блоки и каждый
поместите в свой метод с понятными именами!
• Объединить результаты двух поисков в ширину сделать проще простого с помощью
Linq-метода Join. Изучите его самостоятельно — это будет полезно!
• Reverse — это одновременно метод класса List, а также Linq-метод расширение. Но в
первом случае он модифицирует список и не имеет возвращаемого значения, а во
втором ничего не модифицирует, а возвращает новую перевёрнутую коллекцию.
Смотрите, не запутайтесь!
• Преобразовать список точек в список MoveDirection можно без циклов с помощью
Linq-методов Zip и Skip
3. Практика «Поделить территорию!»
Скачайте проект Rivals.
Оказалось, что в лабиринте есть и другие охотники за сокровищами. Естественно, кто
первый доберется до сундука, тот его и заберет себе.
Неплохо бы знать, кто из соперников до каких клеток лабиринта успеет добраться
быстрее других.
В классе RivalsTask реализуйте функцию разделяющую карту между игроками.
Нужно определить, до каких из клеток карты каждый игрок сможет дойти быстрее, вне
зависимости от тактики остальных. Ходят игроки по очереди, начиная с первого.
Сделайте так, чтобы все тесты в классе Rivals_Should проходили.
После выполнения этого задания, при запуске проекта можно увидеть визуализацию
процесса раздела карты.
Подсказки:
• Подумайте, как эффективно решить эту задачу с помощью поиска в ширину
• Охотников за сокровищами может быть много. Очень много!
• Поиск в ширину можно начинать сразу из нескольких стартовых точек.
___
Лабораторная работа № 2. Тема: Графы и обходы
1. Практика «Поиск в ширину»
Скачайте проект Dungeon
На карте расположено несколько сундуков. Для тех сундуков, до которых существует
путь от точки start, необходимо найти путь от сундука до точки start в виде односвязного
списка SinglyLinkedList.
Для этого в классе BfsTask нужно реализовать поиск в ширину с указанной
сигнатурой. Кстати, он вам понадобится и для следующей задачи!
Проверить корректность своего решения можно запустив тесты в классе Bfs_Should.
Там же, по тестам, можно уточнить постановку задачи на различных крайних случаях.
После корректного выполнения задания, можно будет запустить проект. Кликнув на
пустую ячейку вы увидите найденный вашим алгоритмом путь.
Подсказки:
• Начните поиск в ширину из точки start и продолжайте, пока очередь поиска в ширину
не опустеет.
• Чтобы быстро проверять, содержит ли клетка лабиринта сундук, можно
воспользоваться уже знакомой структурой данных Dictionary или изучить более
подходящую для данной задачи структуру данных HashSet.
• Реализация поиска в ширину немного упростится, если хранить в очереди не просто
координаты точки, а объект SinglyLinkedList, сохраняющий ещё ссылку на
предыдущую точку пути.
• Односвязные списки путей до разных сундуков могут иметь общие «хвосты».
Примерно так же как было в задаче CVS в одной из предыдущих недель.
• Возвращать пути до всех достижимых сундуков можно «лениво» с помощью
оператора yield return
2. Практика «Вынести клад!»
Продолжайте в том же проекте Dungeon
Подготовка закончилась и вы в настоящем лабиринте с сокровищами! Сил хватит
только на один сундук и то еле-еле. Найдите кратчайший путь из начальной точки до выхода,
проходящий через хотя бы один сундук.
Решайте задачу в классе DungeonTask.
Детали реализации для граничных случаев можно найти в классе с тестами
Dungeon_Should. Сделайте так, чтобы все тесты проходили.
После выполнения этого задания, при запуске проекта можно увидеть визуализацию
пути. Наслаждайтесь найденными сокровищами!
Эту задачу можно элегантно решить без циклов, используя LINQ.
Подсказки:
• Придумайте, как можно наиболее экономно свести эту задачу к поиску кратчайших
путей
• Можно обойтись всего двумя поисками в ширину — одним от стартовой точки и ещё
одним от выхода
• Не забудьте о декомпозиции — разбейте ваше решение на логические блоки и каждый
поместите в свой метод с понятными именами!
• Объединить результаты двух поисков в ширину сделать проще простого с помощью
Linq-метода Join. Изучите его самостоятельно — это будет полезно!
• Reverse — это одновременно метод класса List, а также Linq-метод расширение. Но в
первом случае он модифицирует список и не имеет возвращаемого значения, а во
втором ничего не модифицирует, а возвращает новую перевёрнутую коллекцию.
Смотрите, не запутайтесь!
• Преобразовать список точек в список MoveDirection можно без циклов с помощью
Linq-методов Zip и Skip
3. Практика «Поделить территорию!»
Скачайте проект Rivals.
Оказалось, что в лабиринте есть и другие охотники за сокровищами. Естественно, кто
первый доберется до сундука, тот его и заберет себе.
Неплохо бы знать, кто из соперников до каких клеток лабиринта успеет добраться
быстрее других.
В классе RivalsTask реализуйте функцию разделяющую карту между игроками.
Нужно определить, до каких из клеток карты каждый игрок сможет дойти быстрее, вне
зависимости от тактики остальных. Ходят игроки по очереди, начиная с первого.
Сделайте так, чтобы все тесты в классе Rivals_Should проходили.
После выполнения этого задания, при запуске проекта можно увидеть визуализацию
процесса раздела карты.
Подсказки:
• Подумайте, как эффективно решить эту задачу с помощью поиска в ширину
• Охотников за сокровищами может быть много. Очень много!
• Поиск в ширину можно начинать сразу из нескольких стартовых точек.
