题解：A--语言数组地址映射（Mid-Central USA 1996）

一、题目分析

本题要求根据数组声明计算数组引用的物理地址，核心是理解并应用地址计算公式。关键信息：

• 物理地址公式：$A[i₁,i₂,…,i_D] = C₀ + C₁i₁ + C₂i₂ + … + C_Di_D$
• 常数计算规则：
  • $C_D = 元素大小（字节）$
  • $C_d = C_{d+1}×(U_{d+1}-L_{d+1}+1)$（1≤d<D）
  • $C₀ = 基地址 - C₁L₁ - C₂L₂ - … - C_DL_D$
• 输入包含数组定义和引用，需输出对应物理地址

二、代码解析（C++实现）

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int L = 10 + 1;  // 数组名最大长度+1
const int N = 10 + 1;  // 最大数组数量+1

// 数组结构体，存储所有相关参数
struct Array {
    char name[L];       // 数组名
    int base;           // 基地址
    int size;           // 元素大小（字节）
    int dim;            // 维数
    int l[L], u[L];     // 各维下界和上界
    int c[L];           // 系数C₀到C_D
} a[N];

int n, r;  // n为数组数量，r为引用数量

// 根据数组名查找数组索引
int getid(char *s) {
    for (int i = 1; i <= n; i++)
        if (strcmp(a[i].name, s) == 0) return i;
    return -1;  // 题目保证输入合法，无需处理错误
}

int main() {
    scanf("%d%d", &n, &r);  // 读取数组数量和引用数量
    
    // 读取并处理每个数组定义
    for (int i = 1; i <= n; i++) {
        scanf("%s%d%d%d", a[i].name, &a[i].base, &a[i].size, &a[i].dim);
        for (int j = 1; j <= a[i].dim; j++)
            scanf("%d%d", &a[i].l[j], &a[i].u[j]);  // 读取各维上下界
        
        int d = a[i].dim;
        a[i].c[d] = a[i].size;  // 初始化C_D为元素大小
        
        // 计算C₁到C_{D-1}
        for (int j = d - 1; j >= 1; j--)
            a[i].c[j] = a[i].c[j + 1] * (a[i].u[j + 1] - a[i].l[j + 1] + 1);
        
        // 计算C₀ = 基地址 - Σ(C_j×L_j)
        int b = a[i].base;
        for (int j = 1; j <= d; j++)
            b -= a[i].c[j] * a[i].l[j];
        a[i].c[0] = b;
    }
    
    // 处理每个数组引用
    char name[L];
    int id[N];  // 存储引用的各维索引
    for (int i = 1; i <= r; i++) {
        scanf("%s", name);
        int ix = getid(name);  // 获取数组索引
        int d = a[ix].dim;
        
        // 读取引用的各维索引
        for (int j = 1; j <= d; j++)
            scanf("%d", &id[j]);
        
        // 计算物理地址：C₀ + Σ(C_j×i_j)
        int ans = a[ix].c[0];
        for (int j = 1; j <= d; j++)
            ans += a[ix].c[j] * id[j];
        
        // 按格式输出结果
        printf("%s[", name);
        for (int j = 1; j <= d; j++) {
            printf("%d", id[j]);
            if (j != d) printf(", ");  // 索引间用", "分隔
        }
        printf("] = %d\n", ans);
    }

    return 0;
}

三、关键公式与步骤解析

1. 系数计算

   • C_d的递推：从最高维D开始计算，低维系数依赖高维
     [ C_D = \text{size}, \quad C_d = C_{d+1} \times (U_{d+1} - L_{d+1} + 1) \ (d < D) ]
     该式表示低维每个索引变化对应高维的元素数量。

   • C₀的计算：基地址减去各维下界与对应系数的乘积
     [ C_0 = B - \sum_{d=1}^D C_d \times L_d ]
     确保当所有索引取最小值时地址正确。

2. 物理地址计算
   直接代入公式：
   [ \text{address} = C_0 + \sum_{d=1}^D C_d \times i_d ]

3. 示例验证
   以输入数据中的$ONE$数组为例：

   • 声明：$ONE 1500 2 2 2 0 3 1 5$
     即维数D=2，元素大小size=2，各维范围：
     • 第1维：L₁=0, U₁=3
     • 第2维：L₂=1, U₂=5
   • 系数计算：
     • ( C_2 = \text{size} = 2 )
     • ( C_1 = C_2 \times (U_2 - L_2 + 1) = 2 \times (5-1+1) = 10 )
     • ( C_0 = 1500 - C_1L_1 - C_2L_2 = 1500 - 10 \times 0 - 2 \times 1 = 1498 )
   • 引用$ONE 2 4$的地址：
     [ 1498 + 10 \times 2 + 2 \times 4 = 1498 + 20 + 8 = 1526 ]
     与示例输出一致。

四、数据结构设计

• 结构体Array：存储数组的所有属性，包括名称、基地址、元素大小、维数、各维边界和系数
• getid函数：通过数组名快速查找对应结构体索引，时间复杂度O(n)
• 输入输出处理：按顺序读取数组定义和引用，确保格式正确

五、注意事项

1. 维度处理：
   数组维度从1开始编号，与公式中的d对应，避免索引越界。

2. 系数计算顺序：
   必须从最高维D开始递推计算低维系数

3. 输出格式：

   • 索引间用$,$分隔
   • 严格遵循$数组名[索引列表] = 地址$的格式

4. 边界条件：

   • 元素大小、维数等均为正整数
   • 题目保证输入合法，无需额外校验

六、复杂度分析

• 时间复杂度：

  • 数组定义处理：O(N×D)，N为数组数量，D为最大维数（≤10）
  • 引用处理：O(R×D)，R为引用数量
  • 总体复杂度：O((N+R)×D)，可高效处理题目数据范围。

• 空间复杂度：O(N×D)，用于存储数组参数和系数。

七、扩展思考

1. 多维数组地址映射原理：
   公式本质是将多维索引转换为线性地址，$C_d$表示第d维每个索引变化对应的字节偏移量。

2. 动态内存分配：
   若数组维数超过10，只需调整$L$和$N$常量即可扩展。

3. 错误处理：
   实际应用中可添加数组名不存在、索引越界等错误校验。