Ackermann Table Generation

Question

Я работаю над тем, чтобы узнать больше о функциях Аккермана, времени рекурсии и функциональности в целом, однако мой код не будет компилироваться. У меня есть ощущение, что это как-то связано с массивами в 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";
        }
    }
}

Я знаю, что это не самый эффективный алгоритм Аккермана, но я просто использую его в качестве примера.

Ошибка компилятора:

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));

2) Ваше условие цикла написано неправильно:

   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.