Re: [理工] [離散] 導遞迴式

看板Grad-ProbAsk作者compulsory (まけない!)時間15年前 (2011/01/05 00:15)推噓3(3推 0噓 5→)

留言8則, 4人參與討論串2/3 (看更多)

※ 引述《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

01/05 00:18, , 1^F

01/05 00:18, 1^F

→

compulsory

01/05 00:22, , 2^F

01/05 00:22, 2^F

→

compulsory

01/05 00:23, , 3^F

01/05 00:23, 3^F