作者:
JoJo56 (JoJO)
2014-12-17 00:51:14第7題
Given input{4371,1323,6173,4199,4344,9679,1989}and a hash funtion
h(X) = (X mod 10),show the results:
(b) open addressing hash table using quadratic probing (F(i)=3*i^2)
正常來說quadratic probing(二次方探測)應該是當f(x)發生溢位時
下一次探測的位址是(f(x)+i^2) mod b與(f(x)-i^2) mod b才對
所以若依照題目上的(F(i) = 3*i^2)的方式假如位置3發生溢位
我應該把資料放在 3*3^2 =27?還是再mod 10 = 7???是這樣嗎?
第8題
如果有題目再好不過了，因為題目有點長，我打關鍵字就好
(1)Merge Sort (2)Heap Sort (3)MST (4)Floyd-Warshall algo
(5)Find Max independent (6)Huffman's algo (7)Strassen's algo
(8)OBST (9)LCS problem (10) Ford-Fulkerson algo
有哪幾個屬於(a)Divide and Conquer (b)Dynamic Programming
(c)Greedy method (d)Others
這些演算法都知道，但是無法很明確的肯定是哪個，想對對答案
(a)5 (b) 1,4,6,7,8,9 (c) 3,10 (d)2 求解感謝
7,要mod/8(a)1,7 / 8(b) 4,8,9 / 8(c) 2,3,6/ 8(d)5,10
作者:
A4P8T6X9 (殘廢的名偵探)
2014-12-17 09:36:00heap 不太會說是貪婪吧？
作者:
JoJo56 (JoJO)
2014-12-17 11:42:00恩，我也覺得Heap Sort只是把MAX heap的Root刪除 然後調整感覺不出來有用到哪個話說7是因為那個演算法的關係？不然MatrixChain不是Dp解嗎
作者:
kather (Kather)
2014-12-17 13:25:00不是 一個是矩陣乘法 另一個是多個矩陣用甚麼順序乘在一起
heap sort分類到greedy確實不太好 , 但原本的想法只是heap sort的過程確實也滿足條件比較放寬的local最佳解
作者:
maque (Roadside)
2014-12-17 20:27:007.F(i)應該是mod10吧
作者:
JoJo56 (JoJO)
2014-12-18 16:00:00像題目那樣如果資料第一次放在9 所以第二次放在3*3^2mod10那第3次失敗後 是否是放在3*10mod10?再失敗就3*11mod?
題目給的F(i)不是實際值,而是相對於hame value的偏移量第一次失敗是放[9+F(1)]mod10=(9+9)mod10=8
作者:
JoJo56 (JoJO)
2014-12-18 16:39:00但F(1)不是3*1^2=3嗎？ 所以是(9+3)mod10等於2囉?
作者:
JoJo56 (JoJO)
2014-12-18 17:05:00恩 感謝你的解惑
作者:
JacobSyu (JacobSyu)
2014-12-27 01:05:007.100交大考過,沒看Cormen會誤解 8.heap sort => other