Дано число. В двоичной записи 8*1024 бита.Есть ли какой то алгоритм, позволяющий быстро определить, что число делится на 10?

Любое число делится на 10 :)

http://ru.wikipedia.org/wiki/Признаки_делимости

(0) если ты имеешь ввиду результат=целое число. в одинэске прокатывает такая формул
Если (ТвоёЧисло/10)=Окр(ТвоёЧисло/10) Тогда
  //делится на 10
Конецесли:

(0) 10 - это 10 или 2?

(3) не смешно, если последнее число "0" в числе "1230", то на "0" делится. Не кажется ли тебе, что достать последний 0 из числа проще и быстрее чем делить на 0?

(+5) ...делить на 10

Если Число % 10 = 0

я что ли один понял, что число дано в двоичном виде?

в общем если надо делить на 2 (десятичное), то если последний знак будет 0, если 10 (десятичное), то наверно разбить на две подзадачи, проверить деление на 2 (десятичное) и на 5 (не знаю, если правило)

(8) а что такое 0 в двоичном коде?

(10) 0 это 0, а что с ним не так?

(10) http://planetcalc.ru/375/
520 1000001000
521 1000001001
522 1000001010 (не фурычит)))

Признак Паскаля — универсальный признак делимости, позволяющий для любых целых a и b определить, делится ли a на b. Точнее, он позволяет вывести почти все из выше приведённых признаков.

ПРИМЕР
Пусть дано число и найдем сумму всех тетрад::

00101011110001111100011000101000 => 2 + 11 + 12 + 7 + 12 + 6 + 2 + 8 = 60

Если полученная сумма кратна 10 - число делится на 10.
Можно это проверить на любом числе, меньше 10000.

Ха.. да если я захочу, то я и на ноль делить буду сколько не лень будет!

Половину чисел можешь делимостью на 2 отмести, остальные я бы честно делил.

(13) Доцент ты, а не цветочек.

(0) проверить, равен ли остаток от деления 0
Если МоеЧисло % 10 = 0 Тогда
// делится на 10
Иначе
// не делится на 10
КонецЕсли

(13)
10010001
тетрады 9 и 1
в сумме 10
однако исходное число, очевидно, на 10 не делится
чяднт?

(15) ты просто свел задачу к тому, как проверить, что число делится на пять

(17) походу последние 4 надо умножать так
берём из 00101011110001111100011000101000 1000 и умножаем
1*0+0*8+0*4+0*2=0 - делится

(19) не понял

:) мда...дожили..

(1) 0 не делится на 10, что ты с ним ни делай

(22) :) попался гуманитарий!
зы
любое число делится на любое число...просто иногда получаются неопределенности

Только на ноль поделить нельзя, но KRV говорит что может)

:) еще один...у них тут косяк!

(25) ну может он особенный :)

Блин, точно... Совсем уже....

(20) да, чего я прогнал, нашел признак для 16

нулевой коэфф всегда 1
второй 1*2 mod 10 == 2
третий 2*2 mod 10 == 4
четвёртый 4*2 mod 10 == 8
пятый 8*2 mod 10 == 6
шестой 6*2 mod 10 == 2 <- цикл
00101011110001111100011000101000
84268426842684268426842684268421
00208026840004268400042000208000 <- тут поциферное произведение первой строки на вторую
= 70 (это сумма всех цифр)

для твоего из (17)

10010001
84268421
80060001 = 15

Я уже нашел способ, почти как в 13 только правильнее так:
00101101111011111010
Первый бит справа очевидно должен быьть 0 иначе конец алгоритма и число не делится на 10.
Складываем сумму тетрад без первого бита
0001+0110+1111+0111+1101=1+6+15+7+13=42 (достаточно последней цифры 2)
и если эта сумма делится на пять, то все число делится на 10

(31) нет, неправильно, надо складывать триады и проверять деление на 5, плюс доп условие, последний бит = 0

из это следует из правила для пяти

там коэффциенты 1,2,4 в цикле, что фактически сумма триад

00101101111011111010

00+101+101+111+011+111+010=0+5+5+7+3+7+2=29 на пять не делится и остаток 4, хотя последний бит ноль

(31) тебе даже 42 mod 5 == 2 показывает, что это неправильно, т.к. реальный остаток равен 4

Переводить в десятичную еще не предлагали?

(35) строку из 1024 байт?

(24),(25) мой ноль! Хочу - делю, не хочу - не делю.. и вообще - мой ноль он, зараза, хитрый.. чему он чичаз равен я не знаю - как скажет, так и будет!

(34) 42=(двоично)=101010
разбиваем на тетрады без правого бита
101010=000101010=0001_0101_0
первая тетрада 1
вторая тетрада 5
5+1=6
т.е. на пять не делится, значит все число не делится на 10

(37) ?) покажи документы на ноль

(8) Вы путаете число и форму записи числа. Даже если Вы напишите римскими цифрами суть числа не измениться.

(34) остаток от деления на 10 то же легко найти.
сумма тетрад без правого бита делим на 5 получаем остаток. Остаток умножаем на 2 и прибавляем правый бит.
Для (38) это будет
(6 mod 5)*2+0=2

(40) я ничего не путаю, число записано в двоичном виде, надо по этому представлению определить делится оно на 10 или нет

(38) ты походу опять не понял, в (13) есть указание, что можно использовать Признак Паскаля
посмотреть в можешь вики, там пример для десятичной системы,
чтобы использовать для двоичной, надо во все формулы определения остатков вместо 10 подставить 2

я расписал тебе признак делимости для 10 и для 5, т.е. опеределил коэффициенты

10:
нулевой коэфф всегда 1
второй 1*2 mod 10 == 2
третий 2*2 mod 10 == 4
четвёртый 4*2 mod 10 == 8
пятый 8*2 mod 10 == 6
шестой 6*2 mod 10 == 2 <- цикл

5:
0й - 1
1й - 2
2й - 4
3й - 1 <- цикл

т.е. фактически для пяти получается, что признаком будет сложение триад

Все правильно, только не триад, а тетрад.
Пример число 26
В двоичной записи это 011010
В триадах это
011_010
т.е. 3 и 2. В сумме будет пять. Однако 26 на пять не делится
-------
А теперь правильно разбиваем на тетрады
00011010 в триадах это
0001_1010
т.е. 1 и 10, в сумме 11
Остаток от деления на пять 1, правильно
--------
Таким образом тепер получается следующий алгоритм. Двоичное число делится на 10 если сумма его тетрад делится на 5 и последний бит 0.

(44) не упорствуй, коэффициентов всего три 1,2,4, ну нет там коэффициента 8 для тетрады, хотя бы потому как 8 больше 5

(45) Объясни как определить твоим способом остаток от деления на пять числа 26 (011010)?

(46) да ты почти прав, я с коэффициентами ошибся, вернее с их количеством, но не это делает твой способ верным

5:
0й - 1
1й - 2
2й - 4
3й - 3
4й - 1 <- цикл

011010
268421=6+8+2=16 16 mod 5 == 1

00101011110001111100011000101000
34213421342134213421342134213421
00203021340004213400042000203000=5+6+11+11+7=40

если посмотреть на коэффициенты, то видно

3, 4, 2, 1 и если к 3 прибавить 5, которое на результат деления не повлияет, то получим
8, 4, 2, 1

(47) да я пока и не говорил, что именно делает мой способ верным. Посидел посчитал и пришел к такому способу. Ты посчитал по своему, вначале ошибся и я тебя поправил

(48) это не мой, это Паскаля ) там доказательство довольно простое, поэтому если не сходится, значит ошибся с коэффициентами

(0) двоичное число преобразуется в десятичное как
1*б1+2*б2+4*б3+8*б4+16*б5+32*б6+64*б7+... Если рассмотреть остаток от деления этого на 10, то получим:
1*б1+2*б2+4+б3+8*б4+6*б5+2*б6+4*б7+... (повторяются циклически коэффициенты 2, 4, 8, 6)
Ну и если получается большое число в сумме, то повторить алгоритм еще раз

(50) см (29)

(51) а... ну да

(52) ТС выбрал комби, признак на 5 (сложение тетрад со предпоследнего и бита и чётность последнего бита)

+(52) Только число 70 тоже разложить 70=
1000110
4268421
-------
4000420 = дает в сумме 10, т.е. делится на 70 ;-)
(53) Это, кстати, частный случай, т.е. коэффициенты становятся только в 2 раза меньше, в частности для 70=1000110 - отбрасываем последний бит=> 100011 и для него строим в цикле коэффициенты
100011
213421
------
200021 - сумма дает 5, т.е. 70 делится на 5 и за счет проверки последнего бита на равенство 0 = получаем что все число делится на 10

пока самый быстрый вариант поделить на 10

(55) строку из 0 и 1?

(55) смогешь быстро поделить двоичное: 101010101010101010101010101010101010101010101010101101011010101010101010101001010101001011101010110001111101101101000111001001001011101010111001100110

(54).2 если там строка, я думаю проще всё-таки складывать справа на лево коэффициенты 5 или 10, а от комби взять проверку последнего бита, для сокращения работы алгоритма при очевидном итоговом результате

в (57) при этом всего 150 знаков, в условии (0) в 54 раза больше

+(58) ну тупо
Если СимволСтроки = "1" Тогда
Сумма = Сумма + КоэффициентПоПорядку;
КонецЕсли;

+(60) а сам коэффициент определять из счетчика цикла

Если нацело,то в конце 0 , тут горе программеры делят его зачем-то ))))))

(62) ещё один провокатор )

(60) ну да, по очереди берешь коэффициент и прибавляешь, итоговая сумма не превысит 81920, что позволяет проверить и тупо делением.
(62) Двоичное число, для примера, я привел в (57). Проверь...

могу рассказать, как узнать делятся или на 5,2,3 и 9

вот горе от ума - перемудрили

(65) валяй

слишком длинно получилось, поделю в несколько строк:
Итак, (65) предлагаю сказать, делится ли на 10 число (в двоичной записи)
10101010101010101010101010101010101010101010101010110101101010
10101010101010010101010010111010101100011111011011010001110010
01001011101010111001100110

(66) система десятичная?

(53) я уже упростил, для деления на пять можно разбивать на триады даже с последним битом.

(68) двоичная

(70) я сегодня только с поллитровой работаю

(69) тетрады )

(72) да, оговорка. Конечно на тетрады

(56) про строки ничего сказано не было

(74) "Дано число. В двоичной записи 8*1024 бита"

(73) ну в общем то да, смещения вправо (деления на 2) не требуется

СтрокаБитов = "01100101"; // хз как ты её там получаешь
ДлинаБитов = СтрДлина(СтрокаБитов);
Сумма = 0;
Для НС = 0 По ДлинаБибов - 1 Цикл
СимволСтроки = Сред(СтрокаБитов, ДлинаБитов - НС, 1);
Если СимволСтроки = "1" Тогда
КоэффициентПоПорядку = Pow(2, НС % 4);
Сумма = Сумма + КоэффициентПоПорядку;
КонецЕсли;
КонецЦикла;

КоэффициентПоПорядку = Pow(2, НС % 4);
Сумма = Сумма + КоэффициентПоПорядку;

в одну строку

Сумма = Сумма + Pow(2, НС % 4);

(77) На самом деле все в моем частном случае проще у меня это число записано в шестнадцатеричной строке вида
0xffe3a578
Так что достаточно просто вычислять f+f+e+3+a+5+7+8

Кстати, суммой тетрад можно проверять делимость двоичного числа вообще на любое простое число (кроме 2 которое проверяется элементарно)

(80) почему именно тетрад?

(80) например возьмём 7

(80) а нет, гон.

(83) вот для 7 сумма триад

Надо чтобы в системе счисления основанной на этом простом числе возникала цикличность последнего знака, тогда и можно складывать куски размером с эту цикличность
для 7 - да, это триады
1-1
10-2
100-4
1000-1
10000-2

(85) а для 11 вообще 10 коэффициентов

+(86) ну т.е. максимально возможное

а цикличность возникает всегда, хотя бы потому, что число возможных цифр в последнем знаке конечна

таким образом двоичная система самая удобная для проверки на делимость

(88) конечно всегда, она ограничена Число - 1

+(90)* Делитель - 1

(42) Это же элементарно. Тип string. Состоит только из цифр. Последняя цифра ноль.
Проверку на цифры, проверку последнего символа.

(92) ты о чём?

(92) pardon. Не внимательно подумал.
(85) 2 в степени n  никогда не будет иметь последней цифрой 0. Поэтому этот метод негоден.

( ((n) & 1) == 0 && ((n) * 0xcccccccd) <= 0x33333333 )

(95)+ для 32 бит

(95) что это за условие, выполнимо только при n=0
Такая извращенная проверка на 0?

Чтобы число делилось на 10 без остатка необходимо и достаточно чтобы оно делилось без остатка на 2 и делилось без остатка на 5.
Проверить деление на 2 легко.
Вся проблема в том, чтобы проверить деление на 5. Трудность состоит в том, что 2^n никогда не будет равна 5^m

(98) Пока ты думал, мы уже на любое простое число делимость проверять научились

100 делится

(99) это не мы, а Паскаль, Гаусс и Эйлер ) Гаусс вообще первообразные корни забабахал )

(101) лично я, независимо от них это сделао сегодня

(97) & это побитовое И, && - логическое
первая проверка делимости на 2, вторая - на 5

(99) Где? Покажи как проверить делимость на 5. Я не нашел в ветке.

(104) в (77) уже в коде одноэса

(105) Там же простое преобразование в число. Это слишком просто и неинтересно ))

(104) Разбивать строку на куски по 4 бита и эти цифры сложить, если делится на 5 то все число делится на пять.

Пример
1000110110000100
разбиваем на
1000+1101+1000+0100

считаем
8+13+8+4=33 на 5 не делится, значит все число на 5 не делится

(103) Мне интересно, как Вы собрались реализовывать побитовое сравнение с символами строки.

(106) нет

(108) мапингом (по 1совски-соответствием)

(106) там не преобразование в число

(107) Это оптимизация (77) Блоки по четыре позволяют преобразовывать в шестнадцатиричную систему, блоки по три в восьмиричную и т.д.
Вижу отличие. И что, это работает?

(106) исходный признак делимости на 5 в (13) он там неверно назван признаком делимости на 10

(112) ага

причем для любого простого числа, только куски разной длины. Например для проверки на 7 надо разбивать на куски по три бита

(115) да нет, не так
смотри например для 11 надо не только на блоки по 10 бит разбивать, но и ещё и коэффициенты будут в таком порядке:
6 3 7 9 10 5 8 4 2 1

т.е. это остатки от деления степеней 2 на 11
2^9,...,2^0

но фактически можно просто эти остатки в цикле складывать

+(118) конечно, если коэффициент на знакоместе единицы

(119) не надо там никаких остатков. Число простое и коэффициенты не кратны, умножение на них на делимость не влияет

(120) коэффициенты это и есть остатки, а случай 5 просто исключительный, когда коэффициенты (остатки) это степени двойки, кроме 3, но его опять же по равенству остатка можно заменить на 8

+(121) а с 11 будет именно 10 коэффициентов, потому как 2 является первообразным корнем 11

(120) прикольно в (95) пофиг на всю последовательность, можно просто последний бит проверять, потом брать младшие 4 байта умножать на cccccccdh, брать от произведения младший байт и сравнивать его с 33333333h

(8) А в ПК все в двоичной форме. :)

Кто что пишет... Вы хоть у автора спросили, на каком языке программирования нужно это выразить :)

(107) Задумался, почему твой вариант работает... оказалось все просто, коэффициенты, которые мы рассчитали для битов, при проверке делимости на 5 (1,2,4,3):
10111001
34213421
------
30213001=10
80218001=20
В твоем же раскладе получается, что используются коэффициенты: 1,2,4,8=(3+5). Таким образом при добавлении 5 делимость на 5 не нарушается. И только по этому срабатывает.
(125) Придуманный алгоритм можно выразить на любом языке.

(126) надо было (47) прочитать )

(125) Да хоть на брейнфаке, мне это без разницы. Главное алгоритм

(128) алгоритм описан тут
wiki:Признак_Паскаля

(122)
Берем деление на 11 и разберем по признаку Паскаля
r1=2 mod 11 =2
r2= 4 mod 11 =4
r3= 8 mod 11 = 8
r4 = 16 mod 11 =5
r5 = 10 mod 11 = 10
r6 = 20 mod 11 = 9
r7= 18 mod 11 = 7
r8= 14 mod 11 = 3
r9= 6 mod 11 = 6
r10 = 12 mod 11 = 1 = r0

Следовательно для двоичного числа
А вида. ...а10 а9 а8 а7 а6 а5 а4 а3 а2 а1 а0

мы получаем что его делимость, это делимость на 11 числа
а0+a1*2+а2*4+...+a7*7+a8*3+a9*6+{a10+a11*2...}
но обратим внимание, что
а7*7 mod 11 = а7*(7+11*11) mod 11=а7*128 mod 11
и аналогично
а8*3 mod 11 = a8*(3+11*23) mod 11 = a8*256 mod 11

А это значит, что можно проверять на делимость на 11 такое выражение
a0+a1*2+a2*4+...+a7*128+a8*256+a9*512+{a10+a11*2...}

Отсюда видно, что мы можем просто брать куски по 10 битов, складывать их Без всяких коэффициентов. И не усложнять программу.

http://math.hashcode.ru/questions/9903/алгебра-признаки-делимости-в-двоичной-системе-счисления

(131) фигня
Делимость на 5 это суммы блоков по 4 бита делятся на 5
Делимость на 7 это суммы блоков по 3 бита делятся на 7
Делимость на 9 это суммы блоков по 6 бит делятся на 9

(130) а, так уже просто посчитал, тогда согласен без вопросов

Если МоеЧисло%10=0 Тогда
    Сообщить("Да");
Иначе
    Сообщить("Нет");
КонецЕсли;
//-----------------

Уже предлагали:

?

(135) ага, выдает неправильный результат в случае если
МоеЧисло = "1000001101001011011110101101010"

(130) теперь я понял, про что ты говорил, признаки делимости на число m (простое) в двоичной системе - это просто сложение n-битных конструкций, где 0<m<n-1

(136)Так разговор про двоичные числа?

(138) да

+(137) тьфу, где 0<n<m-1

да блин 0<n<m

Если Прав(Строка(ДвоичноеЧисло),4)="1010" Тогда
   Сообщить("Делится");
Иначе
   Сообщить("Не делится");
КонецЕсли;


Так пойдет?:-)

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

Для непростых то же самое, кстати, только блоки не с младшего бита могут начинаться и к ним придется по определенному закону еще хвост приделать

потому как остаток любого разряда k можно будет дополнить до 2^k, т.к. это остаток от 2^k mod m

(142) Ну конечно же нет, выдает неправильный результат при 11010 (число 26)

(143) кроме m вида 2^n

(146)А оно не делится чтобы без остатка

ааа...понял

(148) признак делимости на число m в двоичной системе - это просто сложение n-битных конструкций, где 0<n<m, кроме m вида 2^k

все числа конечно натуральные и больше 1

(149) Не всегда, иногда зацикливание в признаке может произойти с какого то момента на ноль. и Дальше всегда тогда будет ноль. Тогда достаточно проверить хвост в котором еще был не ноль. Это охватывает числа 2^k

(151) но можно точно сказать, что конструкция будет m-1 - битная для m, у которых 2 первообразный корень

вообще этот признак будет справедлив для любой системы счисления, просто для достаточно малых чисел не будет иметь смысла