Проект Эйлер 45

Question

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

Треугольник, пятиугольник и шестиугольник числа генерируются следующими формулы:

• Треугольник T_ (n) = n (n + 1) / 2 1, 3, 6, 10, 15, ...
• Пятиугольник P_ (n) = n (3n − 1) / 2 1, 5, 12, 22, 35, ...
• Шестиугольная H_ (n) = n (2n − 1) 1, 6, 15, 28, 45, ...

Можно проверить, что T_ (285) = P_ (165) = H_ (143) = 40755.

Найдите следующий номер треугольника, который также пятиугольные и шестиугольные.

Описание задачи.

Я знаю, что гексагональные числа являются подмножеством треугольных чисел, что означает, что вам нужно только найти число, где Hn = Pn. Но я не могу заставить свой код работать. Я знаю только язык Java, поэтому у меня проблемы с поиском решения в сети. В любом случае, надеюсь, кто-то может помочь. Вот мой код

public class NextNumber {

    public NextNumber() {
    next();
    }

    public void next() {


int n = 144;
int i = 165;
int p = i * (3 * i - 1) / 2;
int h = n * (2 * n - 1);
        while(p!=h) {
            n++;
           h = n * (2 * n - 1);

            if (h == p) {
                System.out.println("the next triangular number is" + h);
            } else {
                while (h > p) {
                    i++;
                    p = i * (3 * i - 1) / 2;
                }
                if (h == p) {
                    System.out.println("the next triangular number is" + h); break;
                    }
                 else if (p > h) {
                    System.out.println("bummer");
                }
            }

            }

    }
}

Я понимаю, что это, вероятно, очень медленный и неэффективный код, но на данный момент меня это не особо волнует. Меня интересует только поиск следующего числа, даже если это займет годы моего компьютера.

Answer 1

Мы знаем, что T ₂₈₅ = P ₁₆₅ = H ₁₄₃ = 40755. Мы начинаем с nt=286, np=166 и nh=144 иопределите соответствующие треугольные, пятиугольные и шестиугольные числа.Независимо от того, какое полученное число наименьшее, мы увеличиваем его значение n.Продолжайте делать это до тех пор, пока все числа не будут равны, и вы получите свой ответ.

Реализация этого алгоритма на Python выполняется на моем компьютере за 0,1 секунды.

Проблема с вашим кодом - переполнение.В то время как ответ помещается в 32-разрядный int, временные значения i * (3 * i - 1) переполняются до достижения ответа.Использование 64-битных long значений исправляет ваш код.

Answer 2

Другое решение, которое занимает 2 мс :

public class P45 {

    public static void main(String[] args) {
        long H = 0;
        long i = 144;
        while(true) {
            H = i*((i<<1)-1);
            if ( isPentagonal(H) && isTriangle(H) ) {
                break;
            }
            i++;
        }
        System.out.println(H);
    }

    private static boolean isPentagonal(long x) {
        double n = (1 + Math.sqrt(24*x+1)) / 6;
        return n == (long)n;
    }

    private static boolean isTriangle(long x) {
        double n = (-1 + Math.sqrt((x<<3)+1)) / 2;
        return n == (long)n;
    }

}

Улучшен

• Вы уже указали, что: шестиугольные числа являются числами треугольников, но я добавляю краткое доказательство: k*(2*k-1) можно записать в следующей форме i*(i+1)/2, если i = 2*k-1.
• В этом случае isTriangle можно удалить.
• Производительность будет аналогичной, потому что эта функция вызывается редко (вызывается только тогда, когда число было пятиугольным).

Answer 3

Ваш код выглядит так, как будто он даст правильный ответ довольно быстро. Цикл while можно упростить, если вы просто напечатаете результат после его завершения:

while (p != h) {
    n++;
    h = n * (2 * n - 1);
    while (h > p) {
        i++;
        p = i * ((3 * i - 1) / 2);
    }
}
System.out.println("the next triangular number is" + h);

Примечание: ваш внутренний цикл очень похож на внутренний цикл моего решения C ++. Это произвело желаемый ответ примерно за 0,002 секунды на моей машине.