00101011110001111100011000101000 => 2 + 11 + 12 + 7 + 12 + 6 + 2 + 8 = 60
Если полученная сумма кратна 15 - число делится на 15... Хочешь проверить исходное число?
| Версия для печати
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум на Исходниках.RU > Pascal > Делится ли двоичное число на 15 |
| Автор: denis-kasperovski 18.12.08, 13:44 |
| Кто может, подскажите ,плиз, разобраться: Число вводится своим двоичным представлением (длина числа не превышает 10000 двоичных разрядов). Необходимо определить делится ли число на 15. |
| Автор: MBo 18.12.08, 13:55 |
| 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 18.12.08, 13:55 |
| число делится на 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 18.12.08, 14:02 |
| Спасибо, значит будем копаться. |
| Автор: volvo877 18.12.08, 14:15 |
| denis-kasperovski, пробегаешь по всем тетрадам и находишь их сумму: 00101011110001111100011000101000 => 2 + 11 + 12 + 7 + 12 + 6 + 2 + 8 = 60 Если полученная сумма кратна 15 - число делится на 15... Хочешь проверить исходное число? |
| Автор: miksayer 18.12.08, 14:25 |
| volvo877, обоснуй, пожалуйста, свой метод я проверил для твоего примера, он работает, но мне кажется, что это просто совпадение. Имхо это должно работать только для двоично-десятичной с-мы Добавлено кстати, какой ажиотаж в этом разделе в канун сессии))) всем лабы сдавать надо))) |
| Автор: volvo877 18.12.08, 14:33 |
| miksayer, в десятичной системе счисления, что является признаком делимости на 9 (основание - 1), вспомни... А теперь перенеси это на 16-ричную с/с. |
| Автор: MBo 18.12.08, 14:34 |
| miksayer >мне кажется, что это просто совпадение нет, не совпадение, посмотри по моей ссылке - там для десятичной системы есть аналог (10^n-1), ссылка на признак Паскаля, и на книжку по делимости |
| Автор: denis-kasperovski 19.12.08, 07:13 |
| Огромное СПАСИБО!!! всем за помощь! Только вот не пойму: "длина числа не превышает 10000 двоичных разрядов" - значит, что данное двоичное число в десятичном виде не должно быть больше 10000?  |
| Автор: volvo877 19.12.08, 07:23 |
| denis-kasperovski, нет.... Это значит, что число в десятичном виде не должно быть больше 210000 - 1 (байт = 8 бит, какое максимальное десятичное число помещается в байт?) |
| Автор: denis-kasperovski 19.12.08, 07:25 |
| volvo877, тебя понял, сенк! |
| Автор: alextretyak 07.11.20, 02:00 |
| Можно проще: <{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}> n = input() res = 0 for bit in n: res = (res * 2 + int(bit)) % 15 # Если res == 0, то число `n` делится на 15 |