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 - 爲什麼我的代碼超過時間限制？

回答

相關問題