java - 用java解决3n+1

Question

我正在尝试解决java中的3n+1问题。 UVA 显示我的代码的运行时错误。我第一次尝试解决问题，但无法找出问题所在。我使用网站上给出的输入对其进行了测试，并且它有效。是否因为我的代码运行缓慢而被拒绝？如果是这样，如何优化？

PFB我的代码

import java.util.*;

class solution {


public static int[] clength = new int[1000000];

public static long nextnum(long n)
{

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

public static long cyclelength(long n)
{

    if(n==1)
    {
        return 1;

    }
    if (n < 1000000 && clength[(int)n] != 0)
    {
        return clength[(int)n];

    }
    long length= (1+ cyclelength(nextnum(n)));
    if (n < 1000000)
        clength[(int)n] = (int) length;

    return length;
}

public static void main(String[] args) throws Exception {
    // TODO Auto-generated method stub
    Scanner in = new Scanner(System.in);

    while(in.hasNext())
    {
        int a=in.nextInt();
        int b=in.nextInt();
        int min=Math.min(a, b);
        int max=Math.max(a, b);
        int count=0;

        for(int n=min;n<=max;n++)
        {
            count=(int) Math.max(count,cyclelength(n));

        }
        System.out.println(a + " " + b +" " +count );
    }
}

}

Answer 1

尽管问题陈述指出，在那些远大于 1,000,000 的未指定数字中，没有已知的数字使给定序列无法终止，但它没有讨论它们的循环长度是多少。我想你会发现有些数字确实有很长的周期长度。

虽然您似乎很好地利用了内存来避免冗余计算，但递归地构造计算会使您面临调用堆栈溢出的风险，这可能只需要几万的循环长度。此外，方法调用比简单分支要昂贵得多，因此您的递归方法也可能比迭代方法慢。