@DarCKoder

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

Добрый вечер.
Пытаюсь решить задачу.
Написал скрипт:
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();


Принцип работы алгоритма:
3e7a93fd2956494885f2e2b528c15a2c.jpg

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

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

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

Каким образом, можно начать производить умножение так, чтобы произведение записывалось в убывающем порядке?
  • Вопрос задан
  • 434 просмотра
Пригласить эксперта
Ответы на вопрос 1
@Dronablo
Oracle performance geek
Зачем вам вообще массив?
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
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы