# | Название видеоурока | Видео / Тесты | Решило | Рейтинг | Доступ |
---|---|---|---|---|---|
1 |
![]() |
|
|||
В этой серии уроков мы познакомимся с гениальным алгоритмом X Дональда Кнута - Dancing Links. Этот алгоритм можно применять для решения самых разных комбинаторных задач, например, разложение Пентамимо, решение Судоку, размещение ферзей и так далее. Статья Дональда Кнута: https://arxiv.org/pdf/cs/0011047v1.pdf Обзорная статья на Хабре: https://habrahabr.ru/post/194410/ Отчёт отправил: 10623. Андрей Выполнено за 20 мин. [Показать отчёт] Научился: Узнал о гeниальном алгоритме X Дональда Кнута - Dancing Links Сложности: Построение матрицы Комментарии: Хотелось бы написать программу для составления вот таких фигур (как в приложенном файле) |
|||||
2 | Работа алгоритма |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы пошагово рассмотрим статью на Хабре. Отчёт отправил: 10623. Андрей Выполнено за 3 час. 00 мин. [Показать отчёт] Научился: Вручную выполнять алгоритм Сложности: -- Комментарии: Вспомнил студенческие времена и особо вреднющих преподавателей :) Отчет переделываю уже 3-й раз. |
|||||
3 | Двусвязный список с удалением |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы пошагово рассмотрим статью автора данного алгоритма и рассмотрим пошаговое удаление и возвращение элемента. Отчёт отправил: 10623. Андрей Выполнено за 2 час. 09 мин. [Показать отчёт] Научился: Вспомнил циклический двусвязный список Сложности: Сдать отчет очень придирчивому проверяющему :) Комментарии: И опять вспомнилось студенчество. И самые любимые преподаватели |
|||||
4 | Расширение хоровода |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы наконец приступим к реализации двусвязного списка на языке C#. Отчёт отправил: 10623. Андрей Выполнено за 1 час. 38 мин. [Показать отчёт] Научился: Работать со списками Сложности: Все понятно Комментарии: Нет комментариев |
|||||
5 | Заголовки столбцов |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы реализуем перемещение вверх/вниз для реализации четырёх-связного списка, так же создадим класс Header(), чтобы знать в каком столбце мы находимся. Отчёт отправил: 10623. Андрей Выполнено за 1 час. 18 мин. [Показать отчёт] Научился: Создавать списки Сложности: Пока все понятно Комментарии: Комментариев нет |
|||||
6 | Единичная матрица |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке, используя созданный ранее четырёх-связный список, мы добавим необходимые нам элементы для дальнейшем работы с ними. Отчёт отправил: 10623. Андрей Выполнено за 2 час. 05 мин. [Показать отчёт] Научился: Заполнять матрицу Сложности: Много писать Комментарии: Все нормально. В столбце 33 заполнено 7 ячеек |
|||||
7 | Как ссылки пошли впляс |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы реализуем заготовку функции Dance() в классе Dance(). Отчёт отправил: 10623. Андрей Выполнено за 2 час. 15 мин. [Показать отчёт] Научился: Разбирать псевдокод Сложности: Разобрать псевдокод Комментарии: Непонятны были сперва методы cover() и uncover() |
|||||
8 | Открытие/закрытие столбцов |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы доработает функции AddRow() и Dance() в классе Dance(). Так же реализуем функции Cover/Uncover(). Отчёт отправил: 10623. Андрей Выполнено за 2 час. 05 мин. [Показать отчёт] Научился: Реализовывать алгоритм Сложности: Найти ошибку Комментарии: cell.row = row; headers[x].InsertUp(cell); headers[x].size++; Вместо InsertUp было написано InsertLeft. И это было ошибкой :( Программа пытается найти еще несколько вариантов. Но во втором случае она не указала 5 (это фигура E). И мы бы получили полностью собранную фигуру. В третьем случае ответ неверный полностью, так как при выбранных трех фигурах никак нельзя поставить четвертую. Думаю, что неправильные ответы получаются, так как мы не откатываемся до нужного состояния при первых неправильных ответах. Нужно сделать более подробную трассировку работы программы. |
|||||
9 | Фигуры из пентамимо |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы приступаем к решению олимпиадной задачи: Пентамино, заполнив массив всеми вариантами расположения фигур. Отчёт отправил: 10623. Андрей Выполнено за 2 час. 05 мин. [Показать отчёт] Научился: Делать матрицы, описывающие положения фигур, вручную :) Сложности: Попытаться написать автоматическую генерацию массива, описывающего положения фигур. Комментарии: Все равно не понял, почему для той-же фигуры F мы берем всего два положения. А если ни одно из этих положений не будет участвовать в правильном решении? |
|||||
10 | Фигуры в консоли |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы решили реализовать возможность отображения фигур в консоли, чтобы в дальнейшем видеть что происходит в процессе работы алгоритма. Отчёт отправил: 10623. Андрей Выполнено за 45 мин. [Показать отчёт] Научился: Раскрашивать (оживлять) консоль. Сложности: Хотел автоматом высчитать ширину фигуры, чтобы не умножать в цикле h на 5 Комментарии: -- |
|||||
11 | Матрица Пентагона |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы завершим реализацию функции поиска решения Пентамино. Отчёт отправил: 10623. Андрей Выполнено за 2 час. 07 мин. [Показать отчёт] Научился: Заполнять автоматом матрицу Сложности: Дождаться окончания работы программы Комментарии: -- |
|||||
12 | Пентагон в деталях |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы воспользуемся функцией Show() в классе Figure() для визуализации генерации всех вариантов расположения фигур Пентамино. Отчёт отправил: 10623. Андрей Выполнено за 45 мин. [Показать отчёт] Научился: Визуализации алгоритма Сложности: Да, в принципе, этот урок был не сложным. Комментарии: -- |
|||||
13 | Пентагон ищет решение |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы визуализируем поиск решения Пентамино с использованием yield. Отчёт отправил: 10623. Андрей Выполнено за 1 час. 47 мин. [Показать отчёт] Научился: Выводить решение на консоль Сложности: Дождаться окончания работы алгоритма Комментарии: -- |
|||||
14 | Десятикратная оптимизация |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы оптимизируем наш алгоритм поиска решения Пентамино. Отчёт отправил: 10623. Андрей Выполнено за 1 час. 08 мин. [Показать отчёт] Научился: Оптимизировать алгоритмы. Искать в них узкие места. Сложности: Найти узкие места алгоритмов Комментарии: Как всегда, красивые решения вызывают положительные эмоции. Теперь попробуем применить полученные знания к ферзям и судоку :) |
|||||
Итого: 14 видеоуроков |
4 час. 18 мин. |
17 чел. | |||
Финалисты: Иван Воронин, Андрей, AZANIR, Алексей Малышев, Сергей Соколов, Алексей В., Максим Лапшинов, Spellion, Tekashnik, Yefim, Новопашин Владимир, Bazel, Николай Денисов, Иван, Дмитрий, Max, MaxB . |