Проект Эйлера (P14): проблемы рекурсии

Question

Привет, я занимаюсь проблемой последовательности Коллатца в проекте Эйлера (задача 14). Мой код работает с числами ниже 100000, но с большими числами я получаю ошибку переполнения стека.

Есть ли способ, которым я могу перефакторинг кода, чтобы использовать хвостовую рекурсию, или предотвратить переполнение стека. Код ниже:

import java.util.*;

public class v4
{

   // use a HashMap to store computed number, and chain size 

   static HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();

   public static void main(String[] args)
   {

      hm.put(1, 1);

      final int CEILING_MAX=Integer.parseInt(args[0]);
      int len=1;
      int max_count=1;
      int max_seed=1;

      for(int i=2; i<CEILING_MAX; i++)
      {
          len = seqCount(i);

          if(len > max_count)
          {
             max_count = len;
             max_seed = i;
          }
      }
      System.out.println(max_seed+"\t"+max_count);
   }

   // find the size of the hailstone sequence for N

   public static int seqCount(int n)
   {

      if(hm.get(n) != null)
      {
         return hm.get(n);
      }

      if(n ==1)
      {
         return 1;
      }
      else
      {
         int length = 1 + seqCount(nextSeq(n));
         hm.put(n, length);
         return length;
      }
   }

   // Find the next element in the sequence

   public static int nextSeq(int n)
   {

      if(n%2 == 0)
      {
         return n/2;
      }
      else
      {
         return n*3+1;
      }
   }

}

Answer 1

Ваша проблема не в размере стека (вы уже запоминаете значения), а в

1. размер некоторых чисел в последовательностях и
2. верхние пределы 32-разрядного целого числа.

Подсказка:

public static int seqCount(int n)
{
   if(hm.get(n) != null) {
       return hm.get(n);
   }
   if (n < 1) {
      // this should never happen, right? ;)
   } ...
   ...

Надеюсь, этого будет достаточно:)

P.S. вы столкнетесь с необходимостью BigNums во многих проблемах проекта Эйлера ...

Answer 2

Если вы измените значение с integer на long , это даст вам достаточно места для решения проблемы. Вот код, который я использовал для ответа на этот вопрос:

    for(int i=1;i<=1000000;i+=2)
    {
        steps=1;
        int n=i;
        long current=i;
        while(current!=1)
        {
            if(current%2==0)
            {
                current=current/2;
            }else{
                current=(current*3)+1;
            }
            steps++;
        }
        if(steps>best)
        {
            best=steps;
            answer=n;
        }
    }

Грубый форсинг, для запуска требуется около 9 секунд

Answer 3

Я думаю, вам нужны эти 2 подсказки:

1. Не используйте Integer, потому что при некотором начальном номере последовательность переместится в несколько чисел, превышающих Integer.Max_VALUE, равное 2147483647. Вместо этого используйте Long.
2. Старайтесь не использовать рекурсию для решения этой проблемы, даже с запоминанием. Как я упоминал ранее, некоторые числа будут лететь высоко и производить много стеков, что приведет к переполнению стека. Попробуйте использовать «обычную» итерацию, например, do-while или for. Конечно, вы все равно можете использовать некоторые ингредиенты, такие как запоминание, в «обычном» цикле.

О, я кое-что забыл. Возможно, переполнение стека происходит из-за арифметического переполнения. Поскольку вы используете Integer, возможно, Java «изменит» эти «летающие числа» на отрицательные числа, когда произойдет арифметическое переполнение. И, как видно из метода seqCount (int), вы не проверяете инвариант n> 0.

Answer 4

Если вы рассчитываете размер последовательности Коллатца для чисел до 1 000 000 Вы должны повторно рассмотреть использование типа Integer . Я предлагаю использовать BigInteger или, возможно, long .

Это должно облегчить возникшие проблемы, но имейте в виду, что в зависимости от вашей JVM у вас все еще может быть недостаточно места.

Answer 5

Дополнительное примечание (так как кажется, что для этой проблемы на самом деле не требуется оптимизация хвостового вызова): оптимизация хвостового вызова недоступна в Java, и, насколько я слышал, она даже не поддерживается байт-кодом JVM , Это означает, что любая глубокая рекурсия невозможна, и вы должны реорганизовать ее для использования какой-либо другой конструкции цикла.

Answer 6

Здесь вы можете взглянуть на мою рекурсивную реализацию задачи 14:

http://chmu.bplaced.net/?p=265

Answer 7

Вы можете решить эту проблему не только с помощью рекурсии, но и с помощью одного цикла. переполнение , если вы напишите int. потому что он генерирует долго во время изменения, и рекурсия никогда не заканчивается, потому что никогда не равна 1, и вы, вероятно, получите stackoverflow error

Вот мое решение с циклом и рекурсией:

public class Collatz {

    public int getChainLength(long i) {
        int count = 1;

        while (i != 1) {
            count++;

            if (i % 2 == 0) {
                i /= 2;
            } else {
                i = 3 * i + 1;
            }
        }

        return count;
    }

    public static int getChainLength(long i, int count) {
        if (i == 1) {
            return count;
        } else if (i % 2 == 0) {
            return getChainLength(i / 2, count + 1);
        } else {
            return getChainLength(3 * i + 1, count + 1);
        }
    }

    public int getLongestChain(int number) {
        int longestChain[] = { 0, 0 };

        for (int i = 1; i < number; i++) {
            int chain = getChainLength(i);

            if (longestChain[1] < chain) {
                longestChain[0] = i;
                longestChain[1] = chain;
            }
        }

        return longestChain[0];
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        System.out.println(new Collatz().getLongestChain(1000000));
    }
}

Answer 8

import java .util.*;
public class file 
  {
 public static void main(String [] args)
  {
   long largest=0;
   long number=0;
    for( long i=106239;i<1000000;i=i+2)
     {
      long k=1;
       long z=i;
      while(z!=1)
       {
        if(z%2==0)
        {
         k++;
         z=z/2;
        } else{
          k++;
          z=3*z+1;
           }
       }    
    if(k>largest)
      {
       number=i;
       largest=k;
       System.out.println(number+" "+largest);
      }
     }//for loop

   }//main
  }