Всем привет! Сегодня мы рассмотрим такую задачку: нужно найти и посчитать все прямоугольнике в клетчатом квадрате 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 — снизу).
- Если K=L, то F=(M mod K) * (N mod K).
- Если 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).
Оценка 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. Наша функция должна вернуть количество прямоугольников в фигуре. В общем, типа перебираем несколько вариантов.
Для оптимизации можно для прямоугольника, описываемой парой чисел, запоминать максимальное количество, которое у нас получилось, чтобы по несколько раз не вычислять сколько фигур влезает в такой прямоугольник.
Загрузка...
