Пушыстый (_winnie) wrote,
Пушыстый
_winnie

zlib для оценки длины повторяющейся последовательности.

Вот эту задачу с 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) --, но всё-таки ответ оказался правильным.
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 6 comments