(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]

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