# | Название видеоурока | Видео / Тесты | Решило | Рейтинг | Доступ |
---|---|---|---|---|---|
1 |
![]() |
|
|||
В этой серии уроков мы познакомимся с гениальным алгоритмом X Дональда Кнута - Dancing Links. Этот алгоритм можно применять для решения самых разных комбинаторных задач, например, разложение Пентамимо, решение Судоку, размещение ферзей и так далее. Статья Дональда Кнута: https://arxiv.org/pdf/cs/0011047v1.pdf Обзорная статья на Хабре: https://habrahabr.ru/post/194410/ Отчёт отправил: 11589. Yefim Выполнено за 23 мин. [Показать отчёт] Научился: Узнал о существовании алгоритма Dancing Links Сложности: не было сложностей Комментарии: Начало интригующее |
|||||
2 | Работа алгоритма |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы пошагово рассмотрим статью на Хабре. Отчёт отправил: 11589. Yefim Выполнено за 2 час. 22 мин. [Показать отчёт] Научился: Разобрался на словах с алгоритмом Х Дональда Кнута. Сложности: Проработать в пэйнте алгоритм Комментарии: Алгоритм действительно гениальный |
|||||
3 | Двусвязный список с удалением |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы пошагово рассмотрим статью автора данного алгоритма и рассмотрим пошаговое удаление и возвращение элемента. Отчёт отправил: 11589. Yefim Выполнено за 2 час. 34 мин. [Показать отчёт] Научился: Добвылять и Удалять схематично елементы списка Сложности: Рисовать Комментарии: Все отлично |
|||||
4 | Расширение хоровода |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы наконец приступим к реализации двусвязного списка на языке C#. Отчёт отправил: 11589. Yefim Выполнено за 55 мин. [Показать отчёт] Научился: Cоздавать и добавлять и удалять ячейки двусвязного списка Сложности: --- Комментарии: Сначала мне подумалось, что удаление ячейки b - это скорее самоубийство, поскольку она удаляется своими же силами. Но затем понял, что в памяти она сохраняется и я назвал это выходом из списка. |
|||||
5 | Заголовки столбцов |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы реализуем перемещение вверх/вниз для реализации четырёх-связного списка, так же создадим класс Header(), чтобы знать в каком столбце мы находимся. Отчёт отправил: 11589. Yefim Выполнено за 55 мин. [Показать отчёт] Научился: Делать четырех-связный список. Сложности: Понять роль класса Header Комментарии: Непонятно как использовать поле name, чтобы именовать ячейки. |
|||||
6 | Единичная матрица |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке, используя созданный ранее четырёх-связный список, мы добавим необходимые нам элементы для дальнейшем работы с ними. Отчёт отправил: 11589. Yefim Выполнено за 45 мин. [Показать отчёт] Научился: Сoздавать клaсс Dance() с нeобxодимыми пepемeнными и методами Сложности: --- Комментарии: При заполнении таблицы в одной строке ошибся: нарушен был порядок номеров столбцов. Программа указала на ошибку. Приятно. |
|||||
7 | Как ссылки пошли впляс |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы реализуем заготовку функции Dance() в классе Dance(). Отчёт отправил: 11589. Yefim Выполнено за 44 мин. [Показать отчёт] Научился: Рeализoвывать функцию Dance() в клаcсe Dance(). Сложности: --- Комментарии: Не терпится увидеть результат |
|||||
8 | Открытие/закрытие столбцов |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы доработает функции AddRow() и Dance() в классе Dance(). Так же реализуем функции Cover/Uncover(). Отчёт отправил: 11589. Yefim Выполнено за 1 час. 44 мин. [Показать отчёт] Научился: Реализовывать алгоритм Dancing-Links для частного случая Сложности: --- Комментарии: Инициатива наказуема |
|||||
9 | Фигуры из пентамимо |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы приступаем к решению олимпиадной задачи: Пентамино, заполнив массив всеми вариантами расположения фигур. Отчёт отправил: 11589. Yefim Выполнено за 2 час. 11 мин. [Показать отчёт] Научился: Создавать класс Pentaminos() Сложности: Непонятно из каких соображений количество строк в матрице будет 12 +60 Комментарии: Спасибо Алексу Оранжу за громадную работу. Из скрина видно, что все фигуры отображаются правильно. |
|||||
10 | Фигуры в консоли |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы решили реализовать возможность отображения фигур в консоли, чтобы в дальнейшем видеть что происходит в процессе работы алгоритма. Отчёт отправил: 11589. Yefim Выполнено за 44 мин. [Показать отчёт] Научился: Перегружать функцию Show(...) Сложности: --- Комментарии: Фактически, я выполнил это задание в предыдущем уроке. Но должен признать, что код, приведенный в уроке, мне больше нравится. Мой вопрос в скрине. |
|||||
11 | Матрица Пентагона |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы завершим реализацию функции поиска решения Пентамино. Отчёт отправил: 11589. Yefim Выполнено за 1 час. 09 мин. [Показать отчёт] Научился: Строить матрицу Пентагона Сложности: Строить матрицу Пентагона Комментарии: Я не дождался завершeния рaботы aлгoритмa . Время ожидания составило более 12 часов. |
|||||
12 | Пентагон в деталях |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы воспользуемся функцией Show() в классе Figure() для визуализации генерации всех вариантов расположения фигур Пентамино. Отчёт отправил: 11589. Yefim Выполнено за 22 мин. [Показать отчёт] Научился: Скрывать фигуры Сложности: --- Комментарии: Как видно из скрина я сделал не просто задержку, а путем ввода номера фигуры вывожу ее на экран |
|||||
13 | Пентагон ищет решение |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы визуализируем поиск решения Пентамино с использованием yield. Отчёт отправил: 11589. Yefim Выполнено за 47 мин. [Показать отчёт] Научился: Динамически отображать фигуры Сложности: До сих пор не чувствую механизм IEnumerable Комментарии: Программа проработала всю ночь, но решения не выдала. |
|||||
14 | Десятикратная оптимизация |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы оптимизируем наш алгоритм поиска решения Пентамино. Отчёт отправил: 11589. Yefim Выполнено за 49 мин. [Показать отчёт] Научился: Оптимизировать алгоритм Дональда Кнута - Dancing Links. Сложности: --- Комментарии: Не думал, что геторы и сеторы так влияют на скорость выполнения программы. Удалось визуально отобразить решения! Курс СУПЕР!!! |
|||||
Итого: 14 видеоуроков |
4 час. 18 мин. |
17 чел. | |||
Финалисты: Иван Воронин, Андрей, AZANIR, Алексей Малышев, Сергей Соколов, Алексей В., Максим Лапшинов, Spellion, Tekashnik, Yefim, Новопашин Владимир, Bazel, Николай Денисов, Иван, Дмитрий, Max, MaxB . |