5

我用 C 语言编写了一个程序，它计算用户输入的 2 个非负整数的Ackermann值。程序检查整数是否为非负数，如果是，则计算它们的 Ackermann 值，然后请求新的输入或退出。该程序在 C 中运行良好，我对此没有任何问题。这是我的代码：

int ackermann(int m, int n){
        if (m == 0) return n + 1;
        if (n == 0) return ackermann(m - 1, 1);
        return ackermann(m - 1, ackermann(m, n - 1));
}

但是，事实上，为了大学课程的需要，我们使用了 C 的修改版本（基本相同，但有一些不同的语法规则），它模拟了 MIPS 汇编语言的语法和规则。更具体地说，我们使用寄存器来操作除数组和结构之外的所有数据。此外，我们不能使用 for、while 或 do-while 循环，我们使用if和goto而是声明。所以我用这种语言编写了以下程序（正如我所说的，它只不过是具有不同语法的 C）。我的问题是它仅适用于 (x,0) 和 (0,y) 用户输入（x 和 y 是非负数）。它不适用于 (4,1)、(3,2) 以及通常所有不为零的输入。我知道由于这些计算的大量堆栈，它不能有效地处理像 (10,10) 这样的非常大的数字。但我希望它适用于一些简单的输入，如 Ackermann(3,1) == 13。有关 Ackermann 函数的更多信息，请参阅：http ://en.wikipedia.org/wiki/Ackermann_function 这是我的代码：

//Registers --- The basic difference from C is that we use registers to manipulate data
int R0=0,R1,R2,R3,R4,R5,R6,R7,R8,R9,R10,R11,R12,R13,R14,R15,R16,R17,R18,R19,R20,R21,
R22,R23,R24,R25,R26,R27,R28,R29,R30,R31;

int ackermann(int m, int n){

    R4 = m;
    R5 = n;

    if(R4 != 0)
        goto outer_else;
    R6 = R5 + 1;
    return R6;

    outer_else:
        if(R5 != 0)
            goto inner_else;
        R7 = R4 - 1;
        R6 = ackermann(R7, 1);
        return R6;

        inner_else:
            R8 = R5 - 1;
            R9 = ackermann(R4, R8);
            R10 = R4 - 1;
            R6 = ackermann(R10, R9);
            return R6;
}
4

1 回答 1

6

我认为您的问题是这些寄存器值被定义为全局变量，并且它们正在通过对 的内部调用进行更新ackermann()，而外部调用取决于这些值不会改变。例如，看一下inner_else您的寄存器版本中的子句ackermann()：它调用ackermann(R4, R8)，并且在下一条语句中取决于 R4 的当前值，但递归调用在到达赋值语句之前改变了 R4 的设置。

两种常见的解决方案：

  1. 将您的寄存器定义为局部变量，并让编译器为您跟踪每个函数调用状态。

  2. 在进入您的ackermann()函数时，手动保存所有寄存器的状态，然后在退出时恢复相同状态。

尽管解决方案 1 更简单，但我怀疑您的老师可能更喜欢解决方案 2，因为它说明了编译器在其生成的汇编代码中处理实际寄存器管理所使用的技术。

于 2012-12-07T15:44:12.247 回答