我一直在試圖找出有多少種不同的方法可以將某個整數除以某個數字的總和。但我無法解決它。
原來的問題是：
假設需要從非常長的鋼筋上切割出長度為 5 厘米、8 厘米、17 厘米和 28 厘米的短鋼筋。
撰寫一個遞回函式，計算從長度為 n cm 的條中切割出上述短條的不同方法的數量，浪費的條不超過 3cm。
所以也就是用[5, 8, 17, 18]來除某個整數
def cut(x):
m = 0
l = [5, 8, 17, 28]
def cut_rod(x, m):
if x <= 3:
return m
else:
# I don't know what can I do here
return cut_rod(x, m 1)
return cut_rod(x, m)
for i in range(int(input())):
print(cut(int(input( )))
eg.輸入
line1：條數=3，然后輸入3次line2到底部：每個條的長度（int）
3
100
160
240
eg.output 3條輸入，所以輸出3行71表示有71種不同的方式來劃分bar1，長度為100
71
229
667
uj5u.com熱心網友回復：
好吧，一種產生結果的遞回方法：
def cut(x):
l = [5, 8, 17, 28]
def cut_rod(x, pool):
if x < 0: # base case 1: you cut more than there was available
return 0
if x <= 3: # base case 2: success, legal rest, no more cuts
return 1
# recursion:cut off each length, then work with the remainder
# restriction: to avoid duplicates, you cannot cut shorter ones than before
result = 0
for i, v in enumerate(pool):
result = cut_rod(x-v, pool[i:])
return result
return cut_rod(x, l)
cut(100)
# 71
cut(160)
# 229
cut(240)
# 667
獎金：
這個邏輯可以濃縮：
def cut(x):
def rec(x, p):
return x >= 0 and (x <= 3 or sum(rec(x-v, p[i:]) for i, v in enumerate(p)))
return cut_rod(x, [5, 8, 17, 28])
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/346477.html
下一篇：高效遞回隨機抽樣