0

## 考題:陣列問題

There is a 2-dimensional array X. Given that X(1,1) is at address of 2, X(2,3) at address of 18, X(3,2) is at address of 28. What is the address of X (4,5)?

jako iT邦新手 2 級 ‧ 2011-01-05 18:10:34 檢舉
46嗎?我是畫格子亂算的

### 3 個回答

10
shortie
iT邦新手 5 級 ‧ 2011-01-06 14:20:59

(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
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.

(B)

B + c · i + d · j (0)

(1, 1) = 2
--> B + c + d = 2 (1)
(2, 3) = 18
--> B + 2c + 3d = 18 (2)
(3, 2) = 28
--> B + 3c + 2d = 28 (3)

--> 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

leo226 iT邦新手 4 級 ‧ 2011-01-06 15:38:08 檢舉

Lc = 0, Lr = 0 can't be true...<==這個要怎麼判斷呢？
Lc,Lr要從0,0開始代入嗎？

shortie iT邦新手 5 級 ‧ 2011-01-06 16:21:06 檢舉

leo226 iT邦新手 4 級 ‧ 2011-01-07 15:58:27 檢舉

8
Pankt
iT邦研究生 1 級 ‧ 2011-01-06 09:07:51

Ans:46

1,1=2 2,3=18 3,2=28, 如果要將數字填入，並符合題目要求，那麼

8
fillano
iT邦超人 1 級 ‧ 2011-01-06 09:52:51

1. 陣列及位址都是1 base（從1開始算）
2. 假設每行有Y個元素，每個元素的size是Z
3. 從題目條件可知：
Z = 2
y + 3Z = 18
2Y + 2Z = 28
4. 所以Y = 12
5. 所以X(4,5)的位址在3*12+2*5 = 46

fillano iT邦超人 1 級 ‧ 2011-01-06 09:59:48 檢舉

leo226 iT邦新手 4 級 ‧ 2011-01-06 12:07:36 檢舉

y + 3Z = 18，2Y + 2Z = 28，X(4,5)的位址在3*12+2*5 = 46，這３個數學式是怎麼看出來的呢？

fillano iT邦超人 1 級 ‧ 2011-01-06 13:12:58 檢舉

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

fillano iT邦超人 1 級 ‧ 2011-01-06 13:43:44 檢舉

0 + (3*6 + 5) * 2 = 46

leo226 iT邦新手 4 級 ‧ 2011-01-06 15:41:01 檢舉

A + C = 2 -> (1)
A + (B + 3)C = 18 -> (2)
A + (2B + 2)C = 28 -> (3)