Re: [理工]離散遞迴
※ 引述《maque (Que)》之銘言：
: 題目 http://ppt.cc/kNJC
: 小黃課本上有寫解答
: 但無法理解部分觀念
: 解答:http://ppt.cc/5ixl
: 若開始為0,則有an-1個方法
: 開始部分為什麼不討論為1
他是先討論含5個連續1的情況
因為含5個連續0與含5個連續1的情況是相同的
所以只要討論其中一種情況最後再乘以2倍即可
: 接下來討論若開始為10則有an-2個
: 這部分為什麼不討論00、01、11的情況?
如果你現在想討論的是含5個連續1的情況，則討論的順序會是：
0xxx...、10xxx...、110xxx...、1110xxx...、11110xxx...、11111xxx...
以下圖解說明：
假設an表示含5個連續1個方法數
┌─┐┌─────────────────┐
│0 ││ an-1 │=> 剩(n-1)個數要含5個連續1
└─┘└─────────────────┘
┌─┐┌─┐┌──────────────┐
│1 ││0 ││ an-2 │=> 剩(n-2)個數要含5個連續1
└─┘└─┘└──────────────┘
┌─┐┌─┐┌─┐┌───────────┐
│1 ││1 ││0 ││ an-3 │=> 剩(n-3)個數要含5個連續1
└─┘└─┘└─┘└───────────┘
┌─┐┌─┐┌─┐┌─┐┌────────┐
│1 ││1 ││1 ││0 ││ an-4 │=> 剩(n-4)個數要含5個連續1
└─┘└─┘└─┘└─┘└────────┘
┌─┐┌─┐┌─┐┌─┐┌─┐┌─────┐
│1 ││1 ││1 ││1 ││0 ││ an-5 │=> 剩(n-5)個數要含5個連續1
└─┘└─┘└─┘└─┘└─┘└─────┘
┌─┐┌─┐┌─┐┌─┐┌─┐┌─────┐
│1 ││1 ││1 ││1 ││1 ││ 2^(n-5) │=> 已出現5個連續1，後面任意即可
└─┘└─┘└─┘└─┘└─┘└─────┘
含5個連續0也是同樣的討論方式
最後只要再扣掉1111100000與0000011111即可
另外，開頭為00或01與開頭為0的方法數是一樣的
所以只能算一次，否則會重複算
你不能根據你現在討論的開頭是幾個bit去討論所有的情況
而是根據遞迴的條件作為你討論的依據
比方說你會先討論第一個bit
如果第一個bit是0，代表剩下的(n-1)個數中要含5個連續1
如果第一個bit是1，你不能說剩下的(n-1)個數中一樣要含5個連續1
因為如果第二個bit是0的話，代表你的第一個1被中斷了
只能從剩下的(n-2)個數中找到含5個連續1的方法數
所以這個情況就會變成是上面(an-2)的case
但如果第二個bit是1的話，代表你現在有兩個連續1
但你不能說剩下的(n-2)個數中要含5個連續1
因為如果第三個bit是0的話，代表你的前面兩個1被中斷了
只能從剩下的(n-3)個數中找到含5個連續1的方法數
所以這個情況就會變成是上面(an-3)的case
以此類推往下討論就會變成上面的討論方式
所以你必須依照你所定的遞迴條件和你目前的討論狀況作為討論的依據
: 前面有類似題目，例如二元序不含連續個0
: 會分成開頭為1，則有an-1個
: 若第一位為0，則有an-2個
: 則an=(an-1)+(an-2)
此題只要仿照上面的討論方式即可
假設an表示不含連續0的方法數
┌─┐┌─────────────────┐
│1 ││ an-1 │=> 剩(n-1)個數不含連續0
└─┘└─────────────────┘
┌─┐┌─┐┌──────────────┐
│0 ││1 ││ an-2 │=> 剩(n-2)個數不含連續0
└─┘└─┘└──────────────┘
: 麻煩解惑了! 謝謝!
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.42.184.228
※ 文章網址: http://www.ptt.cc/bbs/Grad-ProbAsk/M.1412781496.A.E9D.html
※ 編輯: HiltonCool (114.42.184.228), 10/08/2014 23:21:13
→
10/09 00:37, , 1F
10/09 00:37, 1F
討論串 (同標題文章)