推 prosperous: 遞迴王是你? 08/23 14:28
※ 引述《cschenptt (chen)》之銘言：
: 題目出自黃子嘉 p.3-12
: 只包含0與1兩個數字的數列稱為二元序列，
: 試問二元序列n-序列中包含偶數個0的序列有多少個？
: 看不懂解答
: 為什麼偶數個0和奇數個0的序列各佔一半ＱＱ
: http://imgur.com/a/h9kka
這題可以用遞回的角度去想
令包含奇數個0的二元n序列個數為An
令包含偶數個0的二元n序列個數為Bn
第n位假設為0, 則相當於二元n-1序列中包含奇數個0的序列個數
第n位假設為1, 則相當於二元n-1序列中包含偶數個0的序列個數
由此可以推論出以下式子
Bn = An-1 + Bn-1 = (2^n-1 - Bn-1) + Bn-1 = 2^n-1
An = 2^n - Bn = 2^n - 2^n-1 = 2^n-1
An = Bn
有錯誤在麻煩糾正 3Q
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.133.195.20
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1471607583.A.9E3.html
※ 編輯: amge1524 (220.133.195.20), 08/19/2016 19:54:14