2012-08-28

[離散]第五版P3-6的範例2

請問各位可以解釋這題是在問什麼嗎?

題目:
A palindrome is a string whose reversal is identical to the string . How many bit strings of length n are palindromes?

還有詳解說:
" 第一個字到第(n/2)取上限(ceiling)個字中每個字有2種可能 ",根據乘法原理,長度 n 的 palindrome 的 bit string 個數為2的(n/2)取上限(ceiling)次方

紅色這句話是什麼意思
可以詳細解釋嗎?
(哪兩種可能,可以舉例說明嗎)

謝謝!!

3 則留言:

Unknown 提到...

就是一個palindrome bit string 如果是奇數 則前面n/2+1個bit有兩種可能 如果是偶數則前n/2 bit也有兩種可能 因為是迴文 所以後面的bit必定跟前半字串one to one相關 所以考慮前半段久可以 合起來就是題目的解法

以上淺見~

Unknown 提到...

3bit
00 +0
01 +0
10 +1
11 +1

4bit
00 +00
01 +10
10 +01
11 +11

Unknown 提到...

您應該是非本系學生 bit string就是只有0和1的意思 這有點危險噢 要趕快加強題意瞭解