Ackermann Table Geneation

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, так как начинаются с нуля.