DjangoBB LoFi version

Начало » Python для новичков » тестовые задачи

1 2 3 4 5

Griffon

Окт. 1, 2009 21:27:24

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

А делается только два допущения.
Первое - искомое число находится между девятками. То есть искомое число больше либо равно 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

Тут всё просто. (X - A) * (Y - B) всегда меньше чем (X - C) * Y, где С < A.
Таким образом, если мы нашли полиндром, нет необходимости постоянно уменьшать Y до ста.
ред… Ой. И ещё одно - если получено число X * Y меньше чем уже найденный полиндром, то уменьшая Y мы уже не найдём большего полиндрома. И соответственно в дальнейшем, опять же, не имеет смысла проверять Y меньше полученного (согласно выше описанному правилу).

Griffon

Окт. 1, 2009 22:10:46

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

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)
"""

0.190513249589
0.0583870296364
0.0315302643213

Sapphire

Окт. 2, 2009 00:38:28

Действительно полезная тема. Спасибо за Проект Эйлер, очень занятная штука :))
Раз уж тут такое обсуждение задач пошло, поделюсь своими впечатлениями о 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?

Заинтересовала задача. Я сумничал и перевернул последовательность в обратную сторону, то есть:
начало с 1
n -> (n-1)/3, если в результате получится нечётное число (кроме 1)
n -> 2*n, в любом случае
Тогда получается не последовательность, а дерево! И в это дерево включены все возможные по изначальным условиям задачи последовательности.
Тогда решение сводится к обходу дерева в поиске самой длинной ветви, при этом каждая ветвь кончается, когда следующее число превосходит миллион.
По-моему, красивое решение :)) Я его даже написал на пайтоне и вычислил результат. Но только потом я увидел примечание:

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

:(
Вот как определить такие ветви, которые, пройдя миллион, ещё вернутся назад - что-то нет идей.
И если вообще забыть об идее развернуть последовательность в обратную сторону, то что-то не могу придумать ничего кроме тупого перебора всех вариантов стартовых чисел от 2 до 999999. :\ А у вас есть идеи?

Griffon

Окт. 2, 2009 03:28:00

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

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 <- если от одного до другого не нашлось ни одного числа дающего больший список.
Но так как мы ищем числа близкие к миллиону логично предположить, что если мы имеем нечётное число выше половины миллиона которое даёт больший список чем все предыдущие, дальше чётные числа можно не проверять.

Таким образом можно добавить сразу после for:
if max_chain_value > half and not i % 2:
continue
Либо вообще исключить из поиска чётные числа.

Griffon

Окт. 2, 2009 03:46:40

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

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)

DeFoR

Окт. 2, 2009 04:52:18

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

1 решение в условии (в тексте задачи)
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

а) Нужно найти Палиндром - математически это понятие никак неопределено, а относится к символьной записи чего либо. И еще, Раз мне неизвестно математических взаимосвязей значит решаем перебором
б) of two 2-digit numbers is 9009 = 91 × 99. Find the largest palindrome

Значит можно смело предположить что максимльный палиндром будет числом вида 9……9
Это одно предположение.
И если оно непрокатит то можно всегда вернуться к тупому перебору.

Из этого следует простой алгоритм:
Перебераем пары чисел такие что:
1. произведение последующей пары меньше предыдущей
2. произведение должно оканчиваться на 9

В предыдущем решении 1 условие несовсем выполнялось, ну уж раз никто нехочет этого замечать
то выкладываю более правильный вариант по первому условию
ef gen1(num):
while num>0:
x= 2 if num%10 in (0,7,5,2) else 1
num-=x
yield num

def gen2(num1,num2):
tmp1=num2%10
tmp2=num2*2
d1={0:1,5:4,2:5,7:0,3:0,8:5}
d={9:2,1:8,7:10,3:10}
num2+=d1
while num1>num2:
num2+=d
yield num2 , tmp2-num2

num=0
N=9999999
for i in gen1(N):
for y,x in gen2(N,i):
tmp1=str(y*x)
num+=1
if tmp1==tmp1:
print tmp1, y, x, num
raise

906609 993 913 за 85
Но это тоже не идеал я надеюсь.

Griffon

Окт. 2, 2009 11:47:11

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

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

DeFoR

Окт. 2, 2009 12:25:53

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

Вот тут и самое интересное найти верный путь. Когда (X) * (Y) всегда больше (X-D) * (Y+D)
В моей программе поиск идет по диагонали Поэтому A==B
т.е. должно соблюдаться X-Y-D<0

pasaranax

Окт. 2, 2009 14:38:49

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

Sapphire

Окт. 2, 2009 16:05:38

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