Алгоритм заполнения прямоугольника маленькими квадратами?

Question

Учитывая прямоугольник с шириной и высотой, заполните его n квадратами (n также является целым числом), чтобы квадраты покрывали максимально возможную площадь прямоугольника. Размер одного квадрата должен быть возвращен.

Идеи

Answer 1

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

Для превосходной обработки в случае, когда более крупной формой, в которую упакованы n квадраты, является квадрат, см. Статью Эриха Фридмана Квадраты упаковочной единицы в квадратах: Обзор и новые результаты

Например, Гёдель был первым, кто опубликовал эту тему. Он обнаружил, что квадраты a2 + a + 3 + (a-1) √2 можно упаковать в квадрат стороны a + 1 + 1 / √2, разместив диагональную полосу квадратов под углом 45 градусов. Например,

И просто для удовольствия, я настоятельно рекомендую вам проверить Центр упаковки Эриха .

Answer 2

Я знаю, что этот вопрос был давным-давно, но вот что я:

у вас есть n квадрат, у вас есть прямоугольник, вы хотите узнать размер квадрата, чтобы заполнить прямоугольник

например:

rectangle of 1280*720 filled with 100 squares. 
The surface is 1280*720=921600
1 square should have the surface of 921600/100 = 9216
so the square size is sqrt(9216)=96

В конце это будет просто функция, которая возвращает результат этого:

sqrt((width*height)/n)

Answer 3

Предполагая, что все квадраты выровнены и имеют одинаковый размер, вы можете найти это с помощью двоичного поиска по длине стороны квадрата:

import math

def best_square(w, h, n):
    hi, lo = float(max(w, h)), 0.0
    while abs(hi - lo) > 0.000001:
        mid = (lo+hi)/2.0
        midval = math.floor(w / mid) * math.floor(h / mid)
        if midval >= n:
            lo = mid
        elif midval < n: 
            hi = mid
    return min(w/math.floor(w/lo), h/math.floor(h/lo))

Answer 4

Вот мое решение. Идея состоит в том, чтобы пойти по рекурсивному циклу. Предположим, вы начинаете с square_counter = 0

Пока длина и дыхание: // найдите максимально возможный квадрат

Count1 = длина/ дыхание // взять слово

Square_counts + = count1

Новая длина баланса = длина - count1 * дыхание

Теперь квадрат с максимально возможным размером по отношению к дыханию

Count2 = дыхание / длина

Square_count + = count2

Дыхание = дыхание - считать * длина