將一個數字分解爲幾乎相同的因子

我想將一個數字分解成儘可能相互接近的數字元組，其產品是初始數字。輸入是我們想要的數字n以及所需因子的數字m。將一個數字分解爲幾乎相同的因子

對於這兩個因素的情況（m==2），這是不夠尋找的最大因素不是一個平方根少，所以我可以做這樣的事情

def get_factors(n): 
    i = int(n**0.5 + 0.5) 
    while n % i != 0: 
    i -= 1 
    return i, n/i

因此，與120調用，這將導致10,12。

我意識到對於數字「大小接近」意味着什麼含糊不清。我不介意這是否被解釋爲最小化Σ(x_i - x_avg)或Σ(x_i - x_avg)^2或通常沿着這些線路的其他東西。

對於m==3情況下，我會期望336生產6,7,8和729生產9,9,9。

理想情況下，我想要一個通用的解決方案m，但如果有人有一個想法，即使是m==3它將不勝感激。我也歡迎一般的啓發式。

編輯：我寧願儘量減少因素的總和。對上述內容仍然感興趣，但如果有人有一個想法，以找出最佳的價值，使得因素的總和是最小的，它會很好！

來源

2015-01-20 Alec

你可以嘗試生成所有的主要因素，然後生成'M'的每個組合找到最小誤差。 – 2015-01-21 00:00:52

要回答你的第二個問題（其中m因素和最小），它將始終是最佳的數分裂成其首要因素。事實上，對於除4之外的任何正數複合數字，它的素數因子總和小於數字本身，因此可以通過將複合數字分解爲其素數因子來改善具有合成數字的任何分割。

要回答你的第一個問題，其他人建議的貪婪方法是行不通的，正如我在評論中指出的4104打破了他們，貪婪會立即提取8作爲第一個因子，然後將被迫分割剩下的數字到[3, 9, 19]，未能找到更好的解決方案[6, 6, 6, 19]。但是，簡單的DP可以找到最佳解決方案。 DP的狀態是我們試圖考慮的因素，我們想要獲得多少因素，DP的價值是可能的最佳總和。下面的代碼的一些東西。它可以通過更智能地進行分解來進行優化。

n = int(raw_input()) 
left = int(raw_input()) 


memo = {} 
def dp(n, left): # returns tuple (cost, [factors]) 
    if (n, left) in memo: return memo[(n, left)] 

    if left == 1: 
     return (n, [n]) 

    i = 2 
    best = n 
    bestTuple = [n] 
    while i * i <= n: 
     if n % i == 0: 
      rem = dp(n/i, left - 1) 
      if rem[0] + i < best: 
       best = rem[0] + i 
       bestTuple = [i] + rem[1] 
     i += 1 

    memo[(n, left)] = (best, bestTuple) 
    return memo[(n, left)] 


print dp(n, left)[1]

例如

[In] 4104 
[In] 4 
[Out] [6, 6, 6, 19]

來源

2015-01-21 08:52:49 Ishamael

這個怎麼樣，對於米 = 3和一些ñ：

獲得的比ñ立方根小ñ的最大因素，稱之爲F1
除以n由f1，稱之爲g
查找g「」m = 2示例中的「大致相等的因子」。

對於336，小於立方根336的最大因子是6（我認爲）。將336除以6得到56（另一個因素，去圖！）對56進行相同的數學運算並尋找兩個因子，我們得到7和8.

請注意，對於少於3個因子的任何數字。這種方法可以擴展爲m> 3，也許。

如果這是正確的，我不是太瘋狂了，該解決方案將是一個遞歸函數：

factors=[] 
n=336 
m=3 

def getFactors(howMany, value): 
    if howMany < 2: 
    return value 

    root=getRoot(howMany, value) # get the root of value, eg square root, cube, etc. 
    factor=getLargestFactor(value, root) # get the largest factor of value smaller than root 
    otherFactors=getFactors(howMany-1, value/factor) 
    otherFactors.insert(factor) 
    return otherFactors 
print getFactors(n, m)

我懶得其餘代碼，但應該這樣做。

來源

2015-01-21 00:05:56 whiterook6

我喜歡這個問題的貪婪方法。首先在解決方案樹中深入探索首先搜索每個深度的最大可能因子。然而，如果沒有（howMany-x）因子，算法也應該能夠返回「無解」。或者，如果素數在達到所需深度之前加滿，則可以簡單地返回「1」，具有「1」因子的解可被認爲是不好的。 – BitTickler 2015-01-21 19:03:27

換句話說：如果值/因子爲素數並且遞歸的下一個深度不是最終深度，則不需要調用getFactors（howMany-1，value/factor）。 – BitTickler 2015-01-21 19:07:25

您可以從相同的原則開始：查找低於或等於作爲因子的m根的數字。然後你可以遞歸找到其餘的因素。

def get_factors(n, m): 
    factors = [] 
    factor = int(n**(1.0/m) + .1) # fudged to deal with precision problem with float roots 
    while n % factor != 0: 
     factor = factor - 1 
    factors.append(factor) 
    if m > 1: 
     factors = factors + get_factors(n/factor, m - 1) 
    return factors 

print get_factors(729, 3)

來源

2015-01-21 00:11:06

對於4104，你將得到（3,8,9,19），而（6,6,6,19）對於任一損失函數都更好。 – Ishamael 2015-01-21 08:38:20

將一個數字分解爲幾乎相同的因子

回答

相關問題