Project Euler p14, stackoverflowerror java (in bluej)

Question

我正在研究欧拉问题 14 (http://projecteuler.net/problem=14(。我试图通过一种方法来解决这个问题，该方法贯穿 collatz 方程，并返回所采取的步骤数。如果它更高，则当前记录会覆盖它，否则它会移动到下一个整数。它给出了堆栈溢出错误，所以我添加了 system.out.println 消息以尝试确定它停滞的位置，目前每当它达到 5200~时它就会死亡，我对为什么感到困惑，因为据我所知，此时遇到的值不应该超过 int 限制，即使我将"numberStorage"从 int 更改为 long，错误仍然存在。

这是我当前的代码：

/**
 * Write a description of class calculator here.
 * 
 * @author (your name) 
 * @version (a version number or a date)
 */
public class Calculator
{
    // instance variables - replace the example below with your own
    private int x;
    private int startingNumber = 1;
    private int stepCount;
    private int numberStorage;
    private int currentRecordStart;
    private int currentRecordSteps = 0;
    /**
     * a string and int value to track multiple starting numbers with the same number of steps
     */
    private String tieNote = "no ties";
    private int multiTie = 0;

    /**
     * Constructor for objects of class calculator
     */
    public Calculator()
    {
        x = 0;
    }
    /**
     * begins function
     */
    public void initiater()
    {
        numberStorage = 0;
        stepCount = 0;
        startingNumber = 1;
        currentRecordStart = 1;
        currentRecordSteps = 0;
        stepCount = 0;
        recordHolder(1,1);
    }
    /**
     * starts next rotation
     */
    public void steprunner()
    {
        ++startingNumber;
        System.out.println("starting rotation " + startingNumber + " current record " + currentRecordSteps);
        stepCount = 0;
        numberStorage = 0;
        recordHolder(startingNumber, collatzSequence(startingNumber));
    }
    /**
     * Runs collatz sequence and updates a variable with the number of steps.
     */
    public int collatzSequence(int N)
    {
        numberStorage = 0;
        numberStorage = N;
         if (N == 1)
         {
             return stepCount;
            }
         else if ( (N & 1) == 0)
         {
            numberStorage = numberStorage / 2;
            ++stepCount;
            return collatzSequence(numberStorage);
          }
          else if ( (N & 1) != 0)
          {
               numberStorage = 3 * numberStorage + 1;
               ++stepCount;
               numberStorage = numberStorage / 2;
               ++stepCount;
               return collatzSequence(numberStorage);
          }
        return stepCount;

    }
    /**
     * stores record and starts next cycle
     */
    public void recordHolder(int startingnumber, int stepcount)
     {
           if (startingNumber <= 999999)
          {
             if (stepcount > currentRecordSteps)
             {
                 currentRecordSteps = stepcount;
                 currentRecordStart = startingnumber;
                 tieNote = "no ties";
                 multiTie = 0;
                 System.out.println("a tie occured!");
                }
                else if (stepcount == currentRecordSteps)
                {
                    tieNote = ("starting number " + startingnumber + " also had " + stepcount + "steps");
                    ++multiTie;
                    System.out.println("a secondary tie occured!");
                }
             steprunner();
          }
          if (startingNumber == 999999)
          {
              simulationEnder();
            }
     }
    /**
     * ends simulation
     */
     public void simulationEnder()
     {
        System.out.println("the number with the highest number of steps was " + currentRecordStart + 
        " with " + currentRecordSteps + " steps!");
     }
    }

Answer 1

我不会阅读你的代码。但是我可以向您展示一个用伪代码编写的解决方案，它既简单又快速：

function euler14(n):
  cs := makeArray(1..n)
  maxX, maxLen, cs[1] := 1, 1, 1
  for k from 2 to n
    c, s := 0, k
    while k <= s
      if s % 2 == 0
        s := s / 2
      else
        s := 3 * s + 1
      c := c + 1
    cs[k] := cs[s] + c
    if maxLen < xs[k]
      maxX, maxLen := k, cs[k]
  return maxX

诀窍是按照从 1 开始的顺序计算并保存 collatz 链长度的值;然后，如果将来的序列下降到其起点以下，则计算停止，转而进行简单的查找。这里的cs数组是缓存，k是当前正在计算的链的索引，s是链中的当前项，c是链的当前长度。计算euler14(1000000)不应超过一两秒钟。