Re: [資工]政大資科102-103 四題

[FRAXIS (喔喔)]

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

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 72.80.156.211
※ 文章網址: http://www.ptt.cc/bbs/Grad-ProbAsk/M.1419360413.A.063.html
推 HiltonCool: 他定義的函數為f(x1,x2,...,xk,xk,...,x2,x1)
→ HiltonCool: 所以我才會覺得題目的symmetric不是離散的symmetric
→ HiltonCool: 但數學應該不會用f：{0,1}^k → {0,1}定義一個函數吧
→ HiltonCool: 這樣不就等於是f:{0,1} → {0,1}嗎？
→ FRAXIS: {0,1}^k 代表是k個bits..
→ HiltonCool: 我知道，但以數學的角度來看，重複k次跟原來是一樣的
→ FRAXIS: 好吧 我沒看清楚題目 但是我覺得他打錯字了..
→ FRAXIS: 因為按照你的解釋 這樣輸入會有2k個 但是題目說有k個變數.
→ qoojordon: = =...F大有睡覺嗎?
推 qoojordon: 我手邊沒有答案只能提出來大家討論 =口=
→ qoojordon: 最大的問題應該是x1,x2...xk第定義是什麼? 依照f定義,
→ qoojordon: 輸入是字串,輸出是boolean,可是題目把x1放在輸入,代表
→ qoojordon: x1是字串? 後面定義的symmetric又對x1~xk做sigma,定義
→ qoojordon: 是總合?boalean的OR?還是??
→ galapous: 我也搞不懂他最後sigma是什麼意思
→ HiltonCool: 我也是在猜測題目要考的是什麼，因為考在DS又給這樣的
→ HiltonCool: 函數，所以我才把他解讀成是回文，單就input數量來看
→ HiltonCool: 的話，input總共會有2k個應該是沒錯的，只是symmetric
→ HiltonCool: 的函數是什麼我就不清楚了
→ FRAXIS: 我會這樣回 是因為symmetric function在計算理論上
→ FRAXIS: 是有明確定義的..  看wiki的Symmetric Boolean function
推 qoojordon: 有點理解你要說的意思了 , 前半段怎麼mapping方式出來
→ qoojordon: 後半段就是一樣的輸出 , f其實就是 B^k→B
推 HiltonCool: 哇...那我完全理解錯誤，所以F大說題目打錯的地方應該
→ HiltonCool: 是f(x1,x2,...,xk)對吧？
→ qoojordon: http://ppt.cc/lcGT 應該就是你說的那樣 , 剛剛估到的
推 qoojordon: 照上面的說明,sigma的定義是相加不是OR,symmetric
→ qoojordon: boolean function在意的是input中有幾個1,這樣修改後的
推 qoojordon: 答案應該修正為2^(k+1)比較好,因為k個bits的輸入,1的個
→ qoojordon: 數可能是0~k共k+1種可能
→ qoojordon: 你也可以試試看看這題 http://ppt.cc/t4o2
→ qoojordon: ANS: 2^(2^n) , 4
已修正
※ 編輯: FRAXIS (72.80.156.211), 12/25/2014 01:15:57