Ackermann Table Geneation

Question

我正在学习更多关于Ackermann函数、递归时间和一般函数学的知识，但是，我的代码无法编译。我有一种感觉，这与acktgen()中的数组有关，但我不是100%确定。

#include <stdlib.h>
#include <iostream>
using namespace std;
int ack(int m, int n){
    if(m==0) return n+1;
    else if (n==0) return ack(m,1);
    else return ack(m-1,ack(m,n-1));
}
int acktgen(const int s, const int t){
    int acktable[s+1][t+1];
    for (int i = 1 ; i= t+1; ++i){ //column labels
        acktable[0][i]= i-1 ;
    }
    for (int i = 1 ; i= s+1; ++i){  //row labels
        acktable[i][0]= i-1 ;
    } 
    for (int i = 1; i<=s+1; ++i){
        for (int j = 1; j<=t+1; ++j){
            acktable[i][j]= ack(i-1,j-1);
        }
    }
    return(acktable);
}
int main(){
    for(int i=0;i<5;i++) {
        for(int j=0;j<5;j++) {
            cout<<acktgen(4,4)[i][j]<< "t";
        }
    }
}

我知道这不是最有效的Ackermann算法，但我只是用它作为一个例子。

编译错误:

prog.cpp: In function 'int acktgen(int, int)':
prog.cpp:26:17: error: invalid conversion from 'int (*)[(t + 1)]' to 'int' [-fpermissive]
  return(acktable);
                 ^
prog.cpp:14:6: warning: address of local variable 'acktable' returned [-Wreturn-local-addr]
  int acktable[s+1][t+1];
      ^
prog.cpp: In function 'int main()':
prog.cpp:32:24: error: invalid types 'int[int]' for array subscript
    cout<<acktgen(4,4)[i][j]<< "t";
                        ^

Answer 1

让我们来看看每个错误和警告:

> prog.cpp: In function 'int acktgen(int, int)': prog.cpp:26:17: error:
> invalid conversion from 'int (*)[(t + 1)]' to 'int' [-fpermissive]  
> return(acktable);

你声明你的acktgen函数返回一个int，但是你返回的是一个地址。我不知道你的意图是什么，但如果它是从数组中返回一个值，那么你返回那个值，即

return acktgen[0][4];

之类的

---

> prog.cpp:14:6: warning: address of local variable 'acktable' returned
> [-Wreturn-local-addr]   int acktable[s+1][t+1];

返回一个局部变量的地址。这样做在c++中是未定义的行为，所以不要这样做。当函数返回时，所有的局部变量都消失了。因此，试图返回(并使用)不存在的东西的地址是不会工作的(或者它可能工作，但只是偶然的)。

---

> prog.cpp: In function 'int main()': prog.cpp:32:24: error: invalid
> types 'int[int]' for array subscript
>     cout<<acktgen(4,4)[i][j]<< "t";

这是不正确的，因为acktgen返回int，而不是数组或类似数组的对象。

基本上你需要给我们更多关于你期望在acktgen函数中返回的信息。它真的应该是一个数组吗?它应该只是一个单一的值吗?

---

你的代码:

1)使用非常量表达式声明数组在ANSI中是不合法的c++:

int acktable[s+1][t+1];

那行代码不是合法的c++。要模拟数组，可以使用std::vector<std::vector<int>>:

std::vector<std::vector<int>> acktable(s+1, std::vector<int>(t+1));

你的循环条件写错了:

   for (int i = 1 ; i = t+1; ++i){ //column labels

看看中间的条件——这是你想要的吗，循环只在i == t+1时继续?之后你在循环中犯同样的错误。

第二，循环访问超出边界的数组。c++中的数组是基于0的，但是如果你仔细观察你的循环，你会发现你越过了一个边界:

    for (int i = 1; i<=s+1; ++i){
        for (int j = 1; j<=t+1; ++j){
            acktable[i][j]= ack(i-1,j-1);
        }
    }

最后一次迭代发生了什么?您访问acktable[s+1][t+1]，这是越界的。该数组的最高下标是s和t，因为我们从0开始计数。