Улучшенное решение проблемы 4 от Project euler

В StackOverflow я нашел множество решений проблемы 4 в проекте Euler. Мой вопрос не в том, чтобы снова задать решение проблемы 4 из проекта Euler, который уже реализован в StackOverflow. Вместо этого я нашел улучшенное решение Улучшенное решение от ROMANIA_engineer. У меня два вопроса против улучшенного решения. В любом случае я опубликовал решение ниже, чтобы люди могли его изучить.

public static void main(String[] args) {

int max = -1;

for ( int i = 999 ; i >= 100 ; i--) {
    if ( max >= i*999 ) { 
        break;
    }
    for (int j = 999 ; j >= i ; j-- ) {             
        int p = i * j;
        if ( max < p && isPalindrome(p) ) {
            max = p;
        }
    }
}       
System.out.println(max > -1? max : "No palindrome found");
}

Вопросов

  1. Почему стоит условие (max> = i * 999)?. Чего мы добьемся, включив такую ​​недорогую операцию?

Из приведенного ниже фрагмента

for (int j = 999 ; j >= i ; j-- ) {             
        int p = i * j;
        if ( max < p && isPalindrome(p) ) {
            max = p;
        }
    }
  1. Вместо j >= 100 дается j >= i. Я вижу, что сэкономлено много времени, однако я хотел знать, что за этим стоит.

java algorithm palindrome
person James K J    schedule 19.02.2019    source источник
comment
Какой у Вас вопрос?   -  person Zephyr    schedule 19.02.2019
comment
Это больше математика, чем программирование.   -  person Pham Trung    schedule 19.02.2019

Ответы (1)


arrow_upward
1
arrow_downward

Чтобы ответить на вопрос 1, причина, по которой существует проверка (max >= i * 999), заключается в том, что вы, возможно, уже наткнулись на произведение двух трехзначных чисел, которое является палиндромом, но больше, чем i * 999. Поскольку внешний цикл for начинается с i = 999, после того, как вы нашли новый максимум, существует вероятность того, что новый максимум будет больше, чем максимально возможное произведение палиндрома из уменьшенного значения i в следующей итерации. Например, если мы нашли произведение палиндрома 926 * 998, где i = 926 и j = 998, и для этого продукта был установлен новый максимум. Обратите внимание, что это всего лишь гипотеза, я понятия не имею, является ли продукт палиндромом. Затем внутренний цикл for завершается на итерации i = 926. Затем на следующей итерации внешнего цикла for i теперь равно 925, а поскольку 925 * 999 меньше 926 * 998, нет необходимости продолжать поиск максимального палиндрома товар, потому что он уже был найден. Причина в том, что на данный момент 925 * 999 - это наибольший возможный продукт палиндрома, который можно рассчитать в будущем.

Чтобы ответить на вопрос 2, причина j >= i состоит в том, чтобы избежать повторения расчета продуктов. Например, предположим, что вместо этого условие было j >= 100. На первой итерации внутреннего цикла for, когда j равно 999, а i также равно 999. Мы закончим вычислением, возможно, произведений от 999 * 999, 999 * 998, вплоть до 999 * 100. Однако, если внутренний for цикл когда-либо достигается до точки, где i теперь равно 100, а j равно 999, тогда вы в конечном итоге повторите вычисление 100 * 999. Обратите внимание, что это всего лишь пример, он может даже не дойти до этой точки.

person Chris Gong    schedule 19.02.2019