Сегодня мы собираемся решить следующую задачу от сайта Project Euler:

Самый большой палиндромный продукт

Палиндромное число одинаково читается в обоих направлениях. Самый большой палиндром, составленный из двух двузначных чисел, равен 9009 = 91 × 99.

Найдите самый большой палиндром, составленный из двух трехзначных чисел.

Я справляюсь с задачей быстрее, чем обычно, потому что мы уже решали некоторые задачи в прошлом и у нас больше опыта, не так ли? ;)

Во-первых, давайте создадим функцию, которая будет проверять, является ли число палиндромом:

function isPalindrome(x){
    x = x.toString().split('');         // (1)
    var len = x.length;                 // (2)
    for(var i=0; i<len/2;i++){          // (3)
        if(x[i] !== x[len-1-i]){        // (4)
            return false;
        }
    }
    return true;
}
  1. Преобразуйте число в массив символов. Например, 999 станет: ["9", "9", "9"];
  2. Получить длину массива;
  3. Прокрутите половину элементов массива;
  4. Если i-й элемент не равен t0 len-1-i-му элементу (последний минус i-й элемент), это означает, что число не является палиндромом, поэтому мы возвращаем false. В противном случае цикл продолжается, пока не завершится. Затем возвращаем true;

Примечание: эта функция также работает со строками и массивами!

Потрясающий! Теперь, когда у нас есть эта функция, мы можем перейти к следующему шагу, который перебирает все пары трехзначных чисел, умножает их и проверяет, является ли результат палиндромом.

Мы также собираемся сохранить в переменной самый большой палиндромный продукт, который у нас есть в определенный момент:

function isPalindrome(x){
    x = x.toString().split('');
    var len = x.length;
    for(var i=0; i<len/2;i++){
        if(x[i] !== x[len-1-i]){
            return false;
        }
    }
    return true;
}
function largestPalindrome(){
    var largest = 0;
    for(var i=999; i>=100; i--){
        for(var j=999; j>=100; j--){
            var mult = i*j;
            if(isPalindrome(mult) && mult > largest){
                largest = mult;
            }
        }
    }
    return largest;
}

Как видите, это довольно медленно. В целях тестирования я добавил счетчик, который увеличивается на каждой итерации второго цикла for, и получил результат: 810.000 итераций. Это ОГРОМНО!

Но мы можем улучшить его, выйдя из второго цикла, если произведение i и j меньше, чем largest палиндром, который у нас уже есть. Это потому, что, уменьшая j, мы никогда не получим большего числа.

function isPalindrome(x){
    x = x.toString().split('');
    var len = x.length;
    for(var i=0; i<len/2;i++){
        if(x[i] !== x[len-1-i]){
            return false;
        }
    }
    return true;
}
function largestPalindrome(){
    var largest = 0;
    for(var i=999; i>=100; i--){
        for(var j=999; j>=100; j--){
            var mult = i*j;
            if(mult < largest) break;
            if(isPalindrome(mult) && mult > largest){
                largest = mult;
            }
        }
    }
    return largest;
}

Этот простой if оператор уменьшил количество с 810.000 до 9201. Сладкий! :)

Вывод

Это было быстрое решение для Крупнейшего палиндромного продукта. Я уверен, что есть способы улучшить его еще больше. Если вы нашли способ лучше, не стесняйтесь размещать его ниже в разделе комментариев.

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

Если вам понравился этот вызов и вы нашли его полезным, я был бы искренне признателен, если вы нажмете кнопку Рекомендовать 💚.