# | Название видеоурока | Видео / Тесты | Решило | Рейтинг | Доступ |
---|---|---|---|---|---|
1 |
![]() |
|
|||
В этой серии уроков мы познакомимся с гениальным алгоритмом X Дональда Кнута - Dancing Links. Этот алгоритм можно применять для решения самых разных комбинаторных задач, например, разложение Пентамимо, решение Судоку, размещение ферзей и так далее. Статья Дональда Кнута: https://arxiv.org/pdf/cs/0011047v1.pdf Обзорная статья на Хабре: https://habrahabr.ru/post/194410/ Отчёт отправил: 4814. Дмитрий Выполнено за 44 дня 1 час. 39 мин. [Показать отчёт] Научился: Первое знакомство с алгоритмом X Дональда Кнута. Сложности: Пока все понятно. |
|||||
2 | Работа алгоритма |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы пошагово рассмотрим статью на Хабре. Отчёт отправил: 4814. Дмитрий Выполнено за 44 дня 12 час. 51 мин. [Показать отчёт] Научился: Очень интересно. Выбираем элементы с наименьшим количеством совпадений и проходим по цепочке. Сложности: С точки зрения математики - элементарно, а вот как это запрограммировать - пока непонятно. |
|||||
3 | Двусвязный список с удалением |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы пошагово рассмотрим статью автора данного алгоритма и рассмотрим пошаговое удаление и возвращение элемента. Отчёт отправил: 4814. Дмитрий Выполнено за 37 мин. [Показать отчёт] Научился: Знакомство с двусвязным списком. Сложности: Интересно |
|||||
4 | Расширение хоровода |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы наконец приступим к реализации двусвязного списка на языке C#. Отчёт отправил: 4814. Дмитрий Выполнено за 1 день 5 час. 34 мин. [Показать отчёт] Научился: Создали проект, реализовали удаление и вставку элементов. Сложности: Все ново и интересно. |
|||||
5 | Заголовки столбцов |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы реализуем перемещение вверх/вниз для реализации четырёх-связного списка, так же создадим класс Header(), чтобы знать в каком столбце мы находимся. Отчёт отправил: 4814. Дмитрий Выполнено за 7 час. 15 мин. [Показать отчёт] Научился: Реализовали перемещение вверх-вниз по списку, а также добавили класс Header. Сложности: Интересно, но нелегко. |
|||||
6 | Единичная матрица |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке, используя созданный ранее четырёх-связный список, мы добавим необходимые нам элементы для дальнейшем работы с ними. Отчёт отправил: 4814. Дмитрий Выполнено за 2 час. 17 мин. [Показать отчёт] Научился: Создали класс Dance и реализовали в нем алгоритм добавления строк. Сложности: Ново. |
|||||
7 | Как ссылки пошли впляс |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы реализуем заготовку функции Dance() в классе Dance(). Отчёт отправил: 4814. Дмитрий Выполнено за 5 час. 37 мин. [Показать отчёт] Научился: Подготовили функцию dance с покрытием и раскрытием столбцов. Сложности: Интересно. |
|||||
8 | Открытие/закрытие столбцов |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы доработает функции AddRow() и Dance() в классе Dance(). Так же реализуем функции Cover/Uncover(). Отчёт отправил: 4814. Дмитрий Выполнено за 1 час. 40 мин. [Показать отчёт] Научился: Реализовали функции cover/uncover, решили задачу. Сложности: Интересно и сложно. |
|||||
9 | Фигуры из пентамимо |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы приступаем к решению олимпиадной задачи: Пентамино, заполнив массив всеми вариантами расположения фигур. Отчёт отправил: 4814. Дмитрий Выполнено за 1 день 20 час. 37 мин. [Показать отчёт] Научился: Создали структуры Figure и Variant, заполнили все возможные положения фигур. Сложности: Интересно. |
|||||
10 | Фигуры в консоли |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы решили реализовать возможность отображения фигур в консоли, чтобы в дальнейшем видеть что происходит в процессе работы алгоритма. Отчёт отправил: 4814. Дмитрий Выполнено за 1 час. 1 мин. [Показать отчёт] Научился: Реализовали функцию отображения всех фигур в консоли. Сложности: Все отлично. |
|||||
11 | Матрица Пентагона |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы завершим реализацию функции поиска решения Пентамино. Отчёт отправил: 4814. Дмитрий Выполнено за 1 день 11 час. 38 мин. [Показать отчёт] Научился: Реализовали алгоритм перебора всех вариантов расположения фигур Пентамино. Сложности: Все нормально. |
|||||
12 | Пентагон в деталях |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы воспользуемся функцией Show() в классе Figure() для визуализации генерации всех вариантов расположения фигур Пентамино. Отчёт отправил: 4814. Дмитрий Выполнено за 41 мин. [Показать отчёт] Научился: Реализовали визуализацию вариантов фигур Сложности: Все отлично |
|||||
13 | Пентагон ищет решение |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы визуализируем поиск решения Пентамино с использованием yield. Отчёт отправил: 4814. Дмитрий Выполнено за 16 час. 31 мин. [Показать отчёт] Научился: Реализовали визуализацию поиска решения, добавили итератор, создали структуру FigureRow для хранения расположения фигуры на поле. Сложности: Очень интересно. |
|||||
14 | Десятикратная оптимизация |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы оптимизируем наш алгоритм поиска решения Пентамино. Отчёт отправил: 4814. Дмитрий Выполнено за 16 час. 47 мин. [Показать отчёт] Научился: Реализовали счет количества найденных вариантов и потраченного времени при разных размерах поля. Оптимизировали алгоритм, убрав сеттеры и геттеры. Сложности: Много новой информации. |
|||||
Итого: 14 видеоуроков |
4 час. 18 мин. |
17 чел. | |||
Финалисты: Иван Воронин, Андрей, AZANIR, Алексей Малышев, Сергей Соколов, Алексей В., Максим Лапшинов, Spellion, Tekashnik, Yefim, Новопашин Владимир, Bazel, Николай Денисов, Иван, Дмитрий, Max, MaxB . |