[理工] 離散 遞迴

[sooge (喜歡平井桃)]

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://www.ptt.cc/bbs/Grad-ProbAsk/M.1542382283.A.BB5.html
※ 編輯: sooge (120.105.145.184), 11/16/2018 23:35:49
推 JKLee: https://i.imgur.com/lMkHZaf.jpg
→ JKLee: 以上提供包含3個連續字元的解法
→ JKLee: https://i.imgur.com/LQeUSJ1.jpg
→ JKLee: 以上是3個連續1的解法
→ JKLee: 變化: 求長度n且不含12與21的三元字串總數
→ sooge: 請問第一張圖case2裡*2是什麼意思？ X不是都有3種了為什麼
→ sooge: 不是*3 所以那個*2並不是代表X是00,11,22三種可能的意思？
推 JKLee: 第一張圖 case 2
→ JKLee: 因 Y != X, 所以:
→ JKLee: 當 Y = 1, X = 2 or 3;
→ JKLee: 當 Y = 2, X = 1 or 3;
→ JKLee: 當 Y = 3, X = 1 or 2.
→ JKLee: Y決定好之後, X就剩2種可能.
→ JKLee: sorry,我寫錯. 請忽略case2與3寫的3種.
→ sooge: 為什麼遞迴裡可以把Y固定住 感覺怪怪的 Y固定住的情況下X是
→ sooge: 兩種沒錯 但把Y固定住那其他Y的值不用考慮嗎？如果是case2
→ sooge: 是*2不是*3不就代表Y只有考慮到1種數字(ex.1) 那2和3怎麼
→ sooge: 辦？
推 JKLee: 我不是很了解你卡在什麼地方.
→ JKLee: 我再重新描述一次我的作法.
→ JKLee: 見第一張圖 case 2
→ JKLee: 長度n的字串，
→ JKLee: 切成長度n-2的字串 string 1 與長度2的字串 string 2.
→ JKLee: string 1 是合法的，總共a_(n-2)種.
→ JKLee: string 2 是由2個相同字元構成.
→ JKLee: 我希望 string 1 後面接上的 string 2
→ JKLee: 不可以與 string 1 的結尾相同.
→ JKLee: 所以 string 1 接上 string 2 的方法數總共是
→ JKLee: a_(n-2) * 2
推 JKLee: 我舉另外一個例子:
→ JKLee: 有5種不同的球,取2顆作排列, 且2顆球不可相同.
→ JKLee: 共有5*4種可能.
→ JKLee: 第1個顆球有5種選擇.
→ JKLee: 第2顆球剩4種選擇.
推 JKLee: 感謝版友來信勘誤, 紅圈處應為 2*W_(n-3).
→ JKLee: https://i.imgur.com/rOstAvf.jpg
→ JKLee: 後面的過程也要跟著改
→ sooge: 不知道為什麼你說成string我就懂了 謝謝你！！解釋的超級
→ sooge: 詳細