algorithm - 查找具有给定体积的所有大小的长方体

Question

我有一个整数区间，我需要找到所有体积在所述区间内的唯一长方体。

我想出了一个循环遍历 3 个数字(长方体的大小)(1x1x1、1x1x2、...；2x1x1 也被认为与 1x1x2 相同)的所有唯一组合，从 1 到间隔，然后检查计算的体积是否落在间隔内。如果上限不是太大，则此解决方案非常有效。但如果间隔以千结尾，解决方案就会变得非常慢。

我对代码并不感兴趣，因为我对如何以不同方式解决这个问题的算法感兴趣。你会如何解决这个问题？

Answer 1

如果您的代码很慢，它可能正在尝试可以立即丢弃的值范围，或者它过于复杂并在循环条件等情况下计算平方根或立方根。尝试像下面的代码示例这样简单的操作，其中我确保 a ≤ b ≤ c 以避免重复:

if (Math.cbrt == undefined) // cubic root fix for older browsers
    Math.cbrt = function(x) {var n = 1; while (n * n * n <= x) ++n; return n - 1;}

function cuboids(min_volume, max_volume) {
    var results = [];
    var cr = Math.cbrt(max_volume);
    for (var a = 1; a <= cr; a++) {
        var sr = Math.sqrt(max_volume / a);
        for (var b = a; b <= sr; b++) {
            var lower = Math.ceil(min_volume / (a * b));
            var upper = Math.floor(max_volume / (a * b));
            for (var c = Math.max(b, lower); c <= upper; c++) {
                results.push([a, b, c]);
            }
        }
    }
    return results;
}

var results = cuboids(99900, 100000);
for (var i in results) document.write(results[i].join("*") + "<br>");