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

Question

Я практиковал некоторые вопросы конкурса по программированию (для забавы и практики для предстоящих конкурсов) и застрял на этом: http://dwite.ca/questions/power_tiles.html

Я не совсем уверен, с чего мне начать = /. Как мне подойти к этому вопросу, чтобы решить его?

Спасибо за помощь

Answer 1

Вот ветка, посвященная конкретно этой теме - там вы можете увидеть, что думали другие головоломки: http://compsci.ca/v3/viewtopic.php?t=26423

Answer 2

Я бы подошел к нему по рекурсии.

Напишите функцию, которая получает два целочисленных значения в качестве входных данных.Одно значение будет длиной, а другое - шириной.Самая большая площадь, в которую вы можете поместиться, будет основана на самой короткой стороне.Его размеры будут рассчитываться следующим образом:

2^RoundDown(Log(ShortSide,Base:2))

Это даст вам ваш первый квадрат и разделит прямоугольник либо на 3, либо на 1 другой прямоугольник, или ничего, если он квадрат с 2 ^ n длинами сторон.

Размеры остальных прямоугольников легко получить простым вычитанием.После того, как размеры вычислены, вызовите функцию снова (внутри себя) для каждого нового прямоугольника с его размерами.

Функция должна быть прекращена, когда разности, рассчитанные для обеих сторон, равны нулю, т.е.n длины сторон.

Немного похоже на это:

Global int Counter
DivideRectangle(int Width, int Length)
    int BigSquare = 2^RoundDown(Log(Width,Base:2))
    if NOT(Width - BigSqaure = 0 AND Height- BigSqaure = 0)
        DivideRectangle(width - BigSquare, Height - BigSquare)
        DivideRectangle(width - BigSquare, BigSquare)
        DivideRectangle(BigSquare, Height - BigSquare)

    Counter += 1

Это примерно так;Счетчик, возвращаемый после всей операции, представляет собой число квадратов для заполнения прямоугольника.Очевидно, что код несовершенен и требует доработки, но это всего лишь набросок того, что должно произойти.

Надеюсь, это поможет

Answer 3

Мне кажется, что проблема с динамическим программированием

• Пусть F (ш, ч) будет минимальным числом квадратов, которые составляют плитки w по h прямоугольник.

• Найдите рекурсивную формулировку для F:

  • , если w = 0 или h = 0, тогда F (w, h) =0

  • в противном случае, F (w, h) =

    For each allowable size a=i^2 <= min(w,h), try to place the a by a square (A)
     in the top left corner.
    One of the following possibilities will describe the
     optimal solution:
     +---+--+    +---+--+
     | A | C|    | A |  |
     +---+--+    +---+  |
     |  B   |    |B  |C |
     +------+    +---+--+
     So, choose the best of
       (1 + F(h-a, w) + F(h-a, w-a)) or
       (1 + F(h-a, a) + F(w-a, h))
    

Выполнение анализа big-O на салфетке, этопохоже на O(side^2 * sqrt(side)) -иш алгоритм.Если это слишком много, вы можете:

• Попробуйте использовать симметрии в задаче (например, F (w, h) = F (h, w))
• Проверьтеанализ снова, чтобы убедиться, что он слишком медленный, и вам нужен другой алгоритм (возможно, вам не нужно вычислять для всех (w, h) пар?)
• Найдите некоторое свойство задачи, которое позволяет упроститьМенее исчерпывающая стратегия.(Например, выбор наибольшего квадрата, когда это возможно, простая жадная стратегия ... но работает ли она во всех случаях?)

Answer 4

Я бы начал с выяснения ответа вручную, чтобы сказать полдюжины или около того ... затем смоделировал, как вы справились с проблемой в программе ... Затем, после того, как у вас есть рабочий "грубая сила", попытайтесь решить проблема более элегантно.

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

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

Я уверен, что есть хорошее аккуратное рекурсивное решение ... основанное на степенях двух ... тогда вы можете распутать это в нерекурсивное решение ...

Answer 5

Какие «1, 2, 4, 8 и т. Д.» Помнят вас?

Посмотрите на рисунок, какой порядок (по размеру) начинки вы выберете?