Re: [理工] [離散]-遞迴
※ 引述《yesa315 (XD)》之銘言：
: 求一 n-digit 數字串列由 0,1,2,3組成 含偶0且偶1的有幾種? 請用遞廻
: 用生成函數來看 我一下就想出來了
: 用遞廻觀念 有點卡卡的
: 另An為解
: 1.首項 =\= 0,1 方法數 2A(n-1)
: 再來就卡了
: 請高手指導
: 謝謝
我來挑戰看看 = =
先給定 n-digit
step 1.
把 {0,1}, {2,3}看成兩個個體
則{0,1}各有 1/2的機會總數為偶數/奇數
假設{0,1}總數為偶數的情況下
{0}的總數為偶數的機率為1/2
故 {0,1}為奇數的可能性 = 2*{0,1}為偶數且{0}{1}也為偶數
step 2:
故我們知道 在 {0,1}為奇數的情況下, 只要在加上特定的 {0,1}
就可以得到 {0},{1}皆為偶數的情況 ---- 情況1
且在 {0},{1}皆為偶數的情況下 只要加上任意的 {2},{3}
依然可以得到{0}{1}皆為偶數 ---- 情況2
故 a_n = 2*a_{n-1} + 2*a_{n-1} = 4*a_n{n-1}
==> a_n = c*2^n
又 a_1 = 1
故 a_n = 2^{n-1} done!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.112.39.42
推
12/28 18:41, , 1F
12/28 18:41, 1F
※ 編輯: CMJ0121 來自: 59.112.39.42 (12/28 19:00)
→
12/28 19:01, , 2F
12/28 19:01, 2F
討論串 (同標題文章)