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

Дан исходный прямоугольник N×M. Задача: определить сколько раз можно полностью "уложить" (ориентация любая) меньший прямоугольник n×m в исходный. Возможно, для будущих ходоков будет интересно КАК. Спасибо.

Ответ

Задачка решается просто. Если нужен ответ на вопрос КАК // Возвращает массив расположения блоков [ { x, y, w, h } ] function calc(W, H, w, h) {
var hor = pack([], W, H, w, h, 0, 0); var ver = pack([], W, H, h, w, 0, 0);
// сортировка блоков в порядке сверху-вниз, слева-направо // если не планируется нумеровать блоки - можно удалить return (hor.length >= ver.length ? hor : ver).sort(function(a, b) { return (a.y - b.y) || (a.x - b.x); });
function pack(pieces, W, H, w, h, x0, y0) { var x, y; var nx = W / w | 0; // число блоков, умещающееся по ширине var ny = H / h | 0; // по высоте var n = nx * ny; // всего for (y = 0; y < ny; y++) for (x = 0; x < nx; x++) { pieces.push({ x: x0 + x*w, y: y0 + y*h, w: w, h: h }); } if (W % w >= h && H >= w) { // осталось полезное место справа pack(pieces, W % w, H, h, w, x0 + nx*w, 0); } else if (H % h >= w && W >= h) { // осталось полезное место снизу pack(pieces, W, H % h, h, w, 0, y0 + ny*h); } return pieces; }
} Если нужен ответ на вопрос СКОЛЬКО // Возвращает число блоков function calc(W, H, w, h) {
return Math.max(pack(W, H, w, h), pack(W, H, h, w));
function pack(W, H, w, h) { var n = (W / w | 0) * (H / h | 0); if (W % w >= h && H >= w) { n += pack(W % w, H, h, w); } else if (H % h >= w && W >= h) { n += pack(W, H % h, h, w); } return n; }
} Демо: http://jsfiddle.net/RHq23/