конечный автомат для проверки делимости на 5 в двоичном коде

[Nerex]

Как построить конечный автомат для проверки делимости числа представленного в двоичном коде на 5.

[PAV]

Перемещено, заголовок сменен на информативный, дубль из CS удален.
Nerex, не нарушайте правила форума.

[Brukvalub]

Попробуйте использовать вот это:

\[ \begin{array}{l} 2^0 = 5 \cdot 0 + 1 \\ 2^1 = 5 \cdot 0 + 2 \\ 2^2 = 5 \cdot 1 - 1 \\ 2^3 = 5 \cdot 2 - 2 \\ 2^4 = 5 \cdot 3 + 1 \\ 2^5 = 5 \cdot 6 + 2 \\ 2^6 = 5 \cdot 13 - 1 \\ ............ \end{array} \]

[незваный гость]

Позвольте Вам посоветовать и иной путь, мне более понятный. Пусть у Вас есть число $\overline{a_1 a_2 a_3…a_k}$ Пусть его остаток от деления на $5$ равен $q$. Тогда остаток от деления на $5$ числа $\overline{a_1 a_2 a_3…a_k a_{k+1}}$ равен $2q + a_{k+1}$, не правда ли? Значит …

[Brukvalub]

незваный гость писал(а):

Позвольте Вам посоветовать и иной путь, мне более понятный.

Я всего лишь предлагал использовать указанную мной закономерность для обнаружения признака делимости на 5 в двоичной системе путем редукции числа к линейной комбинации его цифр с коэффициентами, равными последним слагаемым в столбцах выписанных мной соотношений. Такая редукция уменьшает модуль числа и за конечное число шагов позволяет найти остаток. Мне, в свою очередь, непонятны Ваши слова:

незваный гость писал(а):

Пусть у Вас есть число $\overline{a_1 a_2 a_3…a_k}$ Пусть его остаток от деления на $5$ равен $q$. Тогда остаток от деления на $5$ числа $\overline{a_1 a_2 a_3…a_k a_{k+1}}$ равен $2q + a_{k+1}$, не правда ли?

Я бы ответил: "не правда"! Например, если q=4 и $\ a_{k+1}}$=1 , то $2q + a_{k+1}$=9, а остаток не бывает больше 4

[незваный гость]

Brukvalub писал(а):

Я бы ответил: "не правда"!

И были бы правы! Только … я делал все операции по модулю пять, раз уж меня интересуют остатки.

Brukvalub писал(а):

Я всего лишь предлагал использовать указанную мной закономерность для обнаружения признака делимости на 5 в двоичной системе путем редукции числа к линейной комбинации его цифр с коэффициентами, равными последним слагаемым в столбцах выписанных мной соотношений.

Я не оспаривал Ваше предложение. Я лишь предложил иной путь, на мой взгляд, не менее пригодный для построения автомата. У него есть и то удобство, что он не требует признака делимости (которого я так и не знаю, хотя, конечно, могу построить).

Я предлагаю не соревноваться публично, пока Nerex не решит задачу. Споря друг с другом (если речь не идёт о корректности высказываний) мы лишь ему мешаем. Мы можем продолжить в ЛС.

[Батороев]

Brukvalub писал(а):

Я всего лишь предлагал использовать указанную мной закономерность для обнаружения признака делимости на 5 в двоичной системе путем редукции числа к линейной комбинации его цифр с коэффициентами, равными последним слагаемым в столбцах выписанных мной соотношений.

По-видимому, можно обойтись и без коэффициентов, если рассматривать сразу по два знака

[Echo-Off]

Позвольте предложить ещё один путь: если имеется число в двоичной системе, то раз плюнуть перевести это в 16-ричную систему. Дальше складываем цифры по модулю 5. Если получится 0, то делится, иначе нет.
Или можно у 16-ричного числа сложить все цифры не по модулю 5, у полученного числа опять сложить все цифры, у полученного опять итд. Если в конце концов получим 0, 5, A или F, то делится.
Например,
1) $10111101101000110010101_2 = 5ED195_{16},\ \ 5+E+D+1+9+5 = 2 (mod 5)$, не делится. Или $5+E+D+1+9+5=2F,\ \ 2+F=11,\ \ 1+1=2$, не делится.
2) $1010000001110101100101101111100_2=503ACB7C_{16}$,
$5+0+3+A+C+B+7+C=0(mod 5)$, или $5+0+3+A+C+B+7+C=3C,\ \ 3+C=F$, делится.

[Батороев]

А что в двоичной системе сложно складывать и вычитать по два знака (начиная с конца)?
$ 6020_{10} = 1011110000100_2 $
$ 00-01+00-10+11-01+01 = 0 $
Т.к. результат равен нулю, то значит число делится на 5.
Если полученный результат не равен нулю (имеет положительное или отрицательное значение) и имеет больше, чем два знака, то проверяем этот результат тем же методом, а если - не более двух знаков, то делаем вывод, что на 5 не делится.

[Echo-Off]

Точно.
В общем, те же признаки, что и в десятичной системе для 9 и 11
Не удивительно, в общем-то

[Батороев]

Если в еще более общем виде , то признаки делимости
на $ n $ чисел в $ (n+1)- $ и в $ (n-1)- $чных системах счисления (суммы и "суммо-разности" цифр соответственно).
В данном случае $ n = 5 $, $ n - 1 = 4 $.
Но т.к. $ 4 = 2^2 $, то в двоичной системе необходимо рассматривать по два знака.

Если был бы вопрос о делимости на 17 чисел в двоичной системе, то пришлось бы считать "суммо-разности" по 4 знака...

или перевести число в 16-ричную систему

[незваный гость]

Всем любителям признаков делимости: нарисовали бы вы автомат для, скажем, 23. Или 37… Нет, теоретически это можно. Если бумажка достаточного размера.

Мой сарказм к тому, что вопрос конкретен — построить автомат. А совсем не решить, делится ли число на 5.

Батороев писал(а):

Если в еще более общем виде , то признаки делимости на $ n $ чисел в $ (n+1)- $ и в $ (n-1)- $чных системах счисления (суммы и "суммо-разности" цифр соответственно).

Конечно. А для нечётного $n$ Вы всегда можете подобрать нужное количество битов.

Добавлено спустя 7 минут 9 секунд:

Между прочим, подход с остатками позволяет доказать: существует конечный автомат с не более чем $n$ вершинами и $d \cdot n$ дугами, который по $d$-ричной записи числа ответит на вопрос — дилится ли число на $n$.

[Nerex]

Люди.... АУ мне нужен граф или таблица конечного автомата, а не рассуждения как лучше делить число в двоичной системе на 5.

[Батороев]

Nerex писал(а):

Люди.... АУ мне нужен граф или таблица конечного автомата, а не рассуждения как лучше делить число в двоичной системе на 5.

SORRRRY!!!!!:oops:
Модераторы перевели тему из CS в данный раздел, и я подумал...
Еще раз, SORRRRY!!!

[незваный гость]

Nerex писал(а):

Люди.... АУ мне нужен граф или таблица конечного автомата, а не рассуждения как лучше делить число в двоичной системе на 5. Sad

Что Вам нужно, мы уяснили. Советы Вам дали. Что Вы теперь делаете? Ждёте, пока задачу за Вас решат?