5

嗨，我正在做 Euler 项目中的 Collat​​z 序列问题（问题 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;
      }
   }

}
4

8 回答 8

8

您的问题不在于堆栈的大小（您已经记住了这些值），而在于

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

这应该就足够了:)

PS你会在很多项目欧拉问题中遇到对BigNums的需求......

于 2008-12-17T23:13:22.060 回答
2

如果您从整数更改为长整数，它将为您提供足够的空间来解决问题。这是我用来回答这个问题的代码：

    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 秒

于 2009-01-17T22:29:45.847 回答
1

旁注（似乎您实际上并不需要针对此问题进行尾调用优化）：尾调用优化在 Java 中不可用，据我所知，JVM 字节码甚至不支持它。这意味着任何深度递归都是不可能的，您必须重构它以使用其他循环构造。

于 2008-12-17T23:25:36.307 回答
1

如果您正在计算 Collat​​z 序列的大小，最多为 1,000,000，您应该重新考虑使用整数类型。我建议使用BigInteger或可能的long。

这应该可以缓解遇到的问题，但请注意，根据您的 JVM，您可能仍然会用完堆空间。

于 2008-12-18T17:52:19.833 回答
1

我认为你需要这两个提示：

  1. 不要使用 Integer，因为在某个起始数字处，序列会飞到一些大于 Integer.Max_VALUE 的数字，即 2147483647。请改用 Long。
  2. 尽量不要使用递归来解决这个问题，即使有记忆。正如我之前提到的，一些数字会飞得很高并产生大量堆栈，这将导致堆栈溢出。尝试使用“常规”迭代，例如 do-while 或 for。当然，您仍然可以在“常规”循环中使用一些成分，例如记忆。

哦，我忘记了什么。可能由于算术溢出而发生堆栈溢出。由于您使用整数，因此当算术溢出发生时，Java 可能会将这些“飞行数字”“更改”为负数。正如在方法 seqCount(int) 中所见，您不检查不变量 n > 0。

于 2010-08-26T13:12:50.080 回答
0

在这里你可以看看我对问题 14 的递归实现：

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

于 2013-01-16T08:00:10.560 回答
0

您不仅可以使用递归解决此问题，还可以使用单个循环来解决此问题。如果你写 int会有溢出。因为它在 chaning 时会产生很长的时间，并且递归永远不会结束，因为永远不会等于 1，并且您可能会遇到stackoverflow错误

这是我的循环和递归解决方案：

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));
    }
}
于 2010-12-17T05:49:50.357 回答
-1 
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
  }
于 2010-10-11T04:27:06.720 回答