Математика · объяснение и практика
Как найти все прямоугольные раскладки заданного числа клеток
Находим все целочисленные прямоугольные раскладки фиксированного количества клеток, учитываем поворот и проверяем особую квадратную пару.

В теме Делимость, простые числа, НОД и НОК · Учебная карта
Главная мысль
Двадцать четыре одинаковые клетки можно разложить в прямоугольники 1×24,2×12,3×8 и 4×6, если поворот не считается новой раскладкой. Каждая пара сторон является парой положительных делителей с произведением 24. Перебор можно остановить у квадратного корня, чтобы не повторять уже найденные пары.
Как геометрическая задача превращается в делимость
Пусть клетки не перекрываются и образуют полностью заполненный прямоугольник без дырок. Число клеток в строке a и число строк b являются положительными целыми. Общее количество равно ab. Для заданных 24 клеток выбираем делитель a и вычисляем b = 24/a. Если частное нецелое, прямоугольной клеточной раскладки с такими сторонами не получится.
Стороны 4 и 6 подходят, а сторона 5 нет:24 не делится на пять. Это не запрет геометрического прямоугольника площадью 24 с дробными сторонами, а ограничение именно на раскладку целых единичных клеток. Условие модели определяет допустимые стороны. При разных размерах плиток или обязательных промежутках нужна новая геометрическая постановка.
Как не считать повёрнутые раскладки дважды
Пары 2×12 и 12×2 имеют одинаковые размеры после поворота. Если направление не выделено, их удобно считать одной парой. Для этого выбирают меньшую сторону a, так что a ≤ b. Из ab = N следует a² ≤ N. Значит, достаточно проверить целые делители до √N включительно и брать к каждому соответствующее частное.
Если ориентация важна, например число рядов закреплено разметкой, повёрнутые варианты могут считаться разными. Тогда правило подсчёта нужно изменить явно. Не стоит удалять повтор по привычке, если условия различают длину и ширину направленным назначением. В квадратной паре стороны равны, поэтому даже при учёте порядка перестановка не создаёт нового варианта.
Пример
Найдите все раскладки 36 клеток в прямоугольник без различения поворота.
Проверяем делители до 6 включительно:1,2,3,4,6. Получаем 1×36,2×18,3×12,4×9 и 6×6. Всего пять. Квадратная пара 6×6 учитывается один раз, а пары с меньшей стороной больше 6 уже повторили бы прежние.
Как использовать список для дальнейшего выбора
Разные раскладки одинаковой площади имеют разные периметры. Для 24 клеток пары 1×24,2×12,3×8 и 4×6 дают соответственно 50,28,22 и 20 единиц периметра. Среди перечисленных вариантов минимален периметр 4×6. Площадь одинакова, но число пограничных единичных отрезков различается. Нельзя получить периметр только из площади без дополнительных условий о форме.
Проверяйте каждую пару умножением и отдельно контролируйте полноту списка. Число положительных делителей помогает: у неквадратного N делители объединяются в различные пары, у полного квадрата один средний делитель образует пару сам с собой. Это связывает количество раскладок с теорией делителей и объясняет, почему простое деление числа делителей пополам требует поправки для квадратного случая.
От чтения к действию
А теперь — вы
Частые вопросы
Почему можно остановиться около квадратного корня?
Если меньшая сторона стала больше √N, произведение двух не меньших сторон превысит N. Все оставшиеся делители уже повторяют пары в обратном порядке.
У всех раскладок одной площади одинаковый периметр?
Нет. Площадь задаёт произведение сторон, а периметр зависит от их суммы. Разные пары делителей дают разные суммы.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Как степени простых множителей задают число делителей
Считаем положительные делители по разложению числа: выбор степеней, роль нулевого показателя и отличие количества делителей от их суммы.
Открыть темуКак посчитать всю поверхность прямоугольного параллелепипеда
Как находить полную поверхность прямоугольного параллелепипеда по трём размерам, считать парные грани и отличать закрытую коробку от открытой.
Открыть тему