Озадаченный проблемой палиндромного продукта

Question

Я изучал Ruby, поэтому я решил попробовать свои силы в некоторых головоломках проекта Эйлера.Смущающе, я только добрался до задачи 4 ...

Задача 4 выглядит следующим образом:

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

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

Таким образом, я решил, что я бы зациклился с 999 до 100 во вложенном цикле for и выполнил тест для палиндрома, а затем вырвался из циклов, когда нашел первый (который должен быть самым большим):

final=nil
range = 100...1000
for a in range.to_a.reverse do
  for b in range.to_a.reverse do
    c=a*b
    final=c if c.to_s == c.to_s.reverse
    break if !final.nil?
  end
  break if !final.nil?
end
puts final

Это выдает палиндром 580085, но, очевидно, это не самое высокое произведение двух трехзначных чисел в пределах диапазона.Как ни странно, тот же код успешно возвращает 9009, как в примере, если я изменю диапазон на 10 ... 100.

• Может кто-нибудь сказать мне, где я иду не так?
• Кроме того, есть ли лучший способ вырваться из внутреннего цикла?

Спасибо

Answer 1

Вот то, что я придумал в Ruby:

def largest_palindrome_product(digits)
  largest, upper, lower = 0, 10**digits - 1, 10**(digits - 1)

  for i in upper.downto(lower) do
    for j in i.downto(lower) do
      product = i * j
      largest = product if product > largest && palindrome?(product)
    end
  end
  largest
end

А вот функция для проверки, является ли число палиндромом:

def palindrome?(input)
  chars = input.to_s.chars
  for i in 0..(chars.size - 1) do
    return false if chars[i] != chars[chars.size - i - 1]
  end
  true
end

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

Answer 2

Главное - пройти все возможные значения. Не пытайтесь разбить, когда вы найдете первый ответ, просто начните с лучшего ответа нуля, затем попробуйте все комбинации и продолжайте обновлять лучше всего. Второстепенное - попытаться уменьшить набор «всех комбинаций».

Одна вещь, которую вы можете сделать, это ограничить ваш внутренний цикл значениями, меньшими или равными a (так как a b == b a). Это помещает большее значение вашего уравнения всегда в a и существенно сокращает количество значений, которые вы должны проверить.

for a in range.to_a.reverse do
    for b in (100..a).to_a.reverse do

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

c = a*b
next if c < best

Далее, если вы все равно будете проходить через них, нет смысла проходить их в обратном порядке. Начиная с верхней части диапазона, требуется некоторое время, прежде чем вы найдете палиндромное число, и в результате требуется некоторое время, чтобы уменьшить ваш поисковый набор. Если вы начинаете с нижней части, вы начинаете быстро увеличивать нижнюю границу.

for a in range.to_a do
    for b in (100..a).to_a do

Мои тесты показывают, что в любом случае вы пробуете несколько пар 405К. Так как насчет того, чтобы думать о проблеме по-другому. Каково наибольшее возможное произведение двух трехзначных чисел? 999 * 999 = 998001, а наименьшее - 100 * 100 = 10000. Как насчет того, чтобы мы взяли идею о том, что вы разбили первый ответ, но примените ее к другому диапазону, который будет 998001 до 10000 (или 999 * 999 до 100 * 100).

for c in (10000...998001).to_a.reverse do

Мы попадаем на палиндром только после 202 испытаний ... проблема в том, что он не состоит из двух трехзначных чисел. Итак, теперь мы должны проверить, является ли найденный нами палиндром произведением 2-х трехзначных чисел. Как только мы находим значение в диапазоне, который является палиндромом и произведением двух трехзначных чисел, мы готовы. Мои тесты показывают, что мы нашли самый высокий палиндром, который удовлетворяет требованиям после менее чем 93K тестов. Но поскольку нам приходится проверять, что все палиндромы к этому моменту являются продуктами двух трехзначных чисел, это может быть не более эффективным, чем в предыдущем решении.

Итак, вернемся к исходному улучшению.

for a in range.to_a.reverse do
    for b in (100..a).to_a.reverse do

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

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

Answer 3

реализация:

max = 100.upto(999).inject([-1,0,0]) do |m, a|
  a.upto(999) do |b|
    prod = a * b
    m = [prod, a, b] if prod.to_s == prod.to_s.reverse and prod > m[0]
  end
  m
end
puts "%d = %d * %d" % max

отпечатков 906609 = 913 * 993