Реализация функции Аккермана с помощью Java с поддержкой BigInteger - PullRequest
Новая
       48

Реализация функции Аккермана с помощью Java с поддержкой BigInteger

0 голосов
/ 12 июня 2019

Я получаю StackOverflowError (Исключение в потоке "main" java.lang.StackOverflowError) для следующего кода. Но программа прекрасно работает для m = 3, n = 3 (или других более низких значений), но не работает для m = 4 и n = 2 или 3. 

public class AckermannFunction
{
   static BigInteger One = BigInteger.ONE;

   static BigInteger Zero = BigInteger.ZERO;

   static BigInteger ackmnFun(BigInteger m, BigInteger n)
   {
      if (m.equals(Zero))
         return n.add(One);

      if (n.equals(Zero))
         return ackmnFun(m.subtract(One), One);

      return ackmnFun(m.subtract(One), ackmnFun(m, n.subtract(One)));
   }

   public static void main(String[] args)
   {
      BigInteger m = new BigInteger("4");
      BigInteger n = new BigInteger("3");

      System.out.println(ackmnFun(m, n));

   }
}

Я понимаю слишком много рекурсивных вызовов. Есть ли способ избавиться от этой ошибки?

Спасибо.

Ответы [ 2 ]

1 голос
/ 12 июня 2019

Вместо того чтобы делать это рекурсивно, вы можете рассматривать это как проблему динамического программирования и создавать таблицу значений снизу вверх. Тогда вместо того, чтобы делать рекурсивные вызовы, вы просто ссылаетесь на свою таблицу, чтобы создать следующую запись.

0 голосов
/ 19 июня 2019

Я нашел решение своего вопроса сам. Я хочу поделиться этим с вами.

Поскольку функция Аккермана вызывает себя много раз, даже для очень низкого значения m & n, то, что я сделал, я добавил еще несколько завершающих условий до m = 3 и n = 3 (чтобы минимизировать рекурсивные вызовы). И трюки сработали. Я нашел начальные значения, запустив исходную рекурсивную функцию, а затем добавил все это как условие завершения.

Программа находит Акерманна (4,2) через несколько секунд. Ответ очень длинный, содержит десятичные цифры 19729 года.

...