2016-09-10 6 views
0

Я пролежал много лет, но сегодня у меня есть вопрос относительно моего кода. В настоящее время я пытаюсь создать программу collatz, которая помещает количество шагов для определенного числа в массив, но в то же время ставит количество шагов для каждого отдельного номера, через который проходит. Вот мой код:Ошибка повторения ошибки Collatz

public class GenerousRecursion { 

    public static short steps; 
    public static int length; 
    public static short[] array = new short[101]; 

    public static void main(String[] args) { 
    length = 100; 
    for (int count = 2; count < length + 1; count++){ 
     steps = 0; 
     System.out.println(count + ": " + findCollatz(count)); 
    } 
    } 

    public static short findCollatz(int number) { 
    if (number < length){ 
     if (array[number] > 0) { 
     steps = array[number]++; return steps; 
     } 
     else if(number % 2 == 0) { 
     array[number] = findCollatz(number/2); 
     steps ++; 
     return steps; 
     } 
     else { 
     array[number] = findCollatz(3 * number + 1); 
     steps ++; 
     return steps; 
     } 
    } 

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

Вот большое видео на Коллатце гипотезе: Numberphile

Так вот ошибка броска (пониженный), но я не понимаю, потому что я не где-нибудь рядом с границы любого междунар или короткого замыкания:

Exception in thread "main" java.lang.StackOverflowError 
at GenerousRecursion.findCollatz(GenerousRecursion.java:22) 
at GenerousRecursion.findCollatz(GenerousRecursion.java:33) 
at GenerousRecursion.findCollatz(GenerousRecursion.java:27) 

Я просто перечислил эти первые три строки, потому что эти же три линии сделать ошибки для сотен строк.

В чем проблема и как ее исправить? Огромное спасибо!

Редактировать: Когда я запускал отладчик, моя программа непрерывно генерирует исключения, когда массив переопределяется.

+0

Отформатируйте свой код и отлаживайте код. – SMA

+0

'StackOverflowError' не имеет отношения к границам' int' или 'short'. Вы знакомы с концепцией стека? –

+0

@ Марко Топольник Я думал, что сделал, но, видимо, нет! Я был бы признателен за некоторые рекомендации, если вы не возражаете. – Erik

ответ

0

Как указано в видеоролике, продолжающемся с 1, закончится бесконечный цикл. Попробуйте следующее.

static int[] collatzCounts = new int[100]; 
static final int NO_COUNT = -1; 
static { 
    Arrays.fill(collatzCounts, NO_COUNT); 
    collatzCounts{1] = 0; // Define collatz(1) = 0 (1, 4, 2, 1, ...) 
} 

public static void main(String[] args) { 
    for (int n = 2; n < 120; n++) { 
     int steps = countCollatz(n); 
     System.out.println(n + ": " + steps); 
    } 
} 

public static int countCollatz(int n) { 
    IntFunction f = k -> 
      k % 2 == 0 
       ? 1 + countCollatz(k/2) 
       : 1 + countCollatz(3 * k + 1); 
       //: 2 + countCollatz((3 * k + 1)/2); 

    //if (n == 1) { 
    // return 0; 
    //} 
    if (n < collatzCounts.length) { 
     if (collatzCounts[n] == NO_COUNT) { 
      collatzCounts[n] = f.apply(n); 
     } 
     return collatzCounts[n]; 
    } else { 
     return f.apply(n); 
    } 
} 

countCollatz просто подсчитывает шаги, которые необходимы - для достижения 1 на самом деле. Хотя до дальнейшего доказательства может быть цикл более высоких чисел.

Я использовал выражение лямбда Java 8, функцию IntFunction f, поскольку более естественно повторять вычисление, один раз, чтобы заполнить массив, один раз для слишком больших чисел.