По окончаниям имеется ввиду: например, число Х заканчивается на 1, а число Y на 9, что даёт пару (1,9). Только четыре пары при умножении дадут число которое заканчивается на 9. И соответственно число итераций любого алгоритма сокращается вдвое.
И кстати даже если искомое число ниже, ничто нам не мешает для всех чисел которые дают сумму больше 900009, это правило применять. А для чисел которые дают сумму больше 800008, но меньше 900009 проверять только пары которые дают в сумме 8. И так до нуля.
ZZZ
>>Griffon написал:
>>Тут всё просто. (X - A) * (Y - B) всегда меньше чем (X - C) * Y, где С < A.
Хм… У меня это тоже проверяется.
Нет. Это не учитывается.
В приведённом тобой алгоритме учитывается только то, что не умножаются по два раза одни и те же числа. (например 999 * 998 и 998 * 999)
А это… вероятно я не совсем понятно написал. По идее просто (X - A) * (Y - B) всегда меньше чем X * Y.
Т.е. если мы находим полиндром со значениями X и Y, то в дальнейшем во втором цикле мы можем проверять не от 999 до 100, а от 999 до найденного Y.
Вышел сегодня на работу. Времени теперь много :)
Вот ещё такой алгоритм. Работает быстро. Без вероятности на ошибку. В отличии от алгоритмов перебора произведений, для полного перебора выполняет не (10 ** (2 * n)) / 2, а (10 ** (2 * n)) / 4.
Кроме того не требует полного прохода до конца.
def do1(l):
def full(x):
x = str(x)
return int(x+x[::-1])
max1 = int("9" * l)
first_max = int("9" * (l-1) + "7")
min1 = int("1" + "0" * (l-1))
c = 0
for i in range(first_max, min1, -1):
for j in range(max1, min1, -1):
f = full(i)
c += 1
test = f / j
if test > j:
break
if test.is_integer():
print(f, j, int(test), c)
return True
>> do(3)
906609 993 913 2251
И вот такой который требует не меньше, а столько же итераций для полного прохода, но так же не требует полного прохода.
При больших длинах сжирает порядка 30 - 40 мегабайт оперативной памяти. Правда код ужасный.
def do(start, end=0):
values = [start, start - 1]
max_list = [start**2, (start - 1)**2]
offsets = [0, 0]
i = 0
max_len = start - end
test = values[0]
c = 0
while i < max_len and test != 0:
c += 1
x = values[i]
y = x - offsets[i]
test = x * y
max_list[i] = test
max_val = max(max_list)
if test < max_val:
max_val_index = max_list.index(max_val)
if max_val_index == len(max_list) - 1:
values += [values[-1] - 1]
max_list += [values[-1]**2]
offsets += [0]
i = max_val_index
continue
offsets[i] += 1
test = str(test)
if test == test[::-1]:
print(test, x, y, c)
return True
>> do(999)
906609 993 913 4454
Мой алгоритм перебора (без каких либо допущений) выдавал 6159
Причём скорость выполнения первого алгоритма оказалась самой высокой.
Оба алгоритма можно ускорить за счёт описанных по ходу обсуждения темы методов как минимум в два раза.