Задача 4 из Проекта Эйлера: Поиск наибольшего палиндрома

Условие:

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

Решение и Объяснение

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

Шаг 1: Проверка на Палиндром Сначала создадим функцию, которая будет проверять, является ли число палиндромом. Число является палиндромом, если оно читается одинаково в обоих направлениях.

 

def is_palindrome(n):
    return str(n) == str(n)[::-1]

Эта функция преобразует число n в строку, а затем сравнивает её с её же перевёрнутой версией. Если они совпадают, число является палиндромом.

Шаг 2: Поиск Наибольшего Палиндрома Теперь нужно перебрать все возможные произведения трехзначных чисел и найти среди них наибольший палиндром.

def find_largest_palindrome():
    largest_palindrome = 0
    for i in range(100, 1000):
        for j in range(100, 1000):
            product = i * j
            if is_palindrome(product) and product > largest_palindrome:
                largest_palindrome = product
    return largest_palindrome

result = find_largest_palindrome()
print(f'Наибольший палиндром, полученный умножением двух трехзначных чисел: {result}')

В этом коде мы используем два вложенных цикла для перебора всех пар трехзначных чисел (от 100 до 999). Для каждой пары мы вычисляем произведение и проверяем, является ли оно палиндромом с помощью ранее созданной функции is_palindrome. Если текущее произведение является палиндромом и больше уже найденного наибольшего палиндрома, мы обновляем значение наибольшего палиндрома.

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

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

Дополнительное Решение Задачи из Проекта Эйлера

Оптимизация Решения

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

Идея оптимизации:

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

Реализация Оптимизированного Решения

def find_largest_palindrome_optimized():
    max_palindrome = 0
    a = 999
    while a >= 100:
        b = 999
        while b >= a:
            product = a * b
            if product <= max_palindrome:
                break  # Поскольку уменьшение b только снизит произведение
            if is_palindrome(product):
                max_palindrome = product
            b -= 1
        a -= 1
    return max_palindrome

result_optimized = find_largest_palindrome_optimized()
print(f'Оптимизированный поиск наибольшего палиндрома: {result_optimized}')

 

Объяснение Оптимизированного Решения

1. Внешний цикл (a от 999 до 100): Начинаем с самого большого трехзначного числа и уменьшаем его значение после каждой итерации.
2. Внутренний цикл (b от 999 до a): Это позволяет уменьшить количество проверок, так как b начинается с текущего значения a и уменьшается. Кроме того, если произведение a * b меньше уже найденного максимального палиндрома, мы прерываем внутренний цикл, так как дальнейшее уменьшение b только уменьшит произведение.
3. Проверка на палиндром и обновление максимального значения: Если текущее произведение является палиндромом и больше уже найденного, обновляем максимальное значение.

Этот оптимизированный метод сокращает количество необходимых проверок и увеличивает эффективность поиска максимального палиндрома.