Следующая функция вычисляет плитку максимального размера для данной информации.
Если тот факт, что он написан на Python, затрудняет понимание, дайте мне знать в комментарии, и я постараюсь сделать это на другом языке.
import math
from __future__ import division
def max_tile_size(tile_count, rect_size):
"""
Determine the maximum sized tile possible.
Keyword arguments:
tile_count -- Number of tiles to fit
rect_size -- 2-tuple of rectangle size as (width, height)
"""
# If the rectangle is taller than it is wide, reverse its dimensions
if rect_size[0] < rect_size[1]:
rect_size = rect_size[1], rect_size[0]
# Rectangle aspect ratio
rect_ar = rect_size[0] / rect_size[1]
# tiles_max_height is the square root of tile_count, rounded up
tiles_max_height = math.ceil(math.sqrt(tile_count))
best_tile_size = 0
# i in the range [1, tile_max_height], inclusive
for i in range(1, tiles_max_height + 1):
# tiles_used is the arrangement of tiles (width, height)
tiles_used = math.ceil(tile_count / i), i
# tiles_ar is the aspect ratio of this arrangement
tiles_ar = tiles_used[0] / tiles_used[1]
# Calculate the size of each tile
# Tile pattern is flatter than rectangle
if tile_ar > rect_ar:
tile_size = rect_size[0] / tiles_used[0]
# Tile pattern is skinnier than rectangle
else:
tile_size = rect_size[1] / tiles_used[1]
# Check if this is the best answer so far
if tile_size > best_tile_size:
best_tile_size = tile_size
return best_tile_size
print max_tile_size(4, (100, 100))
Алгоритм можно описать следующим образом:
- Если прямоугольник выше, чем он широкий, переверните его так, чтобы он был шире, чем высокий.
- Рассчитайте s , квадратный корень из числа плиток, округленный в большую сторону. (Названо
tiles_max_height в коде.)
- Цикл, где i идет от 1 до с включительно:
- Построить сетку из квадратов, которая составляет количество плиток / i квадратов в ширину и i квадратов в высоту. (Округлите все. Это «дополняет» недостающие плитки, например, используя 2 плитки на 2 плитки, когда общее количество плиток равно 3.)
- Сделайте эту сетку как можно большей. (Рассчитайте это, используя пропорции.) Определите размер одной плитки.
- Используя этот размер, определите общую площадь, покрытую плиткой.
- Проверьте, является ли это лучшая общая площадь на данный момент; если это так, сохраните размер квадрата
- Вернуть этот квадрат
Это, вероятно, один из более быстрых алгоритмов, перечисленных здесь, так как он вычисляет лучший размер квадрата в O (sqrt ( n )) для n плиток.
Обновление
При дальнейшем рассмотрении эта проблема имеет более простое решение, основанное на решении выше. Скажем, вам дано 30 плиток. Ваши возможные расстановки плиток легко вычисляются:
- 30 x 1 (соотношение сторон 30,0000)
- 15 x 2 (соотношение сторон 7.5000)
- 10 x 3 (соотношение сторон 3.3333)
- 8 x 4 (соотношение сторон 2.0000)
- 6 x 5 (соотношение сторон 1,2000)
- 6 x 6 (соотношение сторон 1.0000)
Скажите, что ваш прямоугольник равен 100 x 60. Соотношение сторон вашего прямоугольника составляет 1,6667. Это между 1,2 и 2. Теперь вам нужно только вычислить размеры плиток для 8х4 и 6х5.
Первый шаг все еще технически требует O (sqrt ( n )), поэтому этот обновленный метод не асимптотически быстрее, чем первая попытка.
Некоторые обновления из ветки комментариев
/*
Changes made:
tiles_used -> tiles_used_columns, tiles_used_rows
(it was originally a 2-tuple in the form (colums, rows))
*/
/* Determine the maximum sized tile possible. */
private function wesleyGetTileSize() : Number {
var tile_count : Number = slideCount.value;
var b : Number = heightOfBox.value;
var a : Number = widthOfBox.value;
var ratio : Number;
// // If the rectangle is taller than it is wide, reverse its dimensions
if (a < b) {
b = widthOfBox.value;
a = heightOfBox.value;
}
// Rectangle aspect ratio
ratio = a / b;
// tiles_max_height is the square root of tile_count, rounded up
var tiles_max_height : Number = Math.ceil(Math.sqrt(tile_count))
var tiles_used_columns : Number;
var tiles_used_rows : Number;
var tiles_ar : Number;
var tile_size : Number;
var best_tile_size : Number = 0;
// i in the range [1, tile_max_height], inclusive
for(var i: Number = 1; i <= tiles_max_height + 1; i++) {
// tiles_used is the arrangement of tiles (width, height)
tiles_used_columns = Math.ceil(tile_count / i);
tiles_used_rows = i;
// tiles_ar is the aspect ratio of this arrangement
tiles_ar = tiles_used_columns / tiles_used_rows;
// Calculate the size of each tile
// Tile pattern is flatter than rectangle
if (tiles_ar > ratio){
tile_size = a / tiles_used[0] ;
}
// Tile pattern is skinnier than rectangle
else {
tile_size = b / tiles_used[1];
}
// Check if this is the best answer so far
if (tile_size > best_tile_size){
best_tile_size = tile_size;
}
}
returnedSize.text = String(best_tile_size);
return best_tile_size;
}