Каким образом, можно улучшить алгоритм поиска наибольшего числа палиндрома в произведении двух чисел?

Question

[Umid]

Добрый вечер.
Пытаюсь решить задачу.
Написал скрипт:

def isPolindrom(mystr):
	str_reverse = mystr[::-1]

	if str_reverse == mystr:
		# print(mystr)
		return True
	return False

def euler4():
	numbers = [ {
		"num": 99999,
		"i": 0
	} ]

	polindromHasFound = False
	polindroms = []

	while not polindromHasFound:
		nextNum = numbers[len(numbers) - 1]['num'] - 1

		for el in numbers:
			numForTest = el["num"] * (el["num"] - el["i"])
			if isPolindrom( str(numForTest) ):
				polindroms.insert( len(polindroms), numForTest )
			el["i"] += 1

		if len(polindroms) >= 100:
			print( polindroms )
			print( max(polindroms) )
		
			polindromHasFound = True

		if numbers[0]["i"] != 0:
			numbers.insert( len(numbers), {
				"num": nextNum,
				"i": 0
			} )

euler4();

Принцип работы алгоритма:


Каждая строка из картинки - это новая итерация цикла while.
Цикл for, находит произведение каждой ячейки, и проверяет её на палиндромность, если она такова, то число записывается в массив с остальными найденными палиндромами.

Цикл while, работает до тех пор, пока не наберётся 100 палиндромных чисел в массиве.
Т.к. в момент составления алгоритма я не учёл, что числа не будут идти по убыванию, к примеру, возьмите первую ячейка из 4 строки из картинки, и сравните её с первым значением пятой строки: 996*996 и 999*995. Вот здесь и была моя ошибка, поэтому взять только первый найденный палиндром не удастся( уже пробывал, выходит 888888, а на самом деле, самый большой палиндром - 906609).

И именно поэтому сделал сбор первых 100 палиндромных чисел, для того, чтобы отобрать из неё самый большой. Но, получается много не нужных вычислений, и есть вероятность, что алгоритм даст мне не самый большой палиндром при работе, к примеру, с двумя восьмизначными числами.

Каким образом, можно начать производить умножение так, чтобы произведение записывалось в убывающем порядке?

Answer 1

[Андрей]

Зачем вам вообще массив?

max_poly = 0
for i in range(100, 1000):
    for j in range(100, 1000):
        if i*j>max_poly and str(i*j) == str(i*j)[::-1]:
            max_poly = i*j
print(max_poly)

906609

Comments

[Sayonji]

for j in range(i, 1000):

[longclaps]

Sayonji: Андрей: Это дуболомское решение, O(N^2)
Вот получше:

def palindrome(n):
    """ максимальный палиндром длины n*2 """
    scale = 10 ** n
    for i in range(scale - 1, 0, -1):
        pq = i * scale + int(str(i)[::-1])
        for p in range(scale - 1, 0, -1):
            if p * p < pq:
                break
            if not pq % p:
                return pq

print(palindrome(3))
print(palindrome(6))

[Umid]

longclaps: scale = 10 ** n
А что делать в случае с трехзначным числом, 999, вы возведёте 10 в 999 степень?

[longclaps]

Umid: Обязательно )))

def palindrome(n):
    """ сомножители макс. палиндрома длины n """
    lim = 10 ** ((n + 1) // 2)
    for i in range(lim - 1, 0, -1):
        s = str(i)
        pq = int(s[:n // 2] + s[::-1])
        for p in range(int(pq ** .5) + 1, lim):
            if not pq % p:
                return p, pq // p

N = 16
for x in range(3, N):
    p, q = palindrome(x)
    print("{:>{}d} * {:>{}d} =={:>{}d}".format(
        p, N // 2, q, N // 2, p * q, N))