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

看板Grad-ProbAsk作者 (喔喔)時間9年前 (2014/12/24 02:46), 9年前編輯推噓6(6推 0噓 26→)
留言32則, 4人參與, 最新討論串3/3 (看更多)
※ 引述《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
推
12/24 03:45, , 1F
他定義的函數為f(x1,x2,...,xk,xk,...,x2,x1)
12/24 03:45, 1F
→
12/24 03:46, , 2F
所以我才會覺得題目的symmetric不是離散的symmetric
12/24 03:46, 2F
→
12/24 03:55, , 3F
但數學應該不會用f：{0,1}^k → {0,1}定義一個函數吧
12/24 03:55, 3F
→
12/24 03:56, , 4F
這樣不就等於是f:{0,1} → {0,1}嗎？
12/24 03:56, 4F
→
12/24 04:22, , 5F
{0,1}^k 代表是k個bits..
12/24 04:22, 5F
→
12/24 04:28, , 6F
我知道，但以數學的角度來看，重複k次跟原來是一樣的
12/24 04:28, 6F
→
12/24 07:48, , 7F
好吧 我沒看清楚題目 但是我覺得他打錯字了..
12/24 07:48, 7F
→
12/24 07:49, , 8F
因為按照你的解釋 這樣輸入會有2k個 但是題目說有k個變數.
12/24 07:49, 8F
→
12/24 07:53, , 9F
= =...F大有睡覺嗎?
12/24 07:53, 9F
推
12/24 08:00, , 10F
我手邊沒有答案只能提出來大家討論 =口=
12/24 08:00, 10F
→
12/24 08:02, , 11F
最大的問題應該是x1,x2...xk第定義是什麼? 依照f定義,
12/24 08:02, 11F
→
12/24 08:05, , 12F
輸入是字串,輸出是boolean,可是題目把x1放在輸入,代表
12/24 08:05, 12F
→
12/24 08:07, , 13F
x1是字串? 後面定義的symmetric又對x1~xk做sigma,定義
12/24 08:07, 13F
→
12/24 08:09, , 14F
是總合?boalean的OR?還是??
12/24 08:09, 14F
→
12/24 08:54, , 15F
我也搞不懂他最後sigma是什麼意思
12/24 08:54, 15F
→
12/24 13:18, , 16F
我也是在猜測題目要考的是什麼，因為考在DS又給這樣的
12/24 13:18, 16F
→
12/24 13:19, , 17F
函數，所以我才把他解讀成是回文，單就input數量來看
12/24 13:19, 17F
→
12/24 13:20, , 18F
的話，input總共會有2k個應該是沒錯的，只是symmetric
12/24 13:20, 18F
→
12/24 13:20, , 19F
的函數是什麼我就不清楚了
12/24 13:20, 19F
→
12/24 20:54, , 20F
我會這樣回 是因為symmetric function在計算理論上
12/24 20:54, 20F
→
12/24 20:55, , 21F
是有明確定義的.. 看wiki的Symmetric Boolean function
12/24 20:55, 21F
推
12/24 21:18, , 22F
有點理解你要說的意思了 , 前半段怎麼mapping方式出來
12/24 21:18, 22F
→
12/24 21:21, , 23F
後半段就是一樣的輸出 , f其實就是 B^k→B
12/24 21:21, 23F
推
12/24 22:28, , 24F
哇...那我完全理解錯誤，所以F大說題目打錯的地方應該
12/24 22:28, 24F
→
12/24 22:29, , 25F
是f(x1,x2,...,xk)對吧？
12/24 22:29, 25F
→
12/25 00:24, , 26F
http://ppt.cc/lcGT 應該就是你說的那樣 , 剛剛估到的
12/25 00:24, 26F
推
12/25 00:31, , 27F
照上面的說明,sigma的定義是相加不是OR,symmetric
12/25 00:31, 27F
→
12/25 00:33, , 28F
boolean function在意的是input中有幾個1,這樣修改後的
12/25 00:33, 28F
推
12/25 00:35, , 29F
答案應該修正為2^(k+1)比較好,因為k個bits的輸入,1的個
12/25 00:35, 29F
→
12/25 00:36, , 30F
數可能是0~k共k+1種可能
12/25 00:36, 30F
→
12/25 00:42, , 31F
你也可以試試看看這題 http://ppt.cc/t4o2
12/25 00:42, 31F
→
12/25 00:43, , 32F
ANS: 2^(2^n) , 4
12/25 00:43, 32F
已修正 ※ 編輯: FRAXIS (72.80.156.211), 12/25/2014 01:15:57
‣ 更多 FRAXIS 的文章
文章代碼(AID): #1KcRYT1Z (Grad-ProbAsk)
‣ 更多 FRAXIS 的文章
文章代碼(AID): #1KcRYT1Z (Grad-ProbAsk)