我試圖從單個數字中找到 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]
1 回答
拉莫斯之舞
TA貢獻1820條經驗 獲得超10個贊
將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
添加回答
舉報
0/150
提交
取消