Алгоритм X Dancing Links сборки пентамимо на C#
5.0 (5 ratings)
Course Ratings are calculated from individual students’ ratings and a variety of other signals, like age of rating and reliability, to ensure that they reflect course quality fairly and accurately.
15 students enrolled

Алгоритм X Dancing Links сборки пентамимо на C#

Теоретическое и практическое знакомство с гениальным "Алгоритмом икс" Дональда Кнута с примерами
5.0 (5 ratings)
Course Ratings are calculated from individual students’ ratings and a variety of other signals, like age of rating and reliability, to ensure that they reflect course quality fairly and accurately.
15 students enrolled
Last updated 11/2018
Russian
Current price: $64.99 Original price: $99.99 Discount: 35% off
13 hours left at this price!
30-Day Money-Back Guarantee
This course includes
  • 4 hours on-demand video
  • Full lifetime access
  • Access on mobile and TV
  • Certificate of Completion
Training 5 or more people?

Get your team access to 4,000+ top Udemy courses anytime, anywhere.

Try Udemy for Business
What you'll learn
  • Поймут суть алгоритма X для быстрого поиска решений
  • Решат задачу расстановки пентамимо с использованием алгоритма Dancing Links
Course content
Expand all 14 lectures 04:07:25
+ Теория
3 lectures 32:04

В этой серии уроков мы познакомимся с гениальным "алгоритмом X" Дональда Кнута — Dancing Links.

Этот алгоритм можно применять для решения самых разных комбинаторных задач, например, разложение Пентамимо, решение Судоку, размещение ферзей и так далее. Ссылки на статью Дональда Кнута и обзорная статья на Хабре с описанием данного алгоритма — внизу описания урока.

Самостоятельное задание:

  1. Внимательно прослушать и просмотреть видео.

  2. Подходит ли данный алгоритм для решения задачи Судоку или Парад Ферзей.

  3. Приложить интересную картинку на тему урока.

Preview 08:35

На этом уроке мы пошагово рассмотрим статью на Хабре (см. ссылки ниже).

Самостоятельное задание:

  1. Внимательно прослушать и просмотреть видео.

  2. Напишите своё мнение по поводу данного урока.

  3. Самостоятельно рассмотреть варианты поиска решения.

  4. Приложить скриншот проработанного алгоритма.

Preview 12:43

На этом уроке мы пошагово рассмотрим статью автора данного алгоритма — Дональда Кнута, и рассмотрим пошаговое удаление и возвращение элемента.

Самостоятельное задание:

  1. Внимательно прослушать и просмотреть видео.

  2. Нарисовать циклический список из 4 элементов ABCD.

  3. Проработать весь алгоритм самостоятельно.

  4. Приложить скриншот проработанного алгоритма.

  5. * Продемонстрировать удаление/восстановление всех элементов.

Двусвязный список с удалением
10:46
+ Практика
5 lectures 01:54:55

На этом уроке мы наконец приступим к реализации двусвязного списка на языке C#.

Самостоятельное задание:

  1. Внимательно прослушать и просмотреть видео.

  2. Создать новый проект AlgorithmX.

  3. Создать новый класс Cell().

  4. Добавить необходимые переменные и конструктор в классе Cell().

  5. Избавиться от статика в классе Program().

  6. Реализовать функцию test() в классе Program().

  7. Реализовать функцию InsertLeft() в классе Cell().

  8. Доработать конструктор в классе Cell().

  9. Доработать функцию test() в классе Program(), использовав InsertLeft().

  10. Приложить скриншот результата.

Расширение хоровода
24:08

На этом уроке мы реализуем перемещение вверх/вниз для реализации четырёх-связного списка, а также создадим класс Header(), для того чтобы знать, в каком столбце мы находимся.

Самостоятельное задание:

  1. Внимательно прослушать и просмотреть видео.

  2. Добавить новые переменные в классе Cell().

  3. Доработать в конструктор класса Cell() начальные значение новых переменных.

  4. Реализовать функцию InsertUp() в классе Cell().

  5. Создать класс Header() с необходимыми переменными.

  6. Заменить переменную name на header в классе Cell().

  7. Добавить конструктор в классе Header().

  8. Доработать функцию test() в классе Program(), использовав InsertUp() и Header().

  9. Приложить скриншот результата.

Заголовки столбцов
12:17

На этом уроке, используя созданный ранее четырёх-связный список, мы добавим необходимые нам элементы для дальнейшем работы с ними.

Самостоятельное задание:

  1. Внимательно прослушать и просмотреть видео.

  2. Создать класс Dance() с необходимыми переменными.

  3. Добавить конструктор в классе Dance().

  4. Модифицировать тип переменной name в классе Header().

  5. Реализовать функцию AddRow() в классе Dance().

  6. Реализовать функцию start() в классе Program(), использовав класс Dance().

  7. Приложить скриншот результата.

  8. * Добавить все 12 строчек по образцу.

Единичная матрица
25:01

На этом уроке мы реализуем заготовку функции Dance() в классе Dance().

Самостоятельное задание:

  1. Внимательно прослушать и просмотреть видео.

  2. Добавить все 12 строчек в матрицу.

  3. Реализовать функцию Dance() в классе Dance().

  4. Создать заглушки для функций Cover/Uncover().

  5. Добавить вывод текущего шага в функции Dance().

  6. Приложить скриншот результата.

Как ссылки пошли впляс
21:15

На этом уроке мы доработает функции AddRow() и Dance() в классе Dance(), а также реализуем функции Cover/Uncover().

Самостоятельное задание:

  1. Внимательно прослушать и просмотреть видео.

  2. Добавить номер строки в классе Cell().

  3. Доработать функцию AddRow() в классе Dance().

  4. Доработать функцию Dance() в классе Dance(), использовав стек для хранения целых чисел.

  5. Реализовать функции Cover/Uncover() в классе Dance().

  6. Перенумеровать ячейки от 0 до 11, чтобы избавиться от пустых столбцов.

  7. Приложить скриншот результата.

Открытие/закрытие столбцов
32:14
+ Пентамимо
6 lectures 01:40:26

На этом уроке мы приступаем к решению олимпиадной задачи "Пентамино", заполнив массив всеми вариантами расположения фигур.

Ссылка на файл с кодом функции инициализации фигур на С# — внизу.

Самостоятельное задание:

  1. Внимательно прослушать и просмотреть видео.

  2. Создать структуру Figure() и Variant().

  3. Создать класс Pentaminos().

  4. Заполнить массив всеми 63 вариантами расположения фигур в классе Pentaminos().

  5. Создать функцию startPent() в классе Program().

  6. Проверить заполнение массива всеми вариантами фигур.

  7. Приложить скриншот результата.

  8. ** Доработать функцию startPent() для решения поставленной задачи.

  9. *** Реализовать генератор всевозможных расположений фигур.

Фигуры из пентамимо
18:16

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

Ссылка на файл с кодом функции инициализации фигур на С# — внизу. 

Самостоятельное задание:

  1. Внимательно прослушать и просмотреть видео.

  2. Реализовать функцию Show() в классе Figure().

  3. Добавить в классе Figure() строку символов фигур.

  4. Доработать функцию startPentamino() в классе Program() для отображения фигур.

  5. Реализовать перегрузку функции Show() в классе Figure() для более короткой записи.

  6. Использовать короткую запись в функции startPentamino() класса Program().

  7. Приложить скриншот результата.

  8. * Вывести все 12 фигур в консоли.

Фигуры в консоли
14:59

На этом уроке мы завершим реализацию функции поиска решения Пентамино.

Ссылка на файл с кодом функции инициализации фигур на С# — внизу. 

Самостоятельное задание:

  1. Внимательно прослушать и просмотреть видео.

  2. Реализовать алгоритм перебора всех вариантов расположения фигур Пентамино.

  3. Дождаться завершения работы алгоритма и написать время ожидания.

  4. Приложить скриншот результата.

Матрица Пентагона
15:55

На этом уроке мы воспользуемся функцией Show() в классе Figure() для визуализации генерации всех вариантов расположения фигур Пентамино.

Ссылка на файл с кодом функции инициализации фигур на С# — внизу. 

Самостоятельное задание:

  1. Внимательно прослушать и просмотреть видео.

  2. Исправить ошибку прошлого урока связанную с nr++.

  3. Использовать отображение генерации расположения вариантов фигур через функцию Show().

  4. Добавить задержку после вывода каждого варианта расположения фигур по нажатию клавиш.

  5. Реализовать функцию Hide() в классе Figure().

  6. Использовать функцию Hide() вместо Console.Clear().

  7. Приложить скриншот результата.

Пентагон в деталях
09:40

На этом уроке мы визуализируем поиск решения Пентамино с использованием 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. * Дождаться окончания поиска решений.

Пентагон ищет решение
22:01

В завершение знакомства с гениальным "алгоритмом X" Дональда Кнута — Dancing Links,
мы оптимизируем наш алгоритм поиска решения Пентамино.

Ссылка на файл с кодом функции инициализации фигур на С# — внизу.

Самостоятельное задание:

  1. Внимательно прослушать и просмотреть видео.

  2. Оптимизировать функцию Dance() в классе Dance().

  3. Реализовать счётчик количество найденных вариантов.

  4. Реализовать счётчик времени потраченного на поиск решений.

  5. Поэкспериментировать с разными размерами поля.

  6. Убрать геттеры/сеттеры в классе Cell() для многократного ускорения работы алгоритма.

  7. Приложить скриншот результата.

  8. *** Реализовать решение Судоку, используя данный алгоритм.

  9. *** Реализовать решение Парад Ферзей, используя данный алгоритм.

Десятикратная оптимизация
19:35
Requirements
  • Логическое мышление
  • Основы языка программирования C#
Description

В этой серии уроков мы познакомимся с гениальным алгоритмом X Дональда Кнута - Dancing Links.

Этот алгоритм можно применять для решения самых разных комбинаторных задач, например, заполнение области Пентамимо-фигурами, решение Судоку, размещение ферзей на шахматной доске и так далее. 

В первой части курса "Теория" мы разберём принцип работы алгоритма, выполним его построчно "ручками" на конкретном примере, чтобы лучше понять, как он устроен и как работает.

Во второй части курса "Практика" мы реализуем на C# двух- и четырёх-связных списков и дальнейшей реализации "Алгоритма Икс" Дональда Кнута. и напишем весь алгоритм.

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

Если вам нравятся алгоритмы - обязательно пройдите этот курс, не пожалеете.

Who this course is for:
  • Для любителей алгоритмов
  • Для инженеров и программистов
  • Для студентов с лабораторкой по Dancing Links