1

我正在尝试解决 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 );
    }
}

}
4

1 回答 1

0

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

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

于 2015-10-11T21:18:29.733 回答