[理工] 離散 找出遞迴關係

[SFMAndroid (安卓發送)]

一直搞不懂要怎麼把題目的敘述化成遞迴關係式子

像是Rosen的第七版離散 p.510的第4和p.511的第8題

4. A country uses as currency coins with values of 1 peso,
2 pesos, 5 pesos, and 10 pesos and bills with values of
5 pesos, 10 pesos, 20 pesos, 50 pesos, and 100 pesos.
Find a recurrence for the number of ways to pay a bill
of n pesos if the order in which the coins and bills are paid matters.

助教給的答案是

An = An-1 + An-2 + 2*An-5 + 2*An-10 + An-20 + An-50 + An-100



8. Find a recurrence relation for the number of bit strings
of length n that contain three consecutive 0s.

Ans:

分成4個case討論，ending with 1, 10, 100, and 000

An = An-1 + An-2 + An-3 + 2^(n-3)

不懂為什麼要分成4個case討論

也不太懂為什麼1結尾時，會有An-1種組合，

最後000結尾時，又為什麼是2^(n-3) @@



有沒有大大能用比較淺顯的方式說明呢？

或是有哪位老師的講義比較推薦的

謝謝~

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.62.211
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1529563276.A.2FF.html
※ 編輯: SFMAndroid (140.113.62.211), 06/21/2018 14:41:55
→ SFMAndroid: Q8來說 是因為包含連續0的字串長度n-1,n-2和n-3
→ SFMAndroid: 分別是互斥的關係才能這樣扣掉嗎?
→ SFMAndroid: 那為什麼不用0開頭 或是11 111之類的分case討論呢
→ JKLee: Q8:"不太懂為什麼1結尾時，會有A_(n-1)種組合"
→ JKLee: 長度n-1的合法字串共A_(n-1)種，
→ JKLee: 在上述字串結尾接上1，就變成長度n且合法的字串。
→ JKLee: 長度n且1結尾的合法字串,去掉結尾1,就變成長度n-1的合法字
→ JKLee: 串。
→ JKLee: 由上可知，長度n且1結尾的合法字串，與長度n-1的合法字串，
→ JKLee: 為1-to-1的對映關係。
→ SFMAndroid: 了解 所以是先假設結尾1是合法字串
→ SFMAndroid: 那n-1就一定是合法字串 然後遞迴下去
→ SFMAndroid: 感謝J大！