Почему java-программа зависает на 113882?

Я написал Java-программу, которая находит длину цепочки чисел, используя последовательность коллатца. Последовательность Коллатца: если число четное, разделите его на два, если нечетное, умножьте на 3 и прибавьте единицу. Последовательность заканчивается, когда число достигает 1. Дополнительная информация о последовательности Коллатца. Моя программа находит длину цепочки чисел от 1 до 1 миллиона, но останавливается на 113382. Никакого сообщения об ошибке не выводится, программа просто перестает печатать числа.

*edit: Я проверил, и оказалось, что когда программа находится на 113383, цепочка сходится к отрицательным значениям. Кто-нибудь может это объяснить?

Я включил полный код, так как он очень короткий.

public static void main(String[] args) {
    int max =0, maxChain=0;
    for(int i = 2; i <1000000; i++ )
    {
        int c =i;
        int counter = 0;
        while(c != 1)
        {
            if(c%2 ==0) c/=2;
            else c= 3*c+1;
            counter++;
        }
        if(counter > maxChain)
        {
            maxChain =counter;
            max = i;
        }
        System.out.println(i);
    }
    System.out.println(max +" has a chain length of " +maxChain);

}

java freeze collatz
person A Parikh    schedule 27.01.2014    source источник
comment
бесконечный while цикл   -  person Baby    schedule 27.01.2014
comment
Если вы поместите оператор вывода в while, вы увидите, что он не зависает, он никогда не останавливается.   -  person ChiefTwoPencils    schedule 27.01.2014
comment
@BobbyDigital, тогда, если это так, почему он сходится к отрицательным значениям?   -  person A Parikh    schedule 27.01.2014
comment
Возможный дубликат Что такое отладчик и как это может помочь мне диагностировать проблемы   -  person Raedwald    schedule 29.01.2016

Ответы (1)


arrow_upward
6
arrow_downward

Для числа 113383 итерация №120 дает 827370449. Следующая итерация дает числовое значение 2482111348, которое слишком велико для переменной int, поэтому возникает арифметический переполнение, которое преобразуется в отрицательное число.

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

Однако, если вы измените тип переменной на long, вы избежите переполнения (во всяком случае, для этого начального числа), и последовательность завершится после 247 итераций.

Я, кстати, выяснил это, просто распечатав каждую итерацию, и сразу стало понятно, что произошло. Вы могли бы сделать то же самое и решить эту проблему самостоятельно. Отладка — такой же полезный навык, как и кодирование, потому что все мы сталкиваемся с ситуациями кодирования, которые нас удивляют, и поиск причины самостоятельно всегда приносит больше удовлетворения и запоминается (так что вы не попадете в ту же ловушку снова).

person Bohemian♦    schedule 27.01.2014
comment
Так что используйте long или BigInteger. - person Radiodef; 27.01.2014
comment
Спасибо Bohemian, я забыл о том, что максимальное значение превращается в минимальное значение в Java. Это объяснило бы отрицательные числа и бесконечный цикл. Я буду использовать BigInteger, потому что та же проблема может возникнуть с long когда-нибудь в будущем. - person A Parikh; 27.01.2014