在計數變化遞歸算法中，爲什麼我們返回1如果amount = 0？

我正在修讀課程，對於作業，我已經編寫了一個代碼來計算給定一個名單的金額變化。做了大量的研究，我找到了各種算法的解釋。在遞歸實現中，其中一個基本情況是if the amount money is 0，然後是the count is 1。我不明白爲什麼，但這是代碼工作的唯一方式。我覺得這個數字是0，那麼沒有辦法改變它，我應該拋出異常。該代碼看起來像：在計數變化遞歸算法中，爲什麼我們返回1如果amount = 0？

function countChange(amount : Int, denoms :List[Int]) : Int = { 
    if (amount == 0) return 1 ....

任何解釋是非常感謝。

來源

2014-05-06 awm

有一個辦法，那辦法就是'{}'，空集：

或者，你可以從組合數學爭論。 – ggovan

遞歸按原樣運行，因爲它將貨幣分配到零（只有當準許零時才允許更改）。 – cageman

我在Coursera討論組中發佈了一個關於這個問題的問題。實際上，這個問題沒有說明問題，組合的答案是暗示性的，但不是確定性的。另一種解釋是：如果錢是X，但沒有比X小的硬幣，那麼你不能給予改變（沒有任何改變的方式）。這也應該適用於X == 0。 –

爲了避免專門講述Coursera問題，我將引用一個更簡單但相似的問題。

2個硬幣翻轉有多少結果？ 4.

(H,H),(H,T),(T,H),(T,T)

1枚硬幣翻轉有多少結果？ 2.

(H),(T)

0硬幣翻轉有多少結果？ 1.

()

遞歸表達這種情況，N個硬幣翻轉有多少結果？讓我們把它f(N)其中

f(N) = 2 * f(N - 1), for N > 0 
f(0) = 1

的N = 0微不足道（基地）的情況下被選擇，使得不平凡的情況下，遞歸定義，制定出正確的。由於我們在這個例子中正在進行乘法運算，並且乘法運算的標識元素是1，所以選擇它作爲基本情況是有意義的。 n choose 0 = 1，0! = 1等

來源

2014-05-06 19:41:30

在計數變化遞歸算法中，爲什麼我們返回1如果amount = 0？

回答

相關問題