這個問題在這里已經有了答案： 整數磁區的優雅 Python 代碼 [關閉] （11 個回答） 昨天關閉。
我正在撰寫一個 python 函式，它以 3 到 200 之間的整數值作為輸入，使用將等于該數字的唯一非零數字計算總和的數量并列印輸出。例如; 將 3 作為輸入 1 將被列印，因為只有 1 2 將給出 3，將 6 作為輸入 3 將被列印，因為 1 2 3、1 5 和 2 4 等于 6。我的代碼僅適用于數字更少超過 30 之后，它開始變慢。如何優化我的代碼以針對 3 到 200 之間的所有輸入有效運行。
from itertools import combinations
def solution(n):
count = 0
max_terms = 0
num = 0
for i in range(1,n):
if num i <= n:
max_terms = 1
num = num i
for terms in range(2,max_terms 1):
for sample in list(combinations(list(range(1,n)),terms)):
if sum(sample) == n:
count = 1
print(count)
uj5u.com熱心網友回復：
生成所有組合確實不是很有效，因為大多陣列合不會加起來n。
相反，您可以使用遞回函式，該函式可以在洗掉一個磁區（即總和的一項）后呼叫，并且將解決剩余數量的問題，給出一個額外的指示，即未來的磁區應該大于一個剛拿。
為了進一步提高效率，您可以使用記憶化（動態規劃）來避免多次解決同一子問題。
這是代碼：
def solution(n, least=1, memo={}):
if n < least:
return 0
key = (n, least)
if key in memo: # Use memoization
return memo[key]
# Counting the case where n is not partitioned
# (But do not count it when it is the original number itself)
count = int(least > 1)
# Counting the cases where n is partitioned
for i in range(least, (n 1) // 2):
count = solution(n - i, i 1)
memo[key] = count
return count
使用這些引數測驗了代碼。評論列出了計算的總和：
print(solution(1)) # none
print(solution(2)) # none
print(solution(3)) # 1 2
print(solution(4)) # 1 3
print(solution(5)) # 1 4, 2 3
print(solution(6)) # 1 2 3, 1 5, 2 4
print(solution(7)) # 1 2 4, 1 6, 2 5, 3 4
print(solution(8)) # 1 2 5, 1 3 4, 1 7, 2 6, 3 5
print(solution(9)) # 1 2 6, 1 3 5, 2 3 4, 1 8, 2 7, 3 6, 4 5
print(solution(10)) # 1 2 3 4, 1 2 7, 1 3 6, 1 4 5, 2 3 5, 1 9, 2 8, 3 7, 4 6
uj5u.com熱心網友回復：
你的問題不夠清楚。所以，我在做一些假設......
所以，你想要的是輸入一個數字。說 4，然后找出兩個不同數字加起來的總組合。如果這就是您想要的，那么答案很簡單。
對于 4，讓我們將其視為“n”。'n' 有 1 3,2 2 的組合。
對于 n 為 6，組合是 - 1 5,2 4,3 3。
你可能已經發現了一個模式。（4 和 6 有一半的組合）同樣，對于奇數，它們的組合是前偶數的一半。即 - 5 有 (4/2)=2 連擊。即 1 4,2 3 所以...
獲得組合數的公式是 -
(n)/2 - 這是如果您想包含相同數量的組合，例如 2 2 表示 4，但排除帶有 0 的組合。即 0 4 表示 4
(n 1)/2 - 如果您想排除具有 0 的組合，即 0 4 代表 4 或具有相同數字的組合，即 2 2 代表 4，則此方法有效。
(n-1)/2 - 此處不包括相同數量的組合。即 2 2 不會被算作 n 為 4 的組合。此外，0 組合，即 0 4 為 4 被排除在外。
n 是主要數字。在這些示例中，它是“4”。這僅在 n 是整數并且計算后這些值存盤為整數時才有效。3 個數字組合是完全不同的。我相信也有一個公式。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/380281.html
下一篇：一個關于連續順序的演算法題