[Udemy] Алгоритм X Dancing Links сборки пентамимо на C# (Евгений Волосатов)

​ Теоретическое и практическое знакомство с гениальным "Алгоритмом икс" Дональда Кнута с примерами ​ Чему вы научитесь Поймут суть алгоритма X для быстрого поиска решений Решат задачу расстановки пентамимо с использованием алгоритма Dancing Links Требования Логическое мышление Основы языка программирования C# В этой серии уроков мы познакомимся с гениальным алгоритмом X Дональда Кнута - Dancing Links. Этот алгоритм можно применять для решения самых разных комбинаторных задач, например, заполнение области Пентамимо-фигурами, решение Судоку, размещение ферзей на шахматной доске и так далее. В первой части курса "Теория" мы разберём принцип работы алгоритма, выполним его построчно "ручками" на конкретном примере, чтобы лучше понять, как он устроен и как работает. Во второй части курса "Практика" мы реализуем на C# двух- и четырёх-связных списков и дальнейшей реализации "Алгоритма Икс" Дональда Кнута. и напишем весь алгоритм. Во третьей части курса "Пентамимо" мы применим созданный алгоритм к конкретной олимпиадной задаче по размещению пентамимо-фигур в заданной области. Алгоритм Икс решает эту задачу максимально быстро, так как отметает множество тупиковых веток - он их просто пропускает и делает это красиво. Если вам нравятся алгоритмы - обязательно пройдите этот курс, не пожалеете. Какова целевая аудитория? Для любителей алгоритмов Для инженеров и программистов Для студентов с лабораторкой по Dancing Links Этот алгоритм можно применять для решения самых разных комбинаторных задач, например, разложение Пентамимо, решение Судоку, размещение ферзей и так далее. Ссылки на статью Дональда Кнута и обзорная статья на Хабре с описанием данного алгоритма — внизу описания урока. Самостоятельное задание: 1. Внимательно прослушать и просмотреть видео. 2. Подходит ли данный алгоритм для решения задачи Судоку или Парад Ферзей. 3. Приложить интересную картинку на тему урока. Работа алгоритма - 12:43 На этом уроке мы пошагово рассмотрим статью на Хабре (см. ссылки ниже). Самостоятельное задание: 1. Внимательно прослушать и просмотреть видео. 2. Напишите своё мнение по поводу данного урока. 3. Самостоятельно рассмотреть варианты поиска решения. 4. Приложить скриншот проработанного алгоритма. Двусвязный список с удалением - 10:46 На этом уроке мы пошагово рассмотрим статью автора данного алгоритма — Дональда Кнута, и рассмотрим пошаговое удаление и возвращение элемента. Самостоятельное задание: 1. Внимательно прослушать и просмотреть видео. 2. Нарисовать циклический список из 4 элементов ABCD. 3. Проработать весь алгоритм самостоятельно. 4. Приложить скриншот проработанного алгоритма. 5. * Продемонстрировать удаление/восстановление всех элементов. Практика - 01:54:55 Расширение хоровода - 24:08 На этом уроке мы наконец приступим к реализации двусвязного списка на языке C#. Самостоятельное задание: 1. Внимательно прослушать и просмотреть видео. 2. Создать новый проект AlgorithmX. 3. Создать новый класс Cell(). 4. Добавить необходимые переменные и конструктор в классе Cell(). 5. Избавиться от статика в классе Program(). 6. Реализовать функцию test() в классе Program(). 7. Реализовать функцию InsertLeft() в классе Cell(). 8. Доработать конструктор в классе Cell(). 9. Доработать функцию test() в классе Program(), использовав InsertLeft(). 10. Приложить скриншот результата. Заголовки столбцов - 12:17 На этом уроке мы реализуем перемещение вверх/вниз для реализации четырёх-связного списка, а также создадим класс Header(), для того чтобы знать, в каком столбце мы находимся. Самостоятельное задание: 1. Внимательно прослушать и просмотреть видео. 2. Добавить новые переменные в классе Cell(). 3. Доработать в конструктор класса Cell() начальные значение новых переменных. 4. Реализовать функцию InsertUp() в классе Cell(). 5. Создать класс Header() с необходимыми переменными. 6. Заменить переменную name на header в классе Cell(). 7. Добавить конструктор в классе Header(). 8. Доработать функцию test() в классе Program(), использовав InsertUp() и Header(). 9. Приложить скриншот результата. Единичная матрица - 25:01 На этом уроке, используя созданный ранее четырёх-связный список, мы добавим необходимые нам элементы для дальнейшем работы с ними. Самостоятельное задание: 1. Внимательно прослушать и просмотреть видео. 2. Создать класс Dance() с необходимыми переменными. 3. Добавить конструктор в классе Dance(). 4. Модифицировать тип переменной name в классе Header(). 5. Реализовать функцию AddRow() в классе Dance(). 6. Реализовать функцию start() в классе Program(), использовав класс Dance(). 7. Приложить скриншот результата. 8. * Добавить все 12 строчек по образцу. Как ссылки пошли впляс - 21:15 На этом уроке мы реализуем заготовку функции Dance() в классе Dance(). Самостоятельное задание: 1. Внимательно прослушать и просмотреть видео. 2. Добавить все 12 строчек в матрицу. 3. Реализовать функцию Dance() в классе Dance(). 4. Создать заглушки для функций Cover/Uncover(). 5. Добавить вывод текущего шага в функции Dance(). 6. Приложить скриншот результата. Открытие/закрытие столбцов - 32:14 На этом уроке мы доработает функции AddRow() и Dance() в классе Dance(), а также реализуем функции Cover/Uncover(). Самостоятельное задание: 1. Внимательно прослушать и просмотреть видео. 2. Добавить номер строки в классе Cell(). 3. Доработать функцию AddRow() в классе Dance(). 4. Доработать функцию Dance() в классе Dance(), использовав стек для хранения целых чисел. 5. Реализовать функции Cover/Uncover() в классе Dance(). 6. Перенумеровать ячейки от 0 до 11, чтобы избавиться от пустых столбцов. 7. Приложить скриншот результата. Пентамимо - 01:40:26 Фигуры из пентамимо - 18:16 На этом уроке мы приступаем к решению олимпиадной задачи "Пентамино", заполнив массив всеми вариантами расположения фигур. Ссылка на файл с кодом функции инициализации фигур на С# — внизу. Самостоятельное задание: 1. Внимательно прослушать и просмотреть видео. 2. Создать структуру Figure() и Variant(). 3. Создать класс Pentaminos(). 4. Заполнить массив всеми 63 вариантами расположения фигур в классе Pentaminos(). 5. Создать функцию startPent() в классе Program(). 6. Проверить заполнение массива всеми вариантами фигур. 7. Приложить скриншот результата. 8. ** Доработать функцию startPent() для решения поставленной задачи. 9. *** Реализовать генератор всевозможных расположений фигур. Фигуры в консоли - 14:59 На этом уроке мы решили реализовать возможность отображения фигур в консоли, чтобы в дальнейшем видеть, что происходит в процессе работы алгоритма. Ссылка на файл с кодом функции инициализации фигур на С# — внизу. Самостоятельное задание: 1. Внимательно прослушать и просмотреть видео. 2. Реализовать функцию Show() в классе Figure(). 3. Добавить в классе Figure() строку символов фигур. 4. Доработать функцию startPentamino() в классе Program() для отображения фигур. 5. Реализовать перегрузку функции Show() в классе Figure() для более короткой записи. 6. Использовать короткую запись в функции startPentamino() класса Program(). 7. Приложить скриншот результата. 8. * Вывести все 12 фигур в консоли. Матрица Пентагона - 15:55 На этом уроке мы завершим реализацию функции поиска решения Пентамино. Ссылка на файл с кодом функции инициализации фигур на С# — внизу. Самостоятельное задание: 1. Внимательно прослушать и просмотреть видео. 2. Реализовать алгоритм перебора всех вариантов расположения фигур Пентамино. 3. Дождаться завершения работы алгоритма и написать время ожидания. 4. Приложить скриншот результата. Пентагон в деталях - 09:40 На этом уроке мы воспользуемся функцией Show() в классе Figure() для визуализации генерации всех вариантов расположения фигур Пентамино. Ссылка на файл с кодом функции инициализации фигур на С# — внизу. Самостоятельное задание: 1. Внимательно прослушать и просмотреть видео. 2. Исправить ошибку прошлого урока связанную с nr++. 3. Использовать отображение генерации расположения вариантов фигур через функцию Show(). 4. Добавить задержку после вывода каждого варианта расположения фигур по нажатию клавиш. 5. Реализовать функцию Hide() в классе Figure(). 6. Использовать функцию Hide() вместо Console.Clear(). 7. Приложить скриншот результата. Пентагон ищет решение - 22:01 На этом уроке мы визуализируем поиск решения Пентамино с использованием yield. Ссылка на файл с кодом функции инициализации фигур на С# — внизу. Самостоятельное задание: 1. Внимательно прослушать и просмотреть видео. 2. Модифицировать функцию Dance() в классе Dance(), чтобы она возвращала IEnumerable. 3. Воспользоваться возвращаемым IEnumerable для визуализации текущего состояния поиска решений. 4. Модифицировать работу рекурсии с использованием yield return. 5. Создать структуру FigureRow для хранения расположения фигуры на поле. 6. Использовать динамический список для хранения объектов FigureRow. 7. Добавить конструктор для удобства добавления информации в список. 8. Сделать структуру FigureRow глобальной. 9. Реализовать функции Show/Hide() с параметром FigureRow. 10. Добавить задержку между отображением/стиранием текущего состояния поиска решения. 11. Приложить скриншот результата. 12. * Дождаться окончания поиска решений. Десятикратная оптимизация - 19:35 В завершение знакомства с гениальным "алгоритмом X" Дональда Кнута — Dancing Links, мы оптимизируем наш алгоритм поиска решения Пентамино. Ссылка на файл с кодом функции инициализации фигур на С# — внизу. Самостоятельное задание: 1. Внимательно прослушать и просмотреть видео. 2. Оптимизировать функцию Dance() в классе Dance(). 3. Реализовать счётчик количество найденных вариантов. 4. Реализовать счётчик времени потраченного на поиск решений. 5. Поэкспериментировать с разными размерами поля. 6. Убрать геттеры/сеттеры в классе Cell() для многократного ускорения работы алгоритма. 7. Приложить скриншот результата. 8. *** Реализовать решение Судоку, используя данный алгоритм. 9. *** Реализовать решение Парад Ферзей, используя данный алгоритм. О преподавателе Евгений Волосатов Магистр математики и информатики, C#, Java, PHP программист Я — Игромистр. Моё призвание — показать пошаговый процесс создания игровых и прикладных программ, с нуля до результата. Меня зовут Волосатов Евгений Витольдович, мне 40 лет, живу в Литве, закончил Вильнюсский государственный университет магистром математики и информатики, также имею педагогическое образование. За плечами сотни различных проектов на C#, Java, PHP, ASP.NET, SQL и т.д. Всю свою сознательную жизнь я пишу программы и обучаю этому других.