有没有更有效的方法从单个数字中找到最小的 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]endPython 中的相同代码，以防有人不知道 Lua 语法。class Vector3:    def __init__(self, x, y, z):        self.X = x        self.Y = y        self.Z = zdef 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)

   assert(n > 0 and factors > 0)

   local primes = {}

   local degrees = {}

   local terms = {}

   local p = 2

   local step = {4, 1, 2, 0, 2}

   local m = 0

   while n > 1 do

      if p * p > n then

         p = n

      end

      if n % p == 0 then

         local d = 0

         repeat

            d = d + 1

            n = n / p

         until n % p ~= 0

         m = m + 1

         primes[m] = p

         degrees[m] = d

         terms[m] = {}

      end

      p = p + step[p % 6]

   end

   local parts = {}

   for j = 1, factors do

      parts[j] = 1

   end

   local best_sum = math.huge

   local best_parts = {}

   local process_next_prime

   local function split_in_terms(sum, qty, k)

      if qty < factors then

         local max_val = parts[qty] == parts[qty + 1] and sum > terms[k][qty] and terms[k][qty] or sum

         qty = qty + 1

         local min_val = qty == factors and sum or 0

         for val = min_val, max_val do

            terms[k][qty] = val

            split_in_terms(sum - val, qty, k)

         end

      else

         local p = primes[k]

         for j = 1, factors do

            parts[j] = parts[j] * p^terms[k][j]

         end

         process_next_prime(k)

         for j = 1, factors do

            parts[j] = parts[j] / p^terms[k][j]

         end

      end

   end

   function process_next_prime(k)

      if k < m then

         split_in_terms(degrees[k + 1], 0, k + 1)

      else

         local sum = 0

         for j = 1, factors do

            sum = sum + parts[j]

         end

         if sum < best_sum then

            best_sum = sum

            for j = 1, factors do

               best_parts[j] = parts[j]

            end

         end

      end

   end

   process_next_prime(0)

   table.sort(best_parts)

   return best_parts

end

用法：

local t = split_number_into_factors_having_min_sum(100, 3)

print(unpack(t))  --> 4 5 5