Сегодня мы собираемся решить следующую задачу от сайта 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; }
- Преобразуйте число в массив символов. Например,
999
станет:["9", "9", "9"]
; - Получить длину массива;
- Прокрутите половину элементов массива;
- Если
i
-й элемент не равен t0len-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
. Сладкий! :)
Вывод
Это было быстрое решение для Крупнейшего палиндромного продукта. Я уверен, что есть способы улучшить его еще больше. Если вы нашли способ лучше, не стесняйтесь размещать его ниже в разделе комментариев.
Вы можете ознакомиться с некоторыми другими проблемами кодирования, которые у меня есть здесь.
Если вам понравился этот вызов и вы нашли его полезным, я был бы искренне признателен, если вы нажмете кнопку Рекомендовать 💚.