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

看板Grad-ProbAsk作者 (安卓發送)時間7年前 (2018/06/21 14:41), 7年前編輯推噓0(0推 0噓 13→)
留言13則, 2人參與, 7年前最新討論串1/1
一直搞不懂要怎麼把題目的敘述化成遞迴關係式子 像是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
→
06/21 15:16, 7年前 , 1F
Q8來說 是因為包含連續0的字串長度n-1,n-2和n-3
06/21 15:16, 1F
→
06/21 15:17, 7年前 , 2F
分別是互斥的關係才能這樣扣掉嗎?
06/21 15:17, 2F
→
06/21 15:18, 7年前 , 3F
那為什麼不用0開頭 或是11 111之類的分case討論呢
06/21 15:18, 3F
→
06/21 16:39, 7年前 , 4F
Q8:"不太懂為什麼1結尾時，會有A_(n-1)種組合"
06/21 16:39, 4F
→
06/21 16:40, 7年前 , 5F
長度n-1的合法字串共A_(n-1)種，
06/21 16:40, 5F
→
06/21 16:40, 7年前 , 6F
在上述字串結尾接上1，就變成長度n且合法的字串。
06/21 16:40, 6F
→
06/21 16:41, 7年前 , 7F
長度n且1結尾的合法字串,去掉結尾1,就變成長度n-1的合法字
06/21 16:41, 7F
→
06/21 16:41, 7年前 , 8F
串。
06/21 16:41, 8F
→
06/21 16:44, 7年前 , 9F
由上可知，長度n且1結尾的合法字串，與長度n-1的合法字串，
06/21 16:44, 9F
→
06/21 16:44, 7年前 , 10F
為1-to-1的對映關係。
06/21 16:44, 10F
→
06/22 12:00, 7年前 , 11F
了解 所以是先假設結尾1是合法字串
06/22 12:00, 11F
→
06/22 12:01, 7年前 , 12F
那n-1就一定是合法字串 然後遞迴下去
06/22 12:01, 12F
→
06/22 12:01, 7年前 , 13F
感謝J大！
06/22 12:01, 13F
‣ 更多 SFMAndroid 的文章
文章代碼(AID): #1RAqYCB_ (Grad-ProbAsk)