На прошлой неделе друг представил мне эту задачу из Project Euler, и мы рассмотрели ее базовое решение.
«Палиндромное число одинаково читается в обоих случаях. Самый большой палиндром, составленный из произведения двух двузначных чисел, равен 9009 = 91 × 99.
Найдите самый большой палиндром, составленный из произведения двух трехзначных чисел».
Мы начали с осознания того, что нам потребуются два отдельных метода: один для перебора возможных произведений двух трехзначных чисел, начиная с самого большого, а второй — для проверки того, является ли каждое произведение палиндромом.
Наш метод расчета продукта выглядел так:
def product_calculator product = 0 highest_product = 0 three_digit = [*100..999].reverse second_array = [*100..999].reverse three_digit.each do |num| second_array.each do |second_num| product = num*second_num if checkForPalindrome(product) highest_product = product end end end end highest_product end
Есть две вещи, которыми я горжусь, узнав об этом методе. Первый заключался в создании массива из 999–100, а второй, который мы поняли после некоторого неавтоматического тестирования, заключался в том, что нам на самом деле нужны оба цикла — что если бы мы использовали только один массив, это было бы просто 999*999, а затем 998 * 998 и т. д., и что самый большой палиндром на самом деле может быть 991 * 998 или что-то в этом роде. Итак, он работает за время O(n2) — n в квадрате, но, по крайней мере, он действительно работает!
Кроме того, использование двух точек/десятичных точек/эллипсов, например, 0..99, делает массив включающим оба конца. три точки будут до последнего числа, но не включая его.
Чтобы проверить, является ли число палиндромом, я создал массив и перебрал только его половину, сравнивая массив [0] с массивом [-1], массив [1] с массивом [-2] и т. д. позже понял, что стек будет более эффективным, поэтому я продемонстрирую способ его кодирования в следующем посте!
вот метод проверки палиндрома:
def check_for_palindrome(int) array = int.to_s.chars half = (array.length/2) looping_array = [*0..half] looping_array.each do |num| if !(array[num] == array[-1*(num+1)]) return false end end return true end
Когда я начал писать это на JavaScript, чтобы писать тесты (ждите следующего поста в блоге!), я понял, что перевод этого метода, который было легко закодировать на Ruby, будет проблемой, и что потребуется новая концепция.
Когда я обсудил это с другим другом, он предложил создать два массива, один с числами, записанными как обычно, а другой с числами, записанными наоборот, и сравнить их. Это казалось отличным планом, пока не стало ясно, что сравнение двух массивов никогда не вернет true, поскольку хранящие их переменные указывают на два разных места в памяти. Поэтому мы реализовали эту логику со строками:
function checkForPalindrome(number){ const forward = number.toString() const reverse = forward.split('').reverse().join('') return forward === reverse }
Какие красивые 4 строчки кода! Оставайтесь с нами, чтобы узнать, как это выглядит.