Делится ли двоичное число на 15

[denis-kasperovski]

Кто может, подскажите ,плиз, разобраться:
Число вводится своим двоичным представлением (длина числа не превышает 10000 двоичных разрядов). Необходимо определить делится ли число на 15.

[MBo]

http://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%B8%D0%B7%D0%BD%D0%B0%D0%BA%D0%B8_%D0%B4%D0%B5%D0%BB%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D0%B8
найди аналог в десятичной системе и примени признак делимости.

[FasterHarder]

число делится на 15 тогда и только тогда, когда оно на цело делится на 3 и на 5.
Признак делимости двоичных чисел на 3 следующий: двоичное число делится на 3, если разность суммы цифр, стоящих на нечетных местах (начиная с крайней правой позиции), и суммы цифр, стоящих на четных местах, делится на 3. (из Интернета, возможно это не так).
Пусть дано двоичное число an…a3a2a1a0. Его можно представить как 2n • an + …+ 23 • a3 + 22 • a2 + 2 • a1 + a0 = (2n ± 1) • an ± an … + 9 • a3 – a3 + 3 • a2 + a2 + 3 • a1 – a1 + a0 = [(2n ± 1) • an …+ 9 • a3 + 3 • a2 + 3 • a1] (±an … – a3 + a2 – a1 + a0). Так как число, записанное в квадратных скобках, кратно трем, то заданное число делится на 3 только в случае, когда на 3 делится сумма, записанная в круглых скобках в конце выражения, т.е. в случае, соответствующем приведенному признаку.

не знаю, может поможет как нибудь при решении задачи.

[denis-kasperovski]

Спасибо, значит будем копаться.

[volvo877]

denis-kasperovski, пробегаешь по всем тетрадам и находишь их сумму:
00101011110001111100011000101000 => 2 + 11 + 12 + 7 + 12 + 6 + 2 + 8 = 60

Если полученная сумма кратна 15 - число делится на 15... Хочешь проверить исходное число?

[miksayer]

volvo877, обоснуй, пожалуйста, свой метод
я проверил для твоего примера, он работает, но мне кажется, что это просто совпадение. Имхо это должно работать только для двоично-десятичной с-мы

Добавлено 18.12.08, 14:26
кстати, какой ажиотаж в этом разделе в канун сессии))) всем лабы сдавать надо)))

[volvo877]

miksayer, в десятичной системе счисления, что является признаком делимости на 9 (основание - 1), вспомни... А теперь перенеси это на 16-ричную с/с.

[MBo]

miksayer
>мне кажется, что это просто совпадение
нет, не совпадение, посмотри по моей ссылке - там для десятичной системы есть аналог (10^n-1), ссылка на признак Паскаля, и на книжку по делимости

[denis-kasperovski]

Огромное СПАСИБО!!! всем за помощь!
Только вот не пойму: "длина числа не превышает 10000 двоичных разрядов" - значит, что данное двоичное число в десятичном виде не должно быть больше 10000?

[volvo877]

denis-kasperovski, нет.... Это значит, что число в десятичном виде не должно быть больше 2¹⁰⁰⁰⁰ - 1 (байт = 8 бит, какое максимальное десятичное число помещается в байт?)

[denis-kasperovski]

volvo877, тебя понял, сенк!

[alextretyak]

Цитата volvo877 @ 18.12.08, 14:15

пробегаешь по всем тетрадам и находишь их сумму

Можно проще:

n = input()
 
res = 0
for bit in n:
    res = (res * 2 + int(bit)) % 15
 
# Если res == 0, то число `n` делится на 15