(no subject)

[gns_ua]

> задача о разработке метода определения делимости числа на 15, при условии, что запись числа настолько длинная, что не влезает ни в один целочисленный тип (т.е., грубо говоря, делить напрямую нельзя).

http://smartsourcing.ru/blogs/kurilka/1364

Очевидно, что необходимо и достаточно выполнение двух условий:

а) последняя цифра 5 или 0

б) сумма цифр (aka X mod 9) делится на три. Свойста этой штуки таковы, что на самом деле полную сумму считать не нужно: достаточно складывать цифры по одной, и как только результат становится двузначным - останавливаться, делить на 9 с остатком, продолжать.

def mod9(n):
    sum = 0
    for x in n:
        sum+=int(x)
        if sum>20: sum = sum % 9
    return sum

# x задано как строка
if x[-1] in ('0', '5') and mod9(list(x)) % 3 == 0:
    print "yes'
else:
    print "no"

(вообще, порог 20 здесь произвольный. Можно и 100 взять - чтоб не слишком часто делить)

Comments

[tassadar-ha.livejournal.com]

Не масштабируемо. Для того, чтобы определить, делится ли число n на число k надо перевести n в систему счисления k и посмотреть значение последнего знака.

[gns-ua.livejournal.com]

Задача поставлено именно для 15, и я её решаю за O(log n) :). А какой у тебя есть алгоритм перевода заданного десятичной строкой длинного числа в произвольную систему счисления?

[tassadar-ha.livejournal.com]

Я для таких задач всегда предпочитал пользоваться внешними библиотеками мат. функций. Топорный алгоритм в виде деления на k работает очень медленно, а те как-то оперируют ими так, что время выполнения получается сильно меньше, если в том-таки Питоне проверять.

[gns-ua.livejournal.com]

А это не потому что там сишно-ассемблерно оптимизированный код? Мой алгоритм перепейсать на C, так тоже быстрей питоновского будет.

И тем более (в частном случае), быстрее даже однократного деления (а нам и нужен только остаток). И тем более для bignum.

[tassadar-ha.livejournal.com]

Не уверен, все трансляторы-компиляторы нынче отлично оптимизируют код (я рассказывал тебе пример про этот наш КПИ и Делфи?). Подозреваю, в библиотеках реализован какой-то более эффективный алгоритм перевода систем счисления, сравнительно с тупым делением.

[gns-ua.livejournal.com]

> Не уверен, все трансляторы-компиляторы нынче отлично оптимизируют код

На питоне может проверим?:)

Я тоже рассказывал, про ЗИЭИТ и дельфи/ассемблер :)

> Подозреваю, в библиотеках реализован какой-то более эффективный алгоритм перевода систем счисления, сравнительно с тупым делением.

Для частных случаев, возможно. Но я тут немного погуглил - говорят что до O(l log l) в лучшем случае, по сравнению с схемой Горнера O(l^2). Но нам нужен только собственно остаток от деления на первую степень, а его можно получить делением тупо в столбик (если у нас уже есть десятичная строка) - O(l), как и в моём варианте для частного случая, с точностью до коэффициента.

[tassadar-ha.livejournal.com]

Давай проверим, только, чур, без рекурсий - Питон, как ты знаешь, фигово с ними работает :)