У меня бесконечная петля

Question

Я практикую свою java, подсчитывая возможные пути достижения n кубиками. , и когда значение ввода n меньше, оно работает. , но когда i вводит значение n в 100, он получает бесконечное циклирование.

Могут ли ребята помочь мне?

вот мой код:

public static void main(String[] args) 
{ 
    testCode test = new testCode(); 

    System.out.println(test.countWays(100)); 
} 

private static int countWays(int n) 
    { 
     if(n<=1) 
     { 
      return 1; 
     } 
     else 
     { 
      System.out.println("counting ...."); 
      return countWays(n-6) + countWays(n-5) + countWays(n-4) + countWays(n-3) + countWays(n-2) + countWays(n-1); 
     } 
    } 

Answer 1

Ваша проблема похожа на Fibonnaci одно:

x0 = 0, x1 = 1, x(N) = x(N-2) + x(N-1) 

Если вам нужно сделать это с большими числами, вы должны использовать нерекурсивный метод:

static long countBis(int n) { 
     long fn, f1, f2, f3, f4, f5, f6; 
     int i; 
     f1=f2=f3=f4=f5=f6=fn = 1; 
     for (i = 2; i <= n; i++) { 
      f6 = f5;  
      f5 = f4;  
      f4 = f3; 
      f3 = f2; 
      f2 = f1; 
      f1 = fn; 
      fn = f6 + f5 + f4 + f3 + f2 + f1; 
     } 
     return fn; 
    } 

На каждой итерации вы просто вычисляете сумму прецедентных

Я проверил с n = 32 => с вашим он принял 8SEC, с этим потребовалось менее 1ски (я пробовал с n = 1000 => всегда 1 сек, но я не пробовал ваш ха-ха, после n = 35 это немного long ^^