陣列記憶體位址計算

1. 基礎觀念：一維陣列 (1-Dim Array)

公式：\(Loc(A[i]) = L_0 + (i - l) \times d\)

2. 進階觀念：二維陣列 (2-Dim Array)

宣告：\(A[l_1 \ldots u_1, \ l_2 \ldots u_2]\)
列數 (Rows)：\(R = u_1 - l_1 + 1\)
行數 (Cols)：\(C = u_2 - l_2 + 1\)

通用公式

Row-major (以列為主 - C/C++)：

\[Loc(A[i,j]) = L_0 + [(i - l_1) \times C + (j - l_2)] \times d\]
Column-major (以行為主 - Fortran)：

\[Loc(A[i,j]) = L_0 + [(j - l_2) \times R + (i - l_1)] \times d\]

3. 四大常考題型攻略 (含範例詳解)

🔥 型一：給定所有參數，求位址

題目：陣列 \(A=[-3\ldots8,\,-1\ldots14]\)，起始位址 \(L_0=100\)，元素大小 \(d=4\)。

1. Row-major (求 \(A[5,7]\))

先算行數 (Cols)：\(C = 14 - (-1) + 1 = 16\)
代入公式：

\[ \begin{aligned} Loc(5,7) &= 100 + \big((5 - (-3)) \times 16 + (7 - (-1))\big) \times 4 \\ &= 100 + \big(8 \times 16 + 8\big) \times 4 \\ &= 100 + (128 + 8) \times 4 \\ &= 100 + 544 = \boxed{644} \end{aligned}\]

2. Column-major (求 \(A[3,12]\))

先算列數 (Rows)：\(R = 8 - (-3) + 1 = 12\)
代入公式：

\[ \begin{aligned} Loc(3,12) &= 100 + \big((12 - (-1)) \times 12 + (3 - (-3))\big) \times 4 \\ &= 100 + \big(13 \times 12 + 6\big) \times 4 \\ &= 100 + (156 + 6) \times 4 \\ &= 100 + 162 \times 4 = \boxed{748} \end{aligned}\]

🔥 型二：給 2 個元素位址，判斷 Row/Col Major

題目：\(A(3,2)=1110\)，\(A(2,3)=1115\)，且 \(d=1\)。求儲存方式與 \(A(5,4)\)。

1. 判斷方式 (相對位移法)

\(\Delta i = 2-3 = -1\)
\(\Delta j = 3-2 = 1\)
\(\Delta Addr = 1115 - 1110 = 5\)
測試 Row-major：\(5 = (-1 \times C + 1) \times 1 \Rightarrow C=-4\) (不合理，刪去)
測試 Col-major：\(5 = (1 \times R + (-1)) \times 1 \Rightarrow R=6\) (合理！)
結論：Column-major，且總列數 \(R=6\)。

2. 求 \(A(5,4)\) (利用平移)

從 \(A(3,2)=1110\) 出發到 \((5,4)\)。
公式：\(Loc = 1110 + [(4-2)\times 6 + (5-3)] \times 1\)
計算：\(1110 + [2 \times 6 + 2] = 1110 + 14 = \boxed{1124}\)

🔥 型三：已知 2 點位址，求維度與第三點

題目：\(A[1\ldots m, 1\ldots n]\)，\(d=1\)，已知 \(A(3,3)=121\)，\(A(6,4)=159\)。求 \(A(10,7)\)。

1. 找出維度 (Row 還是 Col?)

\(\Delta i = 3, \Delta j = 1, \Delta Addr = 38\)
若 Row-major：\(38 = (3n + 1) \Rightarrow 3n=37 \Rightarrow n=12.33\) (非整數，剔除)
若 Col-major：\(38 = (1m + 3) \Rightarrow m=35\) (合理！)
結論：Column-major，且 \(m=35\)。

2. 求 \(A(10,7)\)

從 \(A(3,3)=121\) 平移到 \((10,7)\)。
\(\Delta i' = 7, \Delta j' = 4\)
\(Loc = 121 + (4 \times 35 + 7) \times 1 = 121 + 147 = \boxed{268}\)

🔥 型四：給 3 個元素位址，解全套 (B, n, m, d)

題目：\(A(2,3)=18, A(3,2)=28, A(1,1)=2\)。求 \(A(4,5)\)。

假設 Row-major 並列式

通式：\(Addr = B + ((i-1)n + (j-1))d\)

\(A(2,3) \to 18 = 2 + (n + 2)d\) (因為 \(B=A(1,1)=2\)) …①
\(A(3,2) \to 28 = 2 + (2n + 1)d\) …②

2. 解聯立

整理 ①：\(nd + 2d = 16\)
整理 ②：\(2nd + d = 26\)
② - ① \(\times 2\) (消去 \(nd\))：

\((2nd+d) - (2nd+4d) = 26 - 32 \Rightarrow -3d = -6 \Rightarrow \boxed{d=2}\)
代回 ①：\(2n + 4 = 16 \Rightarrow 2n=12 \Rightarrow \boxed{n=6}\)
檢查：\(n, d\) 皆為正整數，假設成立。(若是分數則改設 Column-major)

3. 求 \(A(4,5)\)

\(Loc = 2 + ((4-1)\times 6 + (5-1)) \times 2\)
\(Loc = 2 + (18 + 4) \times 2 = 2 + 44 = \boxed{46}\)

4. 高維度陣列 (3D, 4D, N-Dim)

3D Row-Major 實戰例題

題目：宣告 \(A[1\dots5, 2\dots4, 0\dots3]\)，Row-major，\(L_0=1000, d=2\)。求 \(A[3, 3, 2]\)。

1. 準備參數

各維度大小 (\(S_k\))：
- \(S_1 = 5-1+1 = 5\)
- \(S_2 = 4-2+1 = 3\)
- \(S_3 = 3-0+1 = 4\)
索引偏移 (\(idx\))：
- \(i_{off} = 3-1 = 2\)
- \(j_{off} = 3-2 = 1\)
- \(k_{off} = 2-0 = 2\)

方法 A：公式法

\[Loc = L_0 + [(i_{off})S_2 S_3 + (j_{off})S_3 + k_{off}] \times d\]

\[Loc = 1000 + [2 \times (3 \times 4) + 1 \times 4 + 2] \times 2\]

\[Loc = 1000 + [24 + 4 + 2] \times 2 = 1000 + 60 = \boxed{1060}\]

方法 B：霍納法則 (括號法) - 推薦考試用

\[Loc = L_0 + \Big( \big( (i_{off})S_2 + j_{off} \big) S_3 + k_{off} \Big) \times d\]

\[Loc = 1000 + \Big( \big( 2 \times 3 + 1 \big) \times 4 + 2 \Big) \times 2\]

\[Loc = 1000 + (7 \times 4 + 2) \times 2 = 1000 + 30 \times 2 = \boxed{1060}\]

5. N 維陣列通用公式

宣告：\(A[n_1, n_2, \ldots, n_k]\)

Row-major 通用公式：

\[Loc = L_0 + \left( \sum_{x=1}^{k} (i_x - l_x) \cdot (\prod_{y=x+1}^{k} S_y) \right) \cdot d\]

N 維霍納法則：

\[Offset = (\dots((i_1-l_1)S_2 + (i_2-l_2))S_3 + \dots)S_n + (i_n-l_n)\]

(口訣：上一層結果乘以下一層 Size，再加上下一層偏移)