推 da0910cc: 07/14 23:05
→ metalalive:謝謝@@ 但不知道題目的例子是給錯嗎? 07/24 13:07
→ metalalive:ㄟ,沒事我看錯,謝謝 07/24 13:08
※ 引述《metalalive (想玩音樂)》之銘言：
: 遞迴, section 5-6後面
: http://imageshack.us/photo/my-images/713/0140g.jpg/
: 這裡題意我沒有很清楚, 看解答敘述劃線那段也看得一頭霧水
: 他是問說 "擲 2n次骰子,前面k次出現head且 後面k次出現tail , 的所有可能數"
: 事嗎?
: 那該怎麼分析它的情況呢?
: 一直想不到怎麼轉成 下面 a_n那個式子
: 謝謝!!
它的example是說
n=3時 必須投完2n=6次 head跟tail的個數才會相等
HHHTTT跟HHTHTT都是在投到第6次頭尾個數才相等
HT HHTT 這個投到第2次就相等了 並不符合bn
根據題目給的an的定義: 2n次投擲有n次head和n次tail
很直觀滿足bn一定滿足an
所以必存在一個整數i
會讓head和tail個數第一次相同在第2i次投擲
所以前2i次toss有bi種
剩下 2n-2i = 2(n-i)次投擲一定要head和tail數相同才可以 就是a(n-i)種
這樣就直接推了
a(n) = a(0)b(n) + a(1)b(n-1) + ... + a(n-1)b(1) + a(0)+b(n)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.118.110.186
※ 編輯: mqazz1 來自: 140.118.110.186 (07/14 20:31)