Могу ли я сделать этот код про EulerProblem намного быстрее?

Question

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

Это проблема:

Пифагорейский триплет - это набор из трех натуральных чисел, a Например, 3 ^ 2 + 4 ^ 2 = 9 + 16 = 25 = 5 ^ 2.

Существует ровно один пифагорейский триплет, для которого a + b + c = 1000. Найти товар abc.

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

static int findTriplet(int getal)
{
    boolean test = false;
    for(int a = 1; !test; a++)
        for(int b = a+1; !test; b++)
            for(int c = b+1; !test; c++)
            {
                if( a*a + b*b == c*c)
                {
                    if(a+b+c == getal)
                    {
                        return (a*b*c);
                    }
                }

            }
    return 0;
}

Можно ли сделать код намного быстрее или это нормально, что это занимает часы?

С уважением,

EDIT:

Спасибо за помощь. Тест! Boolean был бесполезен, извините за это, Это работает:

static int findTriplet(int getal)
{
    for(int a = 1; a < 1000; a++)
        for(int b = a+1; b < 1000; b++)
            for(int c = b+1; c < 1000; c++)
            {
                if( a*a + b*b == c*c)
                {
                    if(a+b+c == getal)
                    {
                        return (a*b*c);
                    }
                }

            }
    return 0;
}

Я также написал вариант на Haskell, который тоже помогает.

Думаю, в Хаскеле это было проще и эффективнее.

Спасибо за советы.

Answer 1

Чтобы оптимизировать этот наивный алгоритм, вы должны сначала понять, что:

1. Ваш фактический исходный код вообще не останавливается.Он будет работать, пока проверка false.Вы также рискуете столкнуться с переполнением c.
2. Попытка каждой возможной комбинации a, b и c приведет к попытке 1000 * 999 * 988 = 997 002 000 раз (!).
3. Ключевыми моментами в этих алгоритмах являются:
   • условия остановки в циклах
   • способы поиска следующего, чтобы попробовать
   • способы уменьшения циклов, если это возможно

Теперь вы знаете, что вам необходимо:

1. найти способы избежать третьего цикла, используя условия ваших проблем
2. найдите способы увеличить a и b более умно, используя условия ваших проблем
3. найдите способы остановить циклы раньше, используя условия ваших проблем

Вот несколько советов для легкой оптимизации:

• Как сказал Амит и Сирко, вы можете угадать c , если вы уже знаете a и b .
• Вам не нужно пересчитывать a * a каждый раз, когда вы проверяете новый b
• Вам не нужно проверять, пока a <1000 и b <999, гораздо меньше возможных комбинаций </li>

И несколько советов для более сложной оптимизации:

• Вам не нужно каждый раз пересчитывать b * b
• Вам не нужно просматривать все возможные комбинации

Answer 2

Последнее for является избыточным, вы можете найти c = sqrt(a^2 + b^2), что сделает ваш алгоритм намного быстрее.

На самом деле вам нужно только проверить, есть ли c в N [натуральных числах], таких как sqrt(a^2 + b^2) = c, и проверить, если a+b+c == 1000

Эта опция сделает ваше решение O(n^2) вместо O(n^3), в 1000 раз быстрее!

РЕДАКТИРОВАТЬ: Как обсуждено в комментариях:

1. Может быть более быстрое решение, чем проверка c = sqrt(a^2 + b^2): c = 1000 - a -b, но важная часть делает это в O(n^2), а не O(n^3).
2. Этот ответ является скорее ориентиром, чем полным ответом. В условиях останова вашего цикла нужно проделать еще больше работы. Цель этого ответа состоит только в том, чтобы дать вам представление о том, как это можно сделать быстрее по величине.

Answer 3

Посмотрите на высокий, тонкий, прямоугольный треугольник с основанием a, высотой b и гипотенузой c. Сначала a и b всегда меньше, чем c и c = sqrt(a*a+b*b), так что, как говорили другие авторы, вам нужно искать только по a и b. Вы также знаете, что a+b >= c, поэтому нет смысла смотреть на маленькие пары a,b.

Теперь предположим, что вы начинаете с a=0, b=500, поэтому c==500, а общий периметр равен 1000. Теперь вы увеличиваете a на 1 и рассчитываете периметр. Это будет чуть больше 1000. Тогда вы уменьшите b на 1. Тогда периметр будет чуть меньше 1000. Затем увеличивайте a на 1, пока периметр не станет> 1000 снова.

Итак, пока периметр <= 1000, увеличьте <code>a. Пока это> 1000, уменьшите b. Если оно равно 1000, у вас есть один ответ. Тогда продолжай.

Вам нужно делать это только до тех пор, пока a<b.

Этот алгоритм должен быть O(N), потому что он не тратит время на маленькие пары.

Тогда все, что вам нужно сделать, это доказать себе, что он не пропустит ни одного ответа. Вы делаете это, предполагая, что есть правильный a,b ответ, который он пропускает, и показываете, что это невозможно.