?

Log in

No account? Create an account
nyaload

Журнал Пушыстого

Журнал Пушыстого

Previous Entry Share Flag Next Entry
zlib для оценки длины повторяющейся последовательности.
nyaload
_winnie
Вот эту задачу с projecteuler.net решал так:



import zlib
big = pow(10, 10000)

def ziplen(string):
    return len(zlib.compress(string))

_, n = max((ziplen(str(big / n)), n) for n in range(1, 1000+1))

print n



Объяснение: цикл в дроби 1/n - такой же, как и при делении нацело числа с большим количеством нулей на n.
Длину цикла мне считать лень, поэтому я возлагаю эту задачу на zlib: чем длинее цикл, тем хуже он сжимает строковое представление числа. Могло бы и не повезти -- 0.(11111111116) мог бы сжаться лучше чем 0.(1234567) --, но всё-таки ответ оказался правильным.


  • 1
красивое решение, пусть и не устойчивое!

Ага, интересное применение зипу. но multiplicative order даже в наивном варианте считается куда шустрее )

Я тут GDChan посмотрел -- какого фига этой энциклопедии нет в ЖЖ? У меня она тоже была!!!

О! У тебя есть профиль на МойКруг? Вроде ведь в Яндексе работал — должен быть.

  • 1