Python-сообщество

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

А делается только два допущения.
Первое - искомое число находится между девятками. То есть искомое число больше либо равно 900 009. Очень сильно сокращает количество итераций ибо используются пары чисел (x,y) с соответствующими окончаниями (1,9) (3,3) (7,7) (9,1)

Второе - очень сомнительное и кривое. Проверки то нет.
Но у DeFoR'a допущений больше в последнем алгоритме.

А изначальный вариант выглядел вот так:

def get_max_polindrome(length=3):
    i1 = int("9" * length)
    count = 0
    max_polindrome = [0,0,0]
    min_val = 100
    for i in range(i1, 0, -1):
        for j in range(i, min_val, -1):
            test_val = i * j
            if test_val > max_polindrome[0]:
                if is_polindrome(test_val):
                    min_val = j
                    max_polindrome = [test_val, i, j]
                    break
            else:
                min_val = j
                break
        if i < min_val:
            break
    return max_polindrome

Отредактировано (Окт. 1, 2009 21:43:52)

Я думаю что при преобразовании в строку выполняются те же операции. Только быстрее.

func1 = """
def is_palindrome(n):
    digits = []
    while n > 0:
        n, o = divmod(n, 10)
        digits.insert(0, o)
    if len(digits) % 2 == 0:      
        l = digits[len(digits)//2:]
    else:
        l = digits[len(digits)//2 + 1:]
    l.reverse()
    return digits[:len(digits)//2] == l   
is_palindrome(123456)
is_palindrome(12345)
"""
func2 = """
def is_palindrome(ivalue):
    value = list(str(ivalue))
    reverse = value[:]
    reverse.reverse()
    return value == reverse
is_palindrome(123456)
is_palindrome(12345)
"""
func3 = """
def is_palindrome(ivalue):
    value = str(ivalue)
    return value == value[::-1]
is_palindrome(123456)
is_palindrome(12345)
"""

Действительно полезная тема. Спасибо за Проект Эйлер, очень занятная штука :))
Раз уж тут такое обсуждение задач пошло, поделюсь своими впечатлениями о 14й…

The following iterative sequence is defined for the set of positive integers:
n → n/2 (n is even)
n → 3n + 1 (n is odd)
Using the rule above and starting with 13, we generate the following sequence:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.
Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

Если банально перебором то:

def gen(x):
	while x > 1:
		if x % 2:
			x = x * 3 + 1
		else:
			x = x // 2
		yield x

max_chain_len = 0
max_chain_value = 0
for i in range(2, 10**6):
    c = len([x for x in gen(i)])
    if c > max_chain_len:
        max_chain_len = c
        max_chain_value = i
        
print(max_chain_len, max_chain_value)

Отредактировано (Окт. 2, 2009 03:29:26)

Или вот даже так

max_chain_len = 0
max_chain_value = 0
double_mcv = 0
for i in range(2, 10**6):
    if not i % 2 and i != double_mcv:
        continue
    c = len([None for x in gen(i)])
    if c > max_chain_len:
        max_chain_len = c
        max_chain_value = i
        double_mcv = i * 2

print(max_chain_len, max_chain_value)

Отредактировано (Окт. 2, 2009 03:51:25)

ZZZ
Griffon, код неправилен. Да, он работает, но переводить int в str… Давай математически.

Отредактировано (Окт. 2, 2009 10:28:13)

1. произведение последующей пары меньше предыдущей

Griffon

1. произведение последующей пары меньше предыдущей

Потому я и говорил о сомнительном и кривом допущении. Все алгоритмы не соблюдали это правило.
Ведь (X) * (Y) не всегда больше чем (X-A) * (Y+B). Где А и В произвольные числа.

На счет 14 проблемы. Чисто ради интереса построил диаграмму для самой длинной цепочки от числа меньше миллиона:

Griffon, по-моему все предположения насчёт того, что число должно быть близко к миллиону, или что число должно быть чётным/нечётным, носят лишь вероятностный характер. Чётность/нечётность и близость числа к миллиону ведь нисколько не говорит нам о том, какая последовательность чисел пойдёт после него.
А я тут подумал, что можно пройти по тому же самому дереву, которое я придумал, только начиная с ветвей) То есть по сути просто перебор, но когда встречается число, которое уже было, - прибавляем оставшуюся длину цепочки, и переходим к следующему стартовому числу. Правда для этого нужно будет хранить список пар “число - оставшаяся длина” для всех найденных чисел.

Отредактировано (Окт. 2, 2009 16:07:22)