[考題] 國考歷屆考題與考題觀念討論(書裡看到的選這個)請附上想法、出處
一、有一個 N ×N 的上三角矩陣，每個元素占一個Byte。
(1) 試以最少的記憶體儲存之，請說明應用何種資料結構？（5 分）
(2) 總共用多少記憶體空間？（5 分）
(3) 若矩陣第一個元素（0,0）在位址S，請分別以 Row-Major 及
Column-Major Ordering 寫出矩陣任意元素（i, j）所在位址的表示式。（10 分）
(1) 應該是以一維陣列就可以了。
1 2 3
0 4 5 => [1,2,3,4,5,6]
0 0 6
(2) 記憶體只需要 N(N+1)/2 Bytes
(3) 這題就有點可怕了...
Row- Major:
0 1 2 3
4 5 6
7 8
9
應該是 S + 正常矩陣的位置 - 空格的三角形位置
=> S + (Ni + j) - i(i + 1)/2
Column- Major:
0 1 3 6
2 4 7
5 8
9
應該是 S + 正常矩陣的位置 - 空格的梯形位置
=> S + (i + Nj) - (2N - j - 1)j/2
這是我在考試時想到的概念，可是因為計算有點複雜結果沒能算出來...
反而還在考試中浪費了一堆時間...
回到家之後花一點時間想想，覺得這個想法應該沒錯，
可是計算也太花時間 = ="
不知道有沒有大大這題有寫出來的?
想知道是我概念錯誤還是純粹計算太慢?
還是有比較容易的解法?
--
一、有一個 N ×N 的上三角矩陣，每個元素占一個Byte。
(1) 試以最少的記憶體儲存之，請說明應用何種資料結構？（5 分）
(2) 總共用多少記憶體空間？（5 分）
(3) 若矩陣第一個元素（0,0）在位址S，請分別以 Row-Major 及
Column-Major Ordering 寫出矩陣任意元素（i, j）所在位址的表示式。（10 分）
(1) 應該是以一維陣列就可以了。
1 2 3
0 4 5 => [1,2,3,4,5,6]
0 0 6
(2) 記憶體只需要 N(N+1)/2 Bytes
(3) 這題就有點可怕了...
Row- Major:
0 1 2 3
4 5 6
7 8
9
應該是 S + 正常矩陣的位置 - 空格的三角形位置
=> S + (Ni + j) - i(i + 1)/2
Column- Major:
0 1 3 6
2 4 7
5 8
9
應該是 S + 正常矩陣的位置 - 空格的梯形位置
=> S + (i + Nj) - (2N - j - 1)j/2
這是我在考試時想到的概念，可是因為計算有點複雜結果沒能算出來...
反而還在考試中浪費了一堆時間...
回到家之後花一點時間想想，覺得這個想法應該沒錯，
可是計算也太花時間 = ="
不知道有沒有大大這題有寫出來的?
想知道是我概念錯誤還是純粹計算太慢?
還是有比較容易的解法?
--
All Comments