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

[guitar15]

Всем привет. Возникла проблема поиска палиндрома произведения двух чисел (задание в низу).

Число-палиндром с обеих сторон (справа налево и слева направо) читается одинаково. Самое большое число-палиндром, полученное умножением двух двузначных чисел $\text{~---}$ $9009 = 91 \cdot 99$.
Найдите самый большой палиндром, полученный умножением двух трёхзначных чисел.

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

Используется синтаксис Python

s_list=[]
def num(i):
    k=1000
    while k>=100:
        k-=1
        s0=str(i*k)
        s=s0[::-1]
        if s0==s:
            s=int(s)
            s_list.append(s)
            return s_list
class palinom:
    def num(self):
        i=99
        while i<=1000:
            i+=1
            num(i)
        return num(i)
a=palinom()
print(max(a.num()))
 

В ответе я получаю $999999$, но это неправильно. В чем проблема?

[rockclimber]

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

[guryev]

Цикл

Используется синтаксис Python

        while i<=1000:
            i+=1
            num(i)
 

завершается при первом $\rm{i}>1000$, т.е., при $\rm{i}=1001$. После этого у вас снова вызывается функция $\rm{num}$ для этого $\rm{i}$:

Используется синтаксис Python

        return num(i)
 

которая, естественно, помещает в список $1001\cdot 999$ как палиндром. Он и выводится, поскольку самый большой.

Да, и внутри цикла тоже вызывается $\rm{num}(1001)$ - там же увеличение счётчика идёт перед вызовом функции.

[guitar15]

Все получилось. Пришлось переделать немного код.

Используется синтаксис Python

s_list=[]
def palinom():
    for i in range(100,1000):
        k=1000
        while k>=100:
            s=str(i*k)
            s0=s[::-1]
            k-=1
            if s0==s:
                s_list.append(int(s))
    return s_list
a=palinom()
print(max(a))


 

[Tookser]

(Оффтоп)

Есть некоторый смысл сделать перебор так:

Используется синтаксис Python

for i in range(100,1000):
    for j in range(100,1000):
        #здесь всё то, что в цикле

(Оффтоп)

Первое и второе числа играют одинаковую роль, и по ним можно идти совершенно одинаково. То есть можно сделать два почти одинаковых цикла for. Это довольно сильно улучшает читаемость кода.

И ещё - немного эффективнее будет хранить одно число - наибольший встреченный, на данный момент, палиндром, назовём его p. В самом начале сделать его равным 0, а дальше, каждый раз, когда в результате умножения получается палиндром, сравнивать его с p и если получился больше, присваивать p получившийся палиндром. Это позволит уменьшить расход памяти (в конце перебора будут храниться не все найденные палиндромы, а только один, самый большой). Хотя это изменение кода уже не так полезно, так как читаемость может ухудшиться.

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

[rockclimber]

Tookser
Желание сократить число перебираемых вариантов - это правильное желание. Все остальное, что у вас есть - неправильно
Во-первых, в задаче сказано про трехзначные числа, так что 1000 отпадает. 100 тоже можно откинуть, совершенно очевидно, что ничего толкового с сотней не выйдет. Хотя я не знаю питон, так что если конструкция for i in range(100,1000): означает перебор числел от 101 до 999 - то ок.
Во-вторых, мы ищем максимум. Поэтому начинать надо с 999 и идти вниз.
В-третьих, умножение коммутативно, поэтому цикл по j надо начинать не с 999, а с i.
Далее, когда найден хотя бы один палиндром (допустим, при значениях i1 и j1), не имеет смысла продолжать цикл по i до 101. Достаточно дойти до j1, все остальные произведения будут заведомо меньше.

-- 07.07.2017, 11:12 --

Кстати, есть способ еще круче, но немного менее очевидный.
Перебираем числа, начиная с 1998. Цикл выглядит примерно так (на паскале напишу, он довольно понятный, а питон я не знаю):

Используется синтаксис Pascal

s := 1998; p := 0; // p - искомое произведение
while p = 0 do
  begin
    i := 999;
    j := s - i;
    while (j <= i) and (p = 0) do
      begin
        if {i * j является палиндромом} then p := i * j;
        inc(j); // увеличение на единицу
        dec(i); // уменьшение на единицу
      end;
    dec(s);
  end;

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

[12d3]

Если пишем на питоне, то желание сократить код должно перевешивать желание сократить перебираемые варианты. =) Я вот за такое:

Используется синтаксис Python

from operator import mul
print max(x for x in map(mul,range(100,1000),range(100,1000)) if str(x)==str(x)[::-1])

[rockclimber]

Я для сокращения кода предпочитаю SQL. Длиннее, чем питон, но все равно сильно короче, чем паскаль. И отладка проще на порядок.

Используется синтаксис Oracle 11 SQL

WITH t AS (SELECT ROWNUM + 99 n FROM dual CONNECT BY LEVEL <= 900)
SELECT MAX(t1.n * t2.n)
  FROM t t1, t t2
 WHERE TO_CHAR(t1.n * t2.n) = REVERSE(TO_CHAR(t1.n * t2.n))

[arseniiv]

Зачиркано зачиркано

Скучный код без оптимизаций:

Используется синтаксис Haskell

ghci> let pal n = (let s = show n in s == reverse s) in maximum [k | i <- [100..1000-1], j <- [i..1000-1], let k = i * j, pal k]
906609

UPD. Вот дословная запись оптимизированного поиска rockclimber (жанр однострочников ужасен):

Используется синтаксис Haskell

ghci> let li s0 i0 = filter pal . map (uncurry (*)) . takeWhile (\(i, j) -> j <= i) $ zip [i0,i0-1..] [j0,j0+1..] where j0 = s0 - i0 in head $ concat [li s0 999 | s0 <- [1998,1998-1..]]
906609

UPD2. Ой, это не однострочник, pal используется (я его потом определил отдельно).