Project Euler (P14): проблемы рекурсии

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

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 во многих проблемах проекта Эйлера ...

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

Если вы считаете размер последовательности Коллатца для чисел до 1000000 вам следует пересмотреть использование типа Целое число. Я предлагаю использовать BigInteger или, возможно, длинный.

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

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

    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 секунд

Думаю, вам понадобятся эти 2 подсказки:

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

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

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
  }

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

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

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));
    }
}

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

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