作者SFMAndroid (安卓发送)
看板Grad-ProbAsk
标题[理工] 离散 找出递回关系
时间Thu Jun 21 14:41:14 2018
一直搞不懂要怎麽把题目的叙述化成递回关系式子
像是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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1529563276.A.2FF.html
※ 编辑: SFMAndroid (140.113.62.211), 06/21/2018 14:41:55
1F：→ SFMAndroid: Q8来说 是因为包含连续0的字串长度n-1,n-2和n-3 06/21 15:16
2F：→ SFMAndroid: 分别是互斥的关系才能这样扣掉吗? 06/21 15:17
3F：→ SFMAndroid: 那为什麽不用0开头 或是11 111之类的分case讨论呢 06/21 15:18
4F：→ JKLee: Q8:"不太懂为什麽1结尾时，会有A_(n-1)种组合" 06/21 16:39
5F：→ JKLee: 长度n-1的合法字串共A_(n-1)种， 06/21 16:40
6F：→ JKLee: 在上述字串结尾接上1，就变成长度n且合法的字串。 06/21 16:40
7F：→ JKLee: 长度n且1结尾的合法字串,去掉结尾1,就变成长度n-1的合法字 06/21 16:41
8F：→ JKLee: 串。 06/21 16:41
9F：→ JKLee: 由上可知，长度n且1结尾的合法字串，与长度n-1的合法字串， 06/21 16:44
10F：→ JKLee: 为1-to-1的对映关系。 06/21 16:44
11F：→ SFMAndroid: 了解 所以是先假设结尾1是合法字串 06/22 12:00
12F：→ SFMAndroid: 那n-1就一定是合法字串 然後递回下去 06/22 12:01
13F：→ SFMAndroid: 感谢J大！ 06/22 12:01