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

+(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 первообразный корень

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