[理工] [ds] 96 清大資工

看板Grad-ProbAsk作者 (可愛小小羅)時間13年前 (2011/01/27 22:09), 編輯推噓0(0推 0噓 17→)
留言17則, 4人參與, 最新討論串1/3 (看更多)
http://www.lib.nthu.edu.tw/library/department/ref/exam/eecs/cs/96/2101.pdf 請問第6題 選項(a)為什麼是F 第7題 (f) T ...怎麼證? -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 111.255.10.156 ※ 編輯: ai305428d 來自: 111.255.10.156 (01/27 22:10)
→
01/27 22:31, , 1F
7(f)：鴿籠原理問題。引述黃子嘉離散教材的證法：
01/27 22:31, 1F
→
01/27 22:31, , 2F
假設x_k和y_k表示第k個數開始最長的遞增/遞減序列長度
01/27 22:31, 2F
→
01/27 22:32, , 3F
以反證法出發，假設遞增遞減序列最長只到n
01/27 22:32, 3F
→
01/27 22:33, , 4F
那(x_k, y_k)最多只有n^2個組合，但因為有n^2+1個數字
01/27 22:33, 4F
→
01/27 22:33, , 5F
一定可以找到不相等的i,j使(x_i,y_i)=(x_j,y_j)
01/27 22:33, 5F
→
01/27 22:34, , 6F
可推得(x_i>x_j or y_i>y_j)，造成矛盾。
01/27 22:34, 6F
→
01/27 22:34, , 7F
6(a)詳細希望 Orz
01/27 22:34, 7F
→
01/27 23:16, , 8F
6(a) 他應該是問說 排序好的array 元素是不是很難找尋
01/27 23:16, 8F
→
01/27 23:16, , 9F
答案就是false嚕
01/27 23:16, 9F
→
01/27 23:27, , 10F
我是覺得false啦,如果裡面data的需求不一
01/27 23:27, 10F
→
01/27 23:30, , 11F
但題目有講"Are equally likely to be requested"
01/27 23:30, 11F
→
01/27 23:30, , 12F
講錯了..覺得是true
01/27 23:30, 12F
→
01/27 23:38, , 13F
能舉例嗎?
01/27 23:38, 13F
→
01/27 23:43, , 14F
如果對每個data需求不同,不是可以把比較常用的放在陣列
01/27 23:43, 14F
→
01/27 23:43, , 15F
前面節省search時間嗎?
01/27 23:43, 15F
→
01/27 23:45, , 16F
可是這題最後加上那段equally....
01/27 23:45, 16F
→
09/11 14:11, , 17F
前面節省search時 https://daxiv.com
09/11 14:11, 17F
‣ 更多 ai305428d 的文章
文章代碼(AID): #1DGNoduT (Grad-ProbAsk)
‣ 更多 ai305428d 的文章
文章代碼(AID): #1DGNoduT (Grad-ProbAsk)