※ 引述《HiltonCool (野獸瘋)》之銘言：
: ※ 引述《qoojordon (穎川琦)》之銘言：
: : 102 DS 9
: : 看不太懂題目再問甚麼 , 是考回文嗎 ?
: : 010010 長度k的回文可能個數有幾種 ?
: 應該就是考回文的個數沒錯
: 因為第 k 個 bit 一定要跟第 1 個 bit 一樣
: 所以前面 k/2 個 bits 一定要跟後面 k/2 個 bits 一樣
: 令 T(k) 表示長度為 k 的回文個數
: ┌ ┐
: => T(k) = 2^│k/2│，T(1) = 2
我不太懂為什麼這個跟回文有關係..
因為symmetric function只跟 x_i 的總和有關
http://ppt.cc/lcGT
所以一個symmetric function就等同於{0, 1, ..., k} -> {0, 1}的mapping
因此symmetric funtion的個數是2^(k+1)

他定義的函數為f(x1,x2,...,xk,xk,...,x2,x1)所以我才會覺得題目的symmetric不是離散的symmetric但數學應該不會用f：{0,1}^k → {0,1}定義一個函數吧這樣不就等於是f:{0,1} → {0,1}嗎？

{0,1}^k 代表是k個bits..

我知道，但以數學的角度來看，重複k次跟原來是一樣的

好吧 我沒看清楚題目 但是我覺得他打錯字了..因為按照你的解釋 這樣輸入會有2k個 但是題目說有k個變數.

= =...F大有睡覺嗎?我手邊沒有答案只能提出來大家討論 =口=最大的問題應該是x1,x2...xk第定義是什麼? 依照f定義,輸入是字串,輸出是boolean,可是題目把x1放在輸入,代表x1是字串? 後面定義的symmetric又對x1~xk做sigma,定義是總合?boalean的OR?還是??

我也搞不懂他最後sigma是什麼意思

我也是在猜測題目要考的是什麼，因為考在DS又給這樣的函數，所以我才把他解讀成是回文，單就input數量來看的話，input總共會有2k個應該是沒錯的，只是symmetric的函數是什麼我就不清楚了

我會這樣回 是因為symmetric function在計算理論上是有明確定義的.. 看wiki的Symmetric Boolean function

有點理解你要說的意思了 , 前半段怎麼mapping方式出來後半段就是一樣的輸出 , f其實就是 B^k→B

哇...那我完全理解錯誤，所以F大說題目打錯的地方應該是f(x1,x2,...,xk)對吧？

http://ppt.cc/lcGT 應該就是你說的那樣 , 剛剛估到的照上面的說明,sigma的定義是相加不是OR,symmetricboolean function在意的是input中有幾個1,這樣修改後的答案應該修正為2^(k+1)比較好,因為k個bits的輸入,1的個數可能是0~k共k+1種可能你也可以試試看看這題 http://ppt.cc/t4o2ANS: 2^(2^n) , 4