作者defsrisars (阿转)
看板Grad-ProbAsk
标题[理工] 105台大资工 离散问题
时间Tue Dec 19 18:26:15 2017
https://imgur.com/9lKnQm6
1. 第14题
https://webptt.com/cn.aspx?n=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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1513679177.A.057.html
1F：推 djmez: 因为self dual 所以（00）（11）的结果相同绑定在一起了12/19 19:56
2F：→ djmez: （01）（10）也同理12/19 19:57
第一题了解了！谢谢大大～
第二题有大大能指导一下吗Q_Q
※ 编辑: defsrisars (111.82.50.197), 12/19/2017 20:22:30
3F：→ TMDTMD2487: 第二题我的作法 n=n0+n1+n2, i=n1+n2, i=n-n0 12/19 20:23
4F：→ TMDTMD2487: n0=n2+1, i=n-n2-1, i>=n-i-1, 2i>=n-1 12/19 20:24
5F：推 winiel559: 第二题你就想 有最多leaf=>每个节点都有两个儿子 12/19 20:52
6F：→ winiel559: 然後画一下就知道外部节点e=i+1，搭配e=n-1移项一下就 12/19 20:53
7F：→ winiel559: 好了 12/19 20:53
8F：→ winiel559: 打错 ^e=n-i 12/19 20:54
感谢两位大大~~
会了Q
※ 编辑: defsrisars (61.230.52.157), 12/21/2017 10:51:13