1

我正在研究欧拉问题 14 ( http://projecteuler.net/problem=14 )。我试图通过一个贯穿 collat​​z 方程的方法来解决它，并返回所采取的步骤数。如果它高于它覆盖它的当前记录，否则它移动到下一个整数。它给出了堆栈溢出错误，所以我添加了 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!");
     }
    }
4

1 回答 1

0

我不会读你的代码。但我可以向您展示一个用伪代码编写的简单快捷的解决方案：

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

诀窍是计算并保存 collat​​z 链的长度值，从 1 开始；然后，如果未来序列下降到其起点以下，则计算停止以支持简单查找。这里的cs数组是缓存，k是当前正在计算的链的索引，是链中s的当前项，是链c的当前长度。计算euler14(1000000)应该不超过一两秒。

于 2013-10-09T18:46:27.787 回答