Операция выполнена!
Закрыть
Хабы: Программирование, Математика, Алгоритмы, GPGPU

В продолжение части 1 привожу анализ заполнений квадрата со стороной 45 квадратиками размера от 1 до 9 (1x1 - 1 шт., 2x2 - 2 шт., 3x3 - 3 шт., ..., 9x9 - 9 шт.).

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

Если выстроить квадратики размера 9 вдоль двух соседних «стенок», то мы сведём задачу поиска заполнения к задаче для n=8. Таким образом получается, что около 4% заполнений для n=9 получаются напрямую из заполнений для n=8 (у нас есть 4 способа выбрать 2 соседние «стенки»).

Читать далее
Читайте также
НОВОСТИ

ПИШИТЕ

Техническая поддержка проекта ВсеТут

info@vsetut.pro