iT邦幫忙

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嗎?我是畫格子亂算的
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
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 。

leo226 iT邦新手 5 級 ‧ 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 檢舉

基本上, 我引用第一個公式的時候, 擅自假設了公式中所有的變數都必須大於或等於 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, 在現在的計算機結構中該如何看待它, 就是一個值得探討的問題了.

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

感謝!

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

Ans:46
畫一個二維>5*>4的方格,(上下>=6,左右>=5)將題目的數字填入格裡
1,1=2 2,3=18 3,2=28, 如果要將數字填入,並符合題目要求,那麼
出現在4,5就是46。
要用數學表示式或寫程式解,這、、這,、、、,我不懂@@

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

說size=2也怪怪的...不過算得出來就是了

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

請問一下: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個數學式是怎麼看出來的呢?
不知道怎麼看出來的哭

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

阿,我想錯了應該是這樣:

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

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

阿,結果我答案套錯公式...應該是

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

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

A + C = 2 -> (1)
A + (B + 3)C = 18 -> (2)
A + (2B + 2)C = 28 -> (3)
這公式是怎麼套來的?看是看的懂,但卻不知道公式怎麼來的,怎麼代入的?
可以給我公式自己練習應該比較實際一點,感謝大師~

我要發表回答

立即登入回答