Главная | Эксперименты | Утилиты | Компоненты | Что почитать | Контакты |
|
Подсчитать количество различных замкнутых путей, проходящих через каждую клетку квадратной решетки nxn по крайней мере один раз так, что любые границы между соседними квадратами не пересекаются более одного раза и путь не содержит самопересечений.
Задача может решаться и для прямоугольных сеток nxk. Возможны также два варианта подсчета количества путей: пути, получаемые отражениями и/или вращением могут считаться различными (not reduced for symmetry) или не считаться таковыми (reduced for symmetry). Полученные значения для первого варианта (пути, получаемые поворотом/вращением считаются различными) приведены по ссылке слева. Для расчета использовано динамическое программирование по профилю[2]. Задача значительно усложняется, если пути, получаемые отражениями/вращениями считать одинаковыми. Для подсчета количества уникальных путей использована следующая схема:
Такая схема позволила рассчитать количество уникальных путей для четных n до 10 включительно. Полученные значения приведены в таблице слева.
|