作者sooge (喜歡平井桃)
看板Grad-ProbAsk
標題[理工] 離散 遞迴
時間Fri Nov 16 23:31:21 2018
https://i.imgur.com/NpPFg6V.jpg
我要問第7題 我想了好久了
很疑惑普通的解法要怎麼去慢慢推
因為答案這種方法很像就只適用於連續數字不超過兩個的問題
像是兩個連續1這種
但剛剛想了一下 ，一旦題目說包含3個以上連續1 我就又不知道怎麼處理了....
我不是看不懂解答 解答的我會
但我不知道不用這種方法要怎麼推出來
簡單來說就是我推到這裡我就推不下去了
https://i.imgur.com/KZa8BWh.jpg
因為會牽扯到1和2，我不知道該怎麼推後面的
麻煩各位強者幫我解惑了
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 120.105.145.182
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1542382283.A.BB5.html
※ 編輯: sooge (120.105.145.184), 11/16/2018 23:35:49
2F：→ JKLee: 以上提供包含3個連續字元的解法 11/17 09:39
4F：→ JKLee: 以上是3個連續1的解法 11/17 10:04
5F：→ JKLee: 變化: 求長度n且不含12與21的三元字串總數 11/17 10:09
6F：→ sooge: 請問第一張圖case2裡*2是什麼意思？ X不是都有3種了為什麼 11/17 10:37
7F：→ sooge: 不是*3 所以那個*2並不是代表X是00,11,22三種可能的意思？ 11/17 10:37
8F：推 JKLee: 第一張圖 case 2 11/17 10:44
9F：→ JKLee: 因 Y != X, 所以: 11/17 10:44
10F：→ JKLee: 當 Y = 1, X = 2 or 3; 11/17 10:44
11F：→ JKLee: 當 Y = 2, X = 1 or 3; 11/17 10:44
12F：→ JKLee: 當 Y = 3, X = 1 or 2. 11/17 10:44
13F：→ JKLee: Y決定好之後, X就剩2種可能. 11/17 10:44
14F：→ JKLee: sorry,我寫錯. 請忽略case2與3寫的3種. 11/17 10:53
15F：→ sooge: 為什麼遞迴裡可以把Y固定住 感覺怪怪的 Y固定住的情況下X是 11/17 11:19
16F：→ sooge: 兩種沒錯 但把Y固定住那其他Y的值不用考慮嗎？如果是case2 11/17 11:19
17F：→ sooge: 是*2不是*3不就代表Y只有考慮到1種數字(ex.1) 那2和3怎麼 11/17 11:19
18F：→ sooge: 辦？ 11/17 11:19
19F：推 JKLee: 我不是很了解你卡在什麼地方. 11/17 11:59
20F：→ JKLee: 我再重新描述一次我的作法. 11/17 11:59
21F：→ JKLee: 見第一張圖 case 2 11/17 11:59
22F：→ JKLee: 長度n的字串， 11/17 11:59
23F：→ JKLee: 切成長度n-2的字串 string 1 與長度2的字串 string 2. 11/17 11:59
24F：→ JKLee: string 1 是合法的，總共a_(n-2)種. 11/17 11:59
25F：→ JKLee: string 2 是由2個相同字元構成. 11/17 11:59
26F：→ JKLee: 我希望 string 1 後面接上的 string 2 11/17 11:59
27F：→ JKLee: 不可以與 string 1 的結尾相同. 11/17 11:59
28F：→ JKLee: 所以 string 1 接上 string 2 的方法數總共是 11/17 11:59
29F：→ JKLee: a_(n-2) * 2 11/17 11:59
30F：推 JKLee: 我舉另外一個例子: 11/17 12:47
31F：→ JKLee: 有5種不同的球,取2顆作排列, 且2顆球不可相同. 11/17 12:47
32F：→ JKLee: 共有5*4種可能. 11/17 12:47
33F：→ JKLee: 第1個顆球有5種選擇. 11/17 12:47
34F：→ JKLee: 第2顆球剩4種選擇. 11/17 12:47
35F：推 JKLee: 感謝版友來信勘誤, 紅圈處應為 2*W_(n-3). 11/17 12:50
37F：→ JKLee: 後面的過程也要跟著改 11/17 12:51
38F：→ sooge: 不知道為什麼你說成string我就懂了 謝謝你！！解釋的超級 11/17 13:17
39F：→ sooge: 詳細 11/17 13:17