Блог

#c

#c

Вопрос:

 #include<stdio.h>
#include<conio.h>
#include<time.h>

long int A(int m, int n);

main() {
    int x;
    clock_t t1, t2, t;
    t1 = clock();
    x = A(2, 5);
    printf("the value of x is %dn", x);
    t2 = clock();
    t = (t2 - t1) / CLOCKS_PER_SEC;
    printf("decoding time =%dn", t);
    return 0;
}

int A(int m, int n) {
    if (n == 0) {
        return 1;
    }
    else if(m == 0) {
        return 2*n;
    }
    else  {
        return A(m - 1, A(m, n - 1));
    }
}
  

Комментарии:

1. Я не могу вспомнить название этого алгоритма, но вся его цель — продемонстрировать, что он не поддается вычислению даже с небольшими аргументами. То есть он специально разработан для переполнения стека.

2. Это выглядит довольно похоже на функцию Аккермана . Выполнение этого кода, вероятно, приведет к взрыву вашего стека даже с небольшими аргументами.

3. @user3386109: Функция явно вычислима. На самом деле, здесь приведен код для вычисления этого прямо здесь. («Вычислимый» имеет очень специфическое значение.)

4. @ReddyKowshikk Помимо ужасного форматирования… ну, вы объявили функцию A() как обе int и long int . Это не поможет. Вы также должны иметь int main() , а не только main() . Возможно, использование long long целых чисел для всех переменных помогло бы, но я полагаю, вы все равно столкнетесь с проблемами переполнения стека.

5. @KerrekSB Как я уже сказал, я не смог вспомнить название. Правильное утверждение заключается в том, что функция является примером «полностью вычислимой функции, которая не является примитивно рекурсивной». Так что да, вы правы. Однако ни один современный компьютер не может вычислить это, даже для небольших значений.

Ответ №1:

Комментарии:

1. Хотя я изменил размер стека на 4 МБ, результат тот же, программа не работает

2. @ReddyKowshikk попробуйте 8 МБ. Была ли это точно такая же программа, как в вопросе?`

3. Да, та же программа