有没有更有效的方法从单个数字中找到最小的 Vector3 组合？

Question

我试图从单个数字中找到 vector3 的最小组合，到目前为止我有工作代码，但它确实效率不高。

为了演示，假设用户输入数字n ，该函数应输出 3 个数字 ( x, y, z ) 与最小总和的组合，同时仍然能够与原始数字n相乘。

因此，如果用户输入 100 作为 n，则 x、y 和 z 应该是 4、5 和 5。（或 (5, 5, 4); (5, 4, 5)）。

我正在执行 3 个 for 循环来计算 x、y 和 z 的单独值。它适用于小数字，但随着n 的增加，计算量变得难以置信。我正在寻找任何可以改变计算方法的方法，从而使计算速度更快。我对近似算法持开放态度，因为这不需要 100% 准确。

我最初是用 Lua 编写的，但问题与一种语言没有直接关系。

function CalculateVector(Size)

    local Vectors = {}

    local Lowest = math.huge

    local Index = nil

    for x = 0, Size, 1 do

        for y = 0, Size, 1 do

            for z = 0, Size, 1 do

                if Size - (x * y * z) == 0 then

                    table.insert(Vectors, Vector3.new(x, y, z))

                end

            end

        end 

    end

    table.foreachi(Vectors, function(i, v)

        local Combined = v.X + v.Y + v.Z

        if Combined < Lowest then

            Lowest = Combined

            Index = i

        end

    end)

    return Vectors[Index]

end

Python 中的相同代码，以防有人不知道 Lua 语法。

class Vector3:

    def __init__(self, x, y, z):

        self.X = x

        self.Y = y

        self.Z = z

def CalculateVector(Size):

    Vectors = []

    Lowest = Size + 3

    Index = None

    for x in range(Size):

        for y in range(Size):

            for z in range(Size):

                if Size - (x * y * z) == 0:

                    Vectors.append(Vector3(x, y, z))

    for i,v in enumerate(Vectors):

        Combined = v.X + v.Y + v.Z

        if Combined < Lowest:

            Lowest = Combined

            Index = i

    return Vectors[Index]

Answer 1

将n所有主要因子的每个拆分分解并测试为 3 组function split_number_into_factors_having_min_sum(n, factors)&nbsp; &nbsp;assert(n > 0 and factors > 0)&nbsp; &nbsp;local primes = {}&nbsp; &nbsp;local degrees = {}&nbsp; &nbsp;local terms = {}&nbsp; &nbsp;local p = 2&nbsp; &nbsp;local step = {4, 1, 2, 0, 2}&nbsp; &nbsp;local m = 0&nbsp; &nbsp;while n > 1 do&nbsp; &nbsp; &nbsp; if p * p > n then&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;p = n&nbsp; &nbsp; &nbsp; end&nbsp; &nbsp; &nbsp; if n % p == 0 then&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;local d = 0&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;repeat&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; d = d + 1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; n = n / p&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;until n % p ~= 0&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;m = m + 1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;primes[m] = p&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;degrees[m] = d&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;terms[m] = {}&nbsp; &nbsp; &nbsp; end&nbsp; &nbsp; &nbsp; p = p + step[p % 6]&nbsp; &nbsp;end&nbsp; &nbsp;local parts = {}&nbsp; &nbsp;for j = 1, factors do&nbsp; &nbsp; &nbsp; parts[j] = 1&nbsp; &nbsp;end&nbsp; &nbsp;local best_sum = math.huge&nbsp; &nbsp;local best_parts = {}&nbsp; &nbsp;local process_next_prime&nbsp; &nbsp;local function split_in_terms(sum, qty, k)&nbsp; &nbsp; &nbsp; if qty < factors then&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;local max_val = parts[qty] == parts[qty + 1] and sum > terms[k][qty] and terms[k][qty] or sum&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;qty = qty + 1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;local min_val = qty == factors and sum or 0&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;for val = min_val, max_val do&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; terms[k][qty] = val&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; split_in_terms(sum - val, qty, k)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;end&nbsp; &nbsp; &nbsp; else&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;local p = primes[k]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;for j = 1, factors do&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; parts[j] = parts[j] * p^terms[k][j]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;end&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;process_next_prime(k)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;for j = 1, factors do&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; parts[j] = parts[j] / p^terms[k][j]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;end&nbsp; &nbsp; &nbsp; end&nbsp; &nbsp;end&nbsp; &nbsp;function process_next_prime(k)&nbsp; &nbsp; &nbsp; if k < m then&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;split_in_terms(degrees[k + 1], 0, k + 1)&nbsp; &nbsp; &nbsp; else&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;local sum = 0&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;for j = 1, factors do&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sum = sum + parts[j]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;end&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;if sum < best_sum then&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; best_sum = sum&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for j = 1, factors do&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;best_parts[j] = parts[j]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; end&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;end&nbsp; &nbsp; &nbsp; end&nbsp; &nbsp;end&nbsp; &nbsp;process_next_prime(0)&nbsp; &nbsp;table.sort(best_parts)&nbsp; &nbsp;return best_partsend用法：local t = split_number_into_factors_having_min_sum(100, 3)print(unpack(t))&nbsp; --> 4 5 5