幣值爲2的硬幣兌換方法PYTHON

一旦機器接管，每枚硬幣的面額將爲2的冪：1分，2分，4分，8分，16分等等。硬幣的價值是沒有限制的。幣值爲2的硬幣兌換方法PYTHON

如果硬幣值的總和爲n，則一組硬幣對n進行更改。例如，下面的組做出改變爲7：

7 1美分硬幣 5 1美分，1 2美分硬幣 3 1美分，2 2美分硬幣 3 1美分，1 4 -cent硬幣 1 1美分，3 2美分硬幣 11美分，1 2美分，1 4-美分硬幣因此，有6點的方式，使對7.

寫的變化函數count_change使用一個正整數n並返回使用這些未來硬幣進行n更改的方法數。

我一直在努力使用樹遞歸一小時的這個問題，但它不工作。我正在考慮使用當前金額的2個分支 - 1和當前金額 - 可能的最大硬幣值，但結果永遠不會令人滿意。

請給我一個關於如何接近它的建議...... thx！

來源

2014-02-18 user3325659

哪裏是你的CURREN t代碼？什麼意思是「不起作用」：錯誤（提供完整的追溯），意想不到的輸出（提供輸入和預期的和實際的輸出）？ – jonrsharpe

這是一個功課題嗎？如果是這樣，請顯示你的努力到目前爲止。 – nish

我有點受騙...我打開這個問題，期待看看「2 python的力量」是什麼。至少， –

這是動態編程的一個例子

，您可以對動態編程標準公式實現它（見Coin Change Problem）

讓s = {1,5,10,25}我們coinset現在是標準的硬幣面值

讓f(x,y) = number_of_ways_to_make_change讓x=change_due;y=allowed_coinset_index

備註：如果y == 0，我們允許的coinset是{1}，如果y == 1，我們允許的coinset是{1,5} ...
任何change_due有1一個簡單的解決方案時，我們coinset只由{1}也就是說，如果你只有幾分錢，只存在一個方法，使改變（所有便士）
ERGO f(anything,0) == 1 && f(0,anything) == 1 && f(anything,anthing < 0) == 0

讓我們解決了幾個change_due值

change_due function_call  
1    f(1,0) = 1 
... 
4    f(4,0) = 1 
5    f(5,1) = f((5-5),1) + f(5,0) = 1 + 1 = 2 
... 
9    f(9,1) = f(9-5,1)+f(9,0) = f(4,1) + 1 = f(4,0*) + 1 = 1+1 = 2 
10   f(10,2) = f(10-10,2) + f(10,1) = f(0,2) + (f(5,1)+f(10,0))= 1+(2+1) = 4

，所以我們可以看到我們的基地情況

f(x,0) = f(0,y) = 1 
f(x is less than zero,y) = f(x,y is less than zero) = 0

注意，這適用於任何一組硬幣

V 的，這是重要的組成部分 V

#if x,y are not in above conditions we want to recursively call ourselves allowing us to build up to a complex solution from several simpler solutions 
f(x,y) = f(x-CHANGE_DENOM,y) + f(x,y-1)

可以從上面保持與該表玩，看看我們有多少種方法可以使16美分

S = [1,5,10,25] 
# our y is 2 (since S[2] = 10 which is the largest denomination < our change_due(16)) 
f(16,2) = f(16-S[2],2) + f(16,1) 
     = f(16-10,2) + f(16,1) = f(6,2) + f(16,1) 
    f(6,2) = f(6-S[2]) + f(6,1) = 0 + f(6,1) = 0+2#(see below) = 
    f(16,1) = f(16-S[1],1) + f(16,0) = f(11,1) + 1 
     f(11,1) = f(11-S[1],1) + f(11,0) = f(6,1) + 1 
      f(6,1) = f(6-S[1],1) + f(6,0) = f(1,1) + 1 
      f(1,1) = f(1-S[1],1) + f(1,0) = 0 + 1 = 1 
      f(6,1) = f(1,1) + 1 = 1 + 1 = 2 
     f(11,1) = f(6,1) + 1 = 2 + 1 = 3 
    f(16,1) = f(11,1) + 1 = 3+1 = 4 
f(16,2) = f(6,2) + f(16,1) = 2 + 4 = 6 ways to make change for 16 cents

現在你只需要讓你的大coinset工作

來源

2014-02-18 23:19:36

6是不是兩個權力 - 對於到期= 6 ... – isedev

幣值爲2的硬幣兌換方法PYTHON

回答

相關問題