Блог

Я пытаюсь найти наименьшую комбинацию 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]
  

Разложите 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