Как написать функцию Аккермана итеративно? - PullRequest
Новая
       34

Как написать функцию Аккермана итеративно?

2 голосов
/ 05 марта 2020

Я написал рекурсивную версию функции Ackermann, и она работала правильно: 

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

Затем я попытался переписать код итеративно:

(я не знаю, как использовать 2D массив использует mallo c, поэтому вы можете почувствовать, что код грязный ...) 

int ackermann_i(int m, int n) {
    int* A = (int*) malloc((m+1) * (n+1) * sizeof(int));
    for(int i = 0; i <= m; i++) {
        for(int j = 0; j <= n; j++) {
            if(i == 0) {
                A[i*(n+1) + j] = j + 1;
            } else if(j == 0) {
                A[i*(n+1) + j] = A[(i-1)*(n+1) + 1];
            } else {
                A[i*(n+1) + j] = A[(i-1)*(n+1) + A[i*(n+1) + (j-1)]];
            }
        }
    }
    return A[m*(n+1) + n];
}

Но итерационная версия выдает неправильный ответ. Например: 

m: 3
n: 2
recursive: 29
iterative: 3

Почему мой итеративный код не работает?

1 Ответ

4 голосов
/ 05 марта 2020

Неопределенное поведение

К сожалению, ваш код показывает неопределенное поведение из-за доступа к неинициализированному значению и из-за пределов доступа. Самым простым тестом, демонстрирующим это поведение, является m = 1, n = 0. Это указывает только на две итерации внешнего l oop и одну итерацию внутреннего l oop и, следовательно, легче анализировать: 

int ackermann_i(int m, int n) {
    int* A = (int*) malloc((m+1) * (n+1) * sizeof(int));
    for(int i = 0; i <= m; i++) {
        for(int j = 0; j <= n; j++) {
            if(i == 0) {
                A[i*(n+1) + j] = j + 1;              //       (1)
            } else if(j == 0) {
                A[i*(n+1) + j] = A[(i-1)*(n+1) + 1]; //       (2)
            } else {
                A[i*(n+1) + j] = A[(i-1)*(n+1) + A[i*(n+1) + (j-1)]]; // (3)
            }
        }
    }
    return A[m*(n+1) + n];
}

Итак, давайте итерацию вручную:

  • i = 0, j = 0. Мы вводим (1) и устанавливаем A[0 + 0] = 1.
  • i = 1, j = 0. Мы вводим (2) и устанавливаем A[2 + 0] = A[0 + 1].
  • всегда есть по крайней мере j == 0, поэтому нас не волнует (3).

Но есть проблема: мы никогда не устанавливаем A[0 + 1]. Это значение может быть нулевым, оно может быть и другим случайным образом; возникает неопределенное поведение. Хуже того, наш A недостаточно велик: (m+1)*(n+1) здесь только 2, поэтому A[2] - это доступ к массиву вне границы.

Это указывает на две проблемы:

  • наша выделенная память недостаточно велика и, возможно, никогда не будет, поскольку внутренний член в a(m, a(m-1,n)) может вырасти намного больше, чем n.

  • , если бы у нас было решение для этого нам нужно сначала обработать тривиальные случаи, например, 

    for(int j = 0; j <= (n+1); ++j) {
    A[0 + j] = j + 1;          // set all A[i,j] where i = 0
}

Более глубокая проблема с алгоритмом

Однако есть еще одна более глубокая проблема. Ваш код подразумевает, что функция Аккермана может быть вычислена в θ (m * n). Это, однако, невозможно . Вместо этого вам нужен хотя бы стек или что-то подобное, которое может увеличиться в размере для вычисления результата. Эта реализация в Java дает некоторое вдохновение.

...