(A)
2-D array 元素位址的公式如下:
row-major :
addr (i,j) = B + W * ( Nc * (i - Lr) + (j - Lc) )
column-major :
addr (i,j) = B + W * ( (i - Lr) + Nr * (j - Lc) )
where:
i, j = subscript number
B = base address
W = width (size) of each element
Nc = number of Columns
Nr = Number of Rows
Lc = Lower-bound of Column
Lr = Lower-bound of Row
Row major:
(1, 1) is 2
-> Lc = 0, Lr = 0 can't be true
assume Lc, Lr both are 1:
(1, 1) = B + W * 0 = 2
--> B = 2
(2, 3) = 2 + W (Nc * 1 + 2) = 18
(3, 2) = 2 + W (Nc * 2 + 1) = 28
-->
W (Nc * 1 + 2) = 16
W (Nc * 2 + 1) = 26
Nc + 2 / 2Nc + 1 = 8 / 13
-> Nc = 6
-> W = 2
(4, 5) = 2 + 2 (6 * 3 + 4) = 46
column major:
(1, 1) is 2
--> Lc = 0, Lr = 0 can't be true
assume Lc, Lr both are 1:
(1, 1) = B + W * 0 = 2
--> B = 2
(2, 3) = 2 + W (1 + Nr * 2) = 18
(3, 2) = 2 + W (2 + Nr * 1) = 28
-->
W (1 + Nr * 2) = 16
W (2 + Nr * 1) = 26
-->
(1 + Nr * 2) / (2 + Nr * 1) = 8 / 13
--> Nr can't be found
--> The orignal 2-D array can't be arranged in column-major form.
所以我對這個問題的回答是 46 。
(B)
也可以參考 Wikipedia 提供的 2-D array 位址公式:
B + c · i + d · j (0)
B: fixed base address
c: row address increments
d: column address increments
(1, 1) = 2
--> B + c + d = 2 (1)
(2, 3) = 18
--> B + 2c + 3d = 18 (2)
(3, 2) = 28
--> B + 3c + 2d = 28 (3)
由 (1)
--> B = 2 - c - d (4)
(4) 帶入 (2)
--> 2 - c - d + 2c + 3d = 18
--> c = 16 - 2d (5)
(5) 帶入 (4)
--> B = 2 - (16 - 2d) - d
--> B = d - 14 (6)
(5), (6) 帶入 (3)
--> d - 14 + 3 (16 - 2d) + 2d = 28
--> 34 - 3d = 28
--> d = 6/3 = 2 (7)
(7) 帶入 (5)
--> c = 12 (8)
(7), (8) 帶入 (4)
--> B = 2 - 12 - 2 = -12 (9)
(7), (8), (9) 帶入 (0)
--> -12 + 12 * i + 2 * j (10)
(i, j) = (4, 5) 帶入 (10)
--> -12 + 12 * 4 + 2 * 5
--> 46
這個公式算出來的答案也是 46 。
Lc = 0, Lr = 0 can't be true...<==這個要怎麼判斷呢?
Lc,Lr要從0,0開始代入嗎?
基本上, 我引用第一個公式的時候, 擅自假設了公式中所有的變數都必須大於或等於 0. 因此, 當 Lc = 0, Lr = 0, (i, j) = (1, 1) 帶入公式的時候, B + W * ( Nc + 1 ) = 2 或 B + W * (1 + Nr) = 2, 均不可能找到正整數解, 因此才會推得 (Lc, Lr) = (0, 0) 是不可能為真。
其實若是從 Wikipedia 上的公式來看, 就不需要有這些假設, 2-D 陣列只要有三點就可以求解, N-D 陣列只要有 N+1 點就可以求解, 也可以不需要考慮 B 是否要大於 0, 只是既然是位址, 如果是一個負的 B, 在現在的計算機結構中該如何看待它, 就是一個值得探討的問題了.
感謝!
Ans:46
畫一個二維>5*>4的方格,(上下>=6,左右>=5)將題目的數字填入格裡
1,1=2 2,3=18 3,2=28, 如果要將數字填入,並符合題目要求,那麼
出現在4,5就是46。
要用數學表示式或寫程式解,這、、這,、、、,我不懂@@
需要做一些假設:
說size=2也怪怪的...不過算得出來就是了
請問一下:X(1,1) is at address of 2就是說Z=2嗎?
y + 3Z = 18,2Y + 2Z = 28,X(4,5)的位址在3*12+2*5 = 46,這3個數學式是怎麼看出來的呢?
不知道怎麼看出來的
阿,我想錯了應該是這樣:
start address: A
line-length: B
element size: C
A + C = 2 -> (1)
A + (B + 3)C = 18 -> (2)
A + (2B + 2)C = 28 -> (3)
(2)-(1) => (B+3)C - C = 16 => BC + 3C - C = 16 => BC + 2C = 16 -> (4)
(3)-(2) => (2B+2)C - (B+3)C = 10 => 2BC + 2C - BC - 3C = 10 => BC - C = 10 -> (5)
(4)-(5) => 3C = 6 -> C = 2 => 代入(1) => A = 0
=> 代入(2) => 0 + (B + 3)2 = 18 => 2B + 6 = 18 => 2B = 12 => B = 6
0 + (3 * 6 + 5 * 2) * 2 = 56
所以答案應該是56
阿,結果我答案套錯公式...應該是
0 + (3*6 + 5) * 2 = 46
A + C = 2 -> (1)
A + (B + 3)C = 18 -> (2)
A + (2B + 2)C = 28 -> (3)
這公式是怎麼套來的?看是看的懂,但卻不知道公式怎麼來的,怎麼代入的?
可以給我公式自己練習應該比較實際一點,感謝大師~