作者compulsory (まけない!)
看板Grad-ProbAsk
標題Re: [理工] [離散] 導遞迴式
時間Wed Jan 5 00:15:37 2011
※ 引述《mqazz1 (無法顯示)》之銘言：
: find the number of ternary strings(containing only 0,1,2)
: that contain two consecutive 0
三種情況
↓1/2
1. 最後一個bit是1,2 __ __ __ __ __.... __ __ __ __ __ =>2an-1
|←前面n-1個bit遞回求連續0 →|
2. 最後一個bit是0 倒數第二個是 1or2 1/2 0
↓ ↓
__ __ __ __ __ ... __ __ __ __ __ =>2an-2
|← n-2個bit遞回求連續0 →|
3. 最後一個bit是0 倒數第二個也是0 前面n-2個bit就隨便排了
0 0
↓ ↓
__ __ __ __ __ ... __ __ __ __ __ =>(3^n-2)
|←3種隨便放滿n-2個bit →|
an=2(an-1) + 2(an-2) + 3^(n-2)
a1=0 因為1個bit不可能有連續兩個0
a2=1 因為兩個bit的時候 只有00這種pattern符合 只有一種
: ----------------------------------------------------------
: find the number of bit strings that contain the string "01"
: 請問這兩題要怎麼導呢?
: 謝謝
1.最後一個bit是0 遞回前面n-1個字串出現 01
↓0
__ __ __...__ __ __ => an-1
2.最後一個bit是1 倒數第二個是0 達成了所以前面n-2個隨便放
0 1
↓ ↓
__ __ __...__ __ __ => 2^n-2
3.倒數2 3個bit是01 前面n-3個隨便放
0 1 1
↓ ↓ ↓
__ __ __...__ __ __ => 2^n-3
4. 2^n-4
5. 2^n-5
..
..
n. 2^0
n-2 n-3 0
=>an = (an-1)+[2 + 2 ..........+2 ]
n-1
= (an-1)+ 2 -1
a1=0 因為長度1的字串不可能出現01
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.116.13.191
※ 編輯: compulsory 來自: 122.116.13.191 (01/05 00:18)
→ aoqq12:我突然有個小問題 那000 他該算幾次? 01/05 00:18
→ compulsory:不太懂你的意思 000是三個bit含兩個連續0的其中一個 01/05 00:22
→ compulsory:字串 01/05 00:23
推 aoqq12:!!對後= =我多想了 XD多謝 你還是不用懂我意思好了= =" 01/05 00:25
※ 編輯: compulsory 來自: 122.116.13.191 (01/05 00:34)
推 cakeboy:請問a1為什麼是1 01/05 00:33
→ cakeboy:長度1不是不可能有連續兩個0嗎? 01/05 00:34
→ compulsory:打錯了 XDD 01/05 00:34
推 mqazz1:謝摟! 01/05 01:04