Research Space for Linear Algebra & Discrete Mathematics
利用排容原理，含連續五個0+含連續五個1-含連續五個0跟五個一連續五個0的case只有五個…以此類推不知行不行
若是要算10個bit不需要用到遞迴, 我們可以考慮以下幾種含有5個連續0的情形:1. 00000xxxxx : 2^52. 100000xxxx : 2^43. x100000xxx : 2(2^3)4. xx100000xx : (2^2)(2^2)5. xxx100000x : 2(2^3)6. xxxx100000 : 2^4上面六種情況總數加起來是 112; 若含有5個連續0, 則討論方式同上; 將含有連續0與含有連續1的情況加起來, 再扣掉 0000011111 與 1111100000 各被多算了 1 次, 那麼總數就是 2*112-2 = 222
請問助教,若題目是n個bit該怎麼列遞迴式子?好像很麻煩....
hmm...這裡要討論遞迴的確比較麻煩, 因為它是0和1的連續情形都要考慮, 而不是只有單一個; 若真的要遞的話, 我的方法是假設該遞迴式為A(n), 那麼先考慮B(n)為不含5個連續0且不含5個連續1個遞迴式, 則 B(0)=1, B(1)=2, B(2)=4, B(4)=16, B(5)=30 為了列遞迴式方便起見, 我們可以令B(-1)=1, B(a)=0, for all a<-1, 則B(n) = 2*[B(n-1) -B(n-1-5) +B(n-1-2*5) -...], for all n= 2*Σ(r>=0)((-1)^r)B(n-1-5r), 則A(n) = 2^n - B(n), for all n>0= 2^n - 2Σ(r>=0)((-1)^r)(2^(n-1-5r) - A(n-1-5r))所以 B(6) = 2(B(5)-B(0)) = 58B(7) = 2(B(6)-B(1)) = 112B(8) = 2(B(7)-B(2)) = 216B(9) = 2(B(8)-B(3)) = 416...以 n=10 為例, 先考慮 B(10), (a) 假設考慮第10個bit放0, 那麼前面就有B(9)種不含5個連續0或1的方法, 但我們還必須扣掉第 6 到第 9 的bit為10000而導致再加上最後一個bit後, xxxx100000成為含有 5 個連續 0 的所有可能, 這類型的可能一定是前4個bit為不含5個連續0或1, 再配上第 5 到第 9 個bit為10000的所有string, 所以要扣掉 B(4), 但在扣掉 B(4) 時又會多扣了開頭為1111+10000而導致含有5個連續1的情形, 所以要再加回 1 (也就是B(-1)); (b) 若最後一個bit若是 1, 則討論情形同上, 所以 B(10)=2*(B(9)-B(4)+B(-1))=802 => 1024 - 802 = 222
張貼留言
4 則留言:
利用排容原理，含連續五個0+含連續五個1-含連續五個0跟五個一
連續五個0的case只有五個…以此類推
不知行不行
若是要算10個bit不需要用到遞迴, 我們可以考慮以下幾種含有5個連續0的情形:
1. 00000xxxxx : 2^5
2. 100000xxxx : 2^4
3. x100000xxx : 2(2^3)
4. xx100000xx : (2^2)(2^2)
5. xxx100000x : 2(2^3)
6. xxxx100000 : 2^4
上面六種情況總數加起來是 112; 若含有5個連續0, 則討論方式同上; 將含有連續0與含有連續1的情況加起來, 再扣掉 0000011111 與 1111100000 各被多算了 1 次, 那麼總數就是 2*112-2 = 222
請問助教,若題目是n個bit該怎麼列遞迴式子?好像很麻煩....
hmm...這裡要討論遞迴的確比較麻煩, 因為它是0和1的連續情形都要考慮, 而不是只有單一個; 若真的要遞的話, 我的方法是假設該遞迴式為A(n), 那麼先考慮B(n)為不含5個連續0且不含5個連續1個遞迴式, 則 B(0)=1, B(1)=2, B(2)=4, B(4)=16, B(5)=30
為了列遞迴式方便起見, 我們可以令
B(-1)=1, B(a)=0, for all a<-1, 則
B(n) = 2*[B(n-1) -B(n-1-5) +B(n-1-2*5) -...], for all n
= 2*Σ(r>=0)((-1)^r)B(n-1-5r), 則
A(n) = 2^n - B(n), for all n>0
= 2^n - 2Σ(r>=0)((-1)^r)(2^(n-1-5r) - A(n-1-5r))
所以
B(6) = 2(B(5)-B(0)) = 58
B(7) = 2(B(6)-B(1)) = 112
B(8) = 2(B(7)-B(2)) = 216
B(9) = 2(B(8)-B(3)) = 416
...
以 n=10 為例, 先考慮 B(10), (a) 假設考慮第10個bit放0, 那麼前面就有B(9)種不含5個連續0或1的方法, 但我們還必須扣掉第 6 到第 9 的bit為10000而導致再加上最後一個bit後, xxxx100000成為含有 5 個連續 0 的所有可能, 這類型的可能一定是前4個bit為不含5個連續0或1, 再配上第 5 到第 9 個bit為10000的所有string, 所以要扣掉 B(4), 但在扣掉 B(4) 時又會多扣了開頭為1111+10000而導致含有5個連續1的情形, 所以要再加回 1 (也就是B(-1)); (b) 若最後一個bit若是 1, 則討論情形同上, 所以 B(10)=2*(B(9)-B(4)+B(-1))=802
=> 1024 - 802 = 222
張貼留言