[理工] 105台大資工 離散問題

[defsrisars (阿轉)]

https://imgur.com/9lKnQm6

1. 第14題 https://www.ptt.cc/bbs/Grad-ProbAsk/M.1484804380.A.71E.html
在這篇有大大說明到


每個布林代數有2值 0 or 1 , 又因為 self dual : (0,0) = (1,1) (0,1) = (1,0) 2個
變數有4種可能 但又需要直接砍半 所以除 2 m 個變數 為 2^m 但砍半後剩下 2^(m-1)
所以布林代數 m 個variable 內共有 2^2^(m-1) 種可能性

這邊想了很久，唯一不理解的是，為什麼要砍半呢@@
(0,0) (0,1) (1,0) (1,1) 應該就算4個input不是嗎？
抱歉有點愚鈍，想不明白

ans: 2^(2^(m-1))

2. 第15題也不是很懂
binary tree上的所有node n與internal node i的關係是什麼意思？
關係式又是怎麼求得的呢？
謝謝

ans: ceil( (n-1)/2 )

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.228.240.19
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1513679177.A.057.html
推 djmez: 因為self dual 所以（00）（11）的結果相同綁定在一起了
→ djmez: （01）（10）也同理
第一題瞭解了！謝謝大大～
第二題有大大能指導一下嗎Q_Q
※ 編輯: defsrisars (111.82.50.197), 12/19/2017 20:22:30
→ TMDTMD2487: 第二題我的作法 n=n0+n1+n2, i=n1+n2, i=n-n0
→ TMDTMD2487: n0=n2+1, i=n-n2-1, i>=n-i-1, 2i>=n-1
推 winiel559: 第二題你就想 有最多leaf=>每個節點都有兩個兒子
→ winiel559: 然後畫一下就知道外部節點e=i+1，搭配e=n-1移項一下就
→ winiel559: 好了
→ winiel559: 打錯                              ^e=n-i
感謝兩位大大~~
會了Q
※ 編輯: defsrisars (61.230.52.157), 12/21/2017 10:51:13