所以我想做的是把幾十萬大的數字分解成更小的數字，最好是2~9。
我首先想到的是素數分解，例如數字 49392 可以表示為 (2 x 2 x 2 x 2 x 3 x 3 x 7 x 7 x 7)。但是有素數和25378 = 2 × 12689這樣的數不能只用乘法來表示。
所以我想用乘法和加法分解這些數字，例如，數字 25378 可以表示為 25346 32 = (2 × 19 × 23 × 29) (2^5)。盡管如此，23 和 29 還是太大了，但我只是選擇了亂數，只是為了說明我的意思，通過使用加法和乘法來表達大數字，我確信表達 25378 的數字組合比 25346 和 32 更好。
無論如何，我認為編程這將涉及大量不必要的 if 陳述句，并且在大局中會非常慢。所以我想知道，是否有一個數學演算法或函式可以做這件事？如果沒有，我可以自己優化代碼，但我只是好奇，我自己在谷歌上找不到任何東西。
uj5u.com熱心網友回復：
假設問題是將一個數字寫成包含數字 1-9、加法和乘法的最簡單運算式（最簡單 = 最少的運算子數），那么這個 Python 程式會在 O(N^2) 時間內完成。
一個數字 N 可以寫成兩個較小數字的和或乘積，所以如果你預先計算了構造數字 1..N-1 的最簡單方法，那么你可以找到在 O(N) 中構造 N 的最簡單方法） 時間。那么這只是避免重復作業的問題——例如，在不損失運算式 A B 和 AB、A<=B 的一般性的情況下，并很好地列印出最終運算式。
def nice_exp(x, pri):
if isinstance(x, int):
return str(x)
else:
oppri = 1 if x[0] == '*' else 0
if oppri < pri:
bracks = '()'
else:
bracks = ['', '']
return '%s%s %s %s%s' % (bracks[0], nice_exp(x[1], oppri), x[0], nice_exp(x[2], oppri), bracks[1])
def solve(N):
infinity = 1e12
size = [infinity] * (N 1)
expr = [None] * (N 1)
for i in range(N 1):
if i < 10:
size[i] = 1
expr[i] = i
continue
for j in range(2, i):
if j * j > i: break
if i%j == 0 and size[j] size[i//j] 1 < size[i]:
size[i] = size[j] size[i//j] 1
expr[i] = ('*', expr[j], expr[i//j])
for j in range(1, i):
if j > i-j: break
if size[j] size[i-j] 1 < size[i]:
size[i] = size[j] size[i-j] 1
expr[i] = (' ', expr[j], expr[i-j])
return nice_exp(expr[N], 0)
print(solve(25378))
輸出：
2 * (5 4 * 7 * (5 7 * 8 * 8))
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/510087.html
標籤：算法数学数字因式分解
上一篇：“沒有與鍵CodingKeys關聯的值（stringValue:\"index\",intValue:nil)(\"index\")。”，underly
下一篇：在IRIS資料集上使用卷積