Сколько прямоугольников можно найти

Всем привет! Сегодня мы рассмотрим такую задачку: нужно найти и посчитать все прямоугольнике в клетчатом квадрате 8 на 8, а потом и n на n. Надеюсь, будет весело!

А заодно затронем тему с суммой кубов первых n натуральных чисел, но это так, бонусом:3

Ответ оставил Гуру

18_03_03_Задание № 6:
Сколько прямоугольников можно найти на картинке?
РЕШЕНИЕ: на фото
ОТВЕТ: 11

Если тебя не устраивает ответ или его нет, то попробуй воспользоваться поиском на сайте и найти похожие ответы по предмету Математика.

Дана фигура (A) размером M на N. Дана вторая фигура (B), поменьше, размером K на L.

Нужно определить, сколько максимально фигур B поместятся в фигуре A. Они должны располагаться одна рядом с другой, часть фигур может располагаться вертикально, другая часть горизонтально, что бы занять максимальное возможное пространство в основной фигуре.

Кто то может подсказать что то по этому вопросу?

На данный момент у меня мысли только если:

считать количество прямоугольников, расположенных горизонтально, которые поместятся горизонтально в фигуре, то есть ставим прямоугольник, рядом второй, заполняем линию, дальше снизу ставим еще одну линию, и так до самого низа.

Далее справа, возможно, останется пространство. Проверяем, помещается ли туда прямоугольник вертикально, если да, то заполняем стобец вертикальными прямоугольниками.

В итоге получаем число — сколько поместилось прямоугольников.

Далее повторяем тоже самое, только располагаем изначально прямоугольники вертикально, и если снизу остается пространство, проверяем, помещаются ли туда прямоугольники горизонтально, если да, то заполняем линию. И опять считаем сколько поместилось.

Из двух подсчетом выбираем тот, который дал наибольшый результат.

Вот пример подсчета, который я описал, реализованный на на JavaScript:

5 ответов 5

Существуют очевидные оценки для количества R прямоугольников KxL (K>=L), которое можно разместить внутри прямоугольника MxN (сторона M — снизу).

  1. Если K=L, то F=(M mod K) * (N mod K).
  2. Если K>L, то F >= max(F1,F2), где
    F1 = (M mod K) * (N mod L) + ((M%K) mod L) * (N mod K),
    F2 = (N mod K) * (M mod L) + ((N%K) mod L) * (M mod K).
Читайте также  Сказки на ночь bedtime stories 2008

Оценка F1 соответствует варианту, при котором левая часть большого прямоугольника по максимуму закладывается длинной стороной K вдоль стороны M, а оставшаяся правая часть — с разворотом.
Оценка F2 получается, если стороны M и N поменять ролями.

При этом максимальная оценка F определяется площадями прямоугольников, т.е.
F

Если актуально то в данном случае подойдет алгоритм:

Считаем площадь основной фигуры (A)S = M * N

Считаем площадь вкладываемой фигуры (B)s = K * L

В итоге деления площадей фигуры (A) на (B) и отброса остатка, получаем количество вложенных прямоугольников

если нужно могу реализовать на python’e функцию

Считаешь площадь основной фигуры,считаешь площадь вложенной фигуры и берешь модуль вложенной фигуры из основной(операция %).

Нужно найти лучший вариант или идеальный? С идеальным — проблема. Например, берем квадрат 5*5 и фигуры 2*3. Мы можем разместить 4 фигуры на 24 клетки. Это идеальное решение. А можно ли его получить автоматическим методом — я не знаю. Теперь про определение лучшего результата. Я предлагаю такой алгоритм:

Берем большую фигуру. Делим вертикальной линией так, чтобы в левую часть укладывались маленькие фигуры горизонтально, а в правую часть — вертикально. Вариантов проведения таких линий будет несколько, так что надо будет просчитать каждый вариант.

То есть для фигуры 23*17 и мелкой 4*3 получаем получаем варианты 4+19 8+15 12+11 16+7 20+3

Берем вариант (8 + 15) клеток у нас получается 2 фигуры 8*17 и 15*17 Далее разворачиваем каждый из прямоугольников и вызываем саму функцию рекурсивно для каждого из прямоугольников, то есть 8*17 и 15*17. Наша функция должна вернуть количество прямоугольников в фигуре. В общем, типа перебираем несколько вариантов.

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

Ссылка на основную публикацию
Adblock
detector