Почему петля умирает? (Гипотеза Коллатца)

Я пытаюсь некоторые математические операции с Java, который проверяет число, если его (не) даже и изменить его, пока он достигает 1.

Я пытаюсь запустить цикл 999999 раз, кажется, он застрял примерно в 120000 раз. Ну, это не остановка с исключением, это просто ощущение, что компилятор застрял.

Я не очень хорошо разбираюсь в Java, может кто-нибудь объяснить мне, что здесь происходит?

public static void main(String[] args) {

    int n = 0;
    int highestNumber = 0;
    int highestCounter = 0;
    int counter = 0;
    for (int i = 2;i<1000000;i++) {

        if (i%10000==0) {
            System.out.println(i);
        }
        n = i;
        while (n!=1) {
            if (n%2==0) {   
                n = n/2;
            } else {    
                n=3*n+1;
            }
            counter++;
        }
        if (counter>highestCounter) {

            highestCounter = counter;
            highestNumber = i;
            System.out.println("HIGHEST "+highestNumber+" | counter = "+counter);   
        }
        counter = 0;
        n = 0;
    }
    System.out.println("final "+highestNumber);  
}
Источник

5 ответов

Решение

Вы переполнены, потому что 3 * n + 1 стал больше, чем Integer.MAX_VALUE, Так n становится отрицательным, и цикл while никогда не остановится.

использование long вместо int за n!

Если вы хотите проверить наличие переполнения:

while (n != 1) {
    if (n % 2 == 0) {
        n = n / 2;
    } else {
        if (n > (Integer.MAX_VALUE - 1) / 3) {
            throw new RuntimeException("overflow!");
        }
        n = 3 * n + 1;
    }
    counter++;
}

Дополнение для Java 8

Начиная с Java 8, Math класс предоставляет дополнительные статические методы для "точной" арифметики (сложение, вычитание, умножение, деление), которые бросают ArithmeticException в случае переполнения. Используя эти методы, код можно упростить:

while (n != 1) {
    if (n % 2 == 0) {
        n = n / 2;
    } else {
        n = Math.addExact(Math.multiplyExact(3, n), 1);
    }
    counter++;
}
Источник

У вас проблема переполнения. Измените код следующим образом, и вы увидите это:

    while (n!=1) {
        if(n < 0) throw new IllegalStateException("n should not become < 0" + n + "-" + counter);
        if(n > ((Integer.MAX_VALUE -1) / 3)) System.out.println("n too large. " + n);
        if (n%2==0) {   
            n = n/2;
        } else {    
            n=3*n+1;
        }
        counter++;
    }

если вы сделаете n к long это работает отлично.

Источник

Это исправление работает:

public static void main(String []args){
    long highestCounter = -1;
    long highestNumber = -1;
    for (long i = 2;i<1000000;i++) {

        if (i%1000==0) {
            System.out.println(i);
        }
        long n = i;
        long counter = 0;
        while (n!=1) {
            if (n%2==0) {   
                n = n/2;
            } else {    
                n=3*n+1;
            }
            counter++;
        }
        if (counter>highestCounter) {

            highestCounter = counter;
            highestNumber = i;
            System.out.println("HIGHEST "+highestNumber+" | counter = "+counter);   
        }
        counter = 0;
        n = 0;
    }
    System.out.println("final "+highestNumber); 
}
Источник

Хм, твой код выглядит нормально для меня. Вы решаете довольно типичную проблему

N является целым числом? Если это короткий, вы можете переполнить его.

Помимо этого, максимальное значение целого числа составляет более 2 миллиардов, так что вам не следует его нажимать. На всякий случай попробуйте установить n в long, чтобы увидеть, поможет ли это

Изменить: Возьмем, к примеру, число 77671 Согласно блогу, который я прочитал (читай: не проверено), наибольшее значение n для i = 77671 составляет 1 047 216 490

Так что я думаю, что п должен быть длинным, теперь, когда я думаю об этом больше

Источник

Вы просто запускаете бесконечный цикл внутри блока, добавьте System.out.println(counter); после counter++ чтобы увидеть, что происходит..

Источник
Другие вопросы по тегам