我試圖從單個(gè)數(shù)字中找到 vector3 的最小組合，到目前為止我有工作代碼，但它確實(shí)效率不高。為了演示，假設(shè)用戶輸入數(shù)字n ，該函數(shù)應(yīng)輸出 3 個(gè)數(shù)字 ( x, y, z ) 與最小總和的組合，同時(shí)仍然能夠與原始數(shù)字n相乘。因此，如果用戶輸入 100 作為 n，則 x、y 和 z 應(yīng)該是 4、5 和 5。（或 (5, 5, 4); (5, 4, 5)）。我正在執(zhí)行 3 個(gè) for 循環(huán)來(lái)計(jì)算 x、y 和 z 的單獨(dú)值。它適用于小數(shù)字，但隨著n 的增加，計(jì)算量變得難以置信。我正在尋找任何可以改變計(jì)算方法的方法，從而使計(jì)算速度更快。我對(duì)近似算法持開放態(tài)度，因?yàn)檫@不需要 100% 準(zhǔn)確。我最初是用 Lua 編寫的，但問題與一種語(yǔ)言沒有直接關(guān)系。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 語(yǔ)法。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]
1 回答
拉莫斯之舞
TA貢獻(xiàn)1820條經(jīng)驗(yàn) 獲得超10個(gè)贊
將n所有主要因子的每個(gè)拆分分解并測(cè)試為 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
添加回答
舉報(bào)
0/150
提交
取消