[理工] 離散 遞迴

看板Grad-ProbAsk作者 (喜歡平井桃)時間7年前 (2018/11/16 23:31), 7年前編輯推噓5(5推 0噓 34→)
留言39則, 2人參與, 7年前最新討論串12/17 (看更多)
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
推
11/17 09:27, 7年前 , 1F
11/17 09:27, 1F
→
11/17 09:39, 7年前 , 2F
以上提供包含3個連續字元的解法
11/17 09:39, 2F
→
11/17 10:04, 7年前 , 3F
11/17 10:04, 3F
→
11/17 10:04, 7年前 , 4F
以上是3個連續1的解法
11/17 10:04, 4F
→
11/17 10:09, 7年前 , 5F
變化: 求長度n且不含12與21的三元字串總數
11/17 10:09, 5F
→
11/17 10:37, 7年前 , 6F
請問第一張圖case2裡*2是什麼意思？ X不是都有3種了為什麼
11/17 10:37, 6F
→
11/17 10:37, 7年前 , 7F
不是*3 所以那個*2並不是代表X是00,11,22三種可能的意思？
11/17 10:37, 7F
推
11/17 10:44, 7年前 , 8F
第一張圖 case 2
11/17 10:44, 8F
→
11/17 10:44, 7年前 , 9F
因 Y != X, 所以:
11/17 10:44, 9F
→
11/17 10:44, 7年前 , 10F
當 Y = 1, X = 2 or 3;
11/17 10:44, 10F
→
11/17 10:44, 7年前 , 11F
當 Y = 2, X = 1 or 3;
11/17 10:44, 11F
→
11/17 10:44, 7年前 , 12F
當 Y = 3, X = 1 or 2.
11/17 10:44, 12F
→
11/17 10:44, 7年前 , 13F
Y決定好之後, X就剩2種可能.
11/17 10:44, 13F
→
11/17 10:53, 7年前 , 14F
sorry,我寫錯. 請忽略case2與3寫的3種.
11/17 10:53, 14F
→
11/17 11:19, 7年前 , 15F
為什麼遞迴裡可以把Y固定住 感覺怪怪的 Y固定住的情況下X是
11/17 11:19, 15F
→
11/17 11:19, 7年前 , 16F
兩種沒錯 但把Y固定住那其他Y的值不用考慮嗎？如果是case2
11/17 11:19, 16F
→
11/17 11:19, 7年前 , 17F
是*2不是*3不就代表Y只有考慮到1種數字(ex.1) 那2和3怎麼
11/17 11:19, 17F
→
11/17 11:19, 7年前 , 18F
辦？
11/17 11:19, 18F
推
11/17 11:59, 7年前 , 19F
我不是很了解你卡在什麼地方.
11/17 11:59, 19F
→
11/17 11:59, 7年前 , 20F
我再重新描述一次我的作法.
11/17 11:59, 20F
→
11/17 11:59, 7年前 , 21F
見第一張圖 case 2
11/17 11:59, 21F
→
11/17 11:59, 7年前 , 22F
長度n的字串，
11/17 11:59, 22F
→
11/17 11:59, 7年前 , 23F
切成長度n-2的字串 string 1 與長度2的字串 string 2.
11/17 11:59, 23F
→
11/17 11:59, 7年前 , 24F
string 1 是合法的，總共a_(n-2)種.
11/17 11:59, 24F
→
11/17 11:59, 7年前 , 25F
string 2 是由2個相同字元構成.
11/17 11:59, 25F
→
11/17 11:59, 7年前 , 26F
我希望 string 1 後面接上的 string 2
11/17 11:59, 26F
→
11/17 11:59, 7年前 , 27F
不可以與 string 1 的結尾相同.
11/17 11:59, 27F
→
11/17 11:59, 7年前 , 28F
所以 string 1 接上 string 2 的方法數總共是
11/17 11:59, 28F
→
11/17 11:59, 7年前 , 29F
a_(n-2) * 2
11/17 11:59, 29F
推
11/17 12:47, 7年前 , 30F
我舉另外一個例子:
11/17 12:47, 30F
→
11/17 12:47, 7年前 , 31F
有5種不同的球,取2顆作排列, 且2顆球不可相同.
11/17 12:47, 31F
→
11/17 12:47, 7年前 , 32F
共有5*4種可能.
11/17 12:47, 32F
→
11/17 12:47, 7年前 , 33F
第1個顆球有5種選擇.
11/17 12:47, 33F
→
11/17 12:47, 7年前 , 34F
第2顆球剩4種選擇.
11/17 12:47, 34F
推
11/17 12:50, 7年前 , 35F
感謝版友來信勘誤, 紅圈處應為 2*W_(n-3).
11/17 12:50, 35F
→
11/17 12:50, 7年前 , 36F
11/17 12:50, 36F
→
11/17 12:51, 7年前 , 37F
後面的過程也要跟著改
11/17 12:51, 37F
→
11/17 13:17, 7年前 , 38F
不知道為什麼你說成string我就懂了 謝謝你！！解釋的超級
11/17 13:17, 38F
→
11/17 13:17, 7年前 , 39F
詳細
11/17 13:17, 39F
‣ 更多 sooge 的文章
文章代碼(AID): #1RxkBBkr (Grad-ProbAsk)
討論串 (同標題文章)
完整討論串 (本文為第 12 之 17 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共17篇)
‣ 更多 sooge 的文章
文章代碼(AID): #1RxkBBkr (Grad-ProbAsk)