UVa的3n + 1 - 为什么我的代码超过时间限制？

-1

考虑以下算法：

1.  input n 
    2.  if n = 1 then STOP 
    3.    if n is odd then n = 3n+1 
    4.    else n=n/2 
    5.  GOTO 2

鉴于输入22，数字的以下序列将被打印：

22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

据推测，上述算法将终止（当一个1打印）为任何积分输入值。尽管算法很简单，但是这个猜想是否属实却是未知数。然而，已经验证了对于所有整数n使得0 < n < 1,000,000（并且事实上，对于比这更多的数字）。给定输入n，可以确定打印的数量（包括1）。对于给定的n，这称为n的周期长度。在上例中，22的周期长度为16。对于任何两个数字i和j，您应确定在i和j之间的所有数字的最大周期长度。

Sample Input: 1 10 
Sample Output: 1 10 20

这是我的解决方案。

import java.io.IOException; 

public class Main{ 
    public static void main(String[]args) { 
     new N1().run(); 
    } 
    public static String readLine(int maxLength) { 
     byte[] bytes = new byte[maxLength]; 
     int length=0; 
     int input = 0; 
     while(length<maxLength) { 
      try { 
       input = System.in.read(); 
      } catch (IOException e) { 
       return null; 
      } 
      if(input=='\n') 
       break; 
      bytes[length] += input; 
      length++; 
     } 
     if(length==0) 
      return null; 
     return new String(bytes, 0, length); 
    } 
} 

class N1 implements Runnable { 

    @Override 
    public void run() { 
     String line = Main.readLine(100); 
     while(line!=null) { 
      solve(line); 
      line = Main.readLine(100); 
     } 
    } 
    private void solve(String input) { 
     String[] tokens = input.trim().split("\\s+"); 
     if(tokens.length!=2) 
      return; 
     int i=-1, j=-1; 
     try{ 
      i = Integer.parseInt(tokens[0]); 
      j = Integer.parseInt(tokens[1]); 
     }catch(Exception e) { 
      return; 
     } 
     if(i<=0||j<=0) 
      return; 
     int low, high; 
     low = (i<j) ? i :j; 
     high = i+j-low; 
     int max = -1; 
     for(int k=i;k<=j;k++) { 
      max = Math.max(max, CycleLength(k)); 
     } 
     System.out.println(i+" "+j+" "+max); 
     return; 
    } 
    private int CycleLength(int k) { 
     int length = 1; 
     long n = k; 
     while(n!=1) { 
      n = (n & 1)==0 ? n>>1 : n*3+1; 
      length++; 
     } 
     return length; 
    } 
}

以上是我对UVA 3n + 1问题的解决方案。我在笔记本电脑上使用此代码没有任何问题，并且响应很快。但是，判决是'超过时限' 有什么问题？

来源

2014-10-22 윤상진

为了在时间限制内工作，我猜你需要[记忆]（http://en.wikipedia.org/wiki/Memoization）值及其运行长度。 – msandiford 2014-10-22 04:43:18

您的run（）方法是一个无限循环，它调用readLine（）和readLine（）不检查文件结尾或输入结束。因此，即使在文件结尾或输入结束时，程序也试图读取另一行。所以它永远等待，时间耗尽。

来源

2014-10-22 08:03:43 Marichyasana

UVa的3n + 1 - 为什么我的代码超过时间限制？

回答

相关问题