Гость
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Четверговый НАМ и сложение двоичных чисел в строках / 25 сообщений из 107, страница 1 из 5
28.05.2020, 18:29
    #39963532
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Четверговый НАМ и сложение двоичных чисел в строках
Привет Котаны-Бротаны! В уже сложившейся традиции четверговых-пятничных топиков я публикую логическую задачу-головоломку. Задача Написать алгоритм сложения двух двоичных чисел в нотации Нормальных Алгоритмов Маркова (НАМ) Input:
Код: sql
1.
2.

"1101+111"
Output code example:
Код: sql
1.
2.
3.
4.
5.

 ->
 ->
 ...
 |->
Output result example:
Код: sql
1.
2.

"10100"
Под катом я расскажу что такое НАМ своими словамиНормальные Алгоритмы Маркова (НАМ) - представляют собой совокупность правил (rules) вида:
Код: sql
1.
2.
3.

a -> b
x -> y
которые последовательно применяются к входящей строке до тех пор пока не будет достигнyто условие применения terminal rule ( |-> ). Применение - суть строковая замена. Выражение слева от стрелки заменятеся на правое. Пример алгоритма переводящего римскую цифру в десятичное число.
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.

IX -> 9
VIII -> 8
VII -> 7
VI -> 6
V -> 5
IV -> 4
III -> 3
II -> 2
I -> 1
|->
Еще некоторы дополнения. 1) За 1 раз выполняется только 1 строкова замена. 2) Если rule сработал - то возвращаемся к самому первому rule по списку. 3) Если левое выражение от стрелки - пустое - то это означает конкатенацию к голове результирующей строки. 4) Правое выражение пустое - просто удаляем подстроку. 5) Никаких if-else,for/do while не существует. Вот. Надеюсь нормально пояснил.
Что приветстуется:
  • Ваши любые рассуждения и решения как это сделать. Сам я сейчас - не знаю как решить эту задачу. Тоесть нахожусь в одинаковых условиях с вами.
  • Любые реализации машины Маркова. С++/браузерные и теоретические.
  • Новые задачи и головоломки после того как решим эту.
Не приветсвтуется:
    вопросы из серии "зачем это надо" игнорирование алгоритмов НАМ
Некоторые подсказки которые я сам для себя нашел Иногда полезно вводить в алфавит новый символ. Какую-то звездочку. Ее можно приклеивать к строкам как вагончик и использовать для поиска. А в конце - удалить. Пример программы которая передвигает букву 'a' в конец слова.
Код: sql
1.
2.
3.
4.

*ab -> b*a
* |-> 
-> *
Input: abbbbb Output: bbbbba (обратите внимание. терминальная стрелочка стоит на второй позиции. Это важно. Если ее не там поставить - мы получим зацикливание) Некоторый формализм я сознательно скипал. Алфавиты и символы. И поэтому в литературе терминальная стрелочка может рисоваться не так. Но нам пофиг.
Просто некоторые линки https://en.wikipedia.org/wiki/Markov_algorithm Здесь есть пример перевода двоички в унарный код
Вот так. Go-go думать! Об оптимизации - не думаем. Нужно любое работающее решение.
...
Рейтинг: 0 / 0
28.05.2020, 19:50
    #39963592
mini.weblab
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Четверговый НАМ и сложение двоичных чисел в строках
Алгоритм: сложение в столбик
...
Рейтинг: 0 / 0
28.05.2020, 19:53
    #39963597
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Четверговый НАМ и сложение двоичных чисел в строках
Ммм... да. Код давай.
...
Рейтинг: 0 / 0
28.05.2020, 20:02
    #39963601
exp98
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Четверговый НАМ и сложение двоичных чисел в строках
Может вопрос-таки об умножении?
...
Рейтинг: 0 / 0
28.05.2020, 20:11
    #39963604
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Четверговый НАМ и сложение двоичных чисел в строках
Давайте все таки начнем со сложения.
...
Рейтинг: 0 / 0
28.05.2020, 20:47
    #39963618
Aleksandr Sharahov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Четверговый НАМ и сложение двоичных чисел в строках
mayton
Давайте все таки начнем со сложения.


1. двоичный код - в палки (для обоих слагаемых)
2. убрать плюс
3. палки - в двоичный код
...
Рейтинг: 0 / 0
28.05.2020, 21:19
    #39963640
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Четверговый НАМ и сложение двоичных чисел в строках
+1

Одна процедура уже есть. Но мне кажется что обратная будет не так проста.
...
Рейтинг: 0 / 0
28.05.2020, 22:21
    #39963675
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Четверговый НАМ и сложение двоичных чисел в строках
Скопипащу с вики сюда. Что б было.

Конвертер с бинарного кода в унарный.

Rule|0 -> 0||1 -> 0|0 ->

Для нашего примера.

Input:
1101+111

Output:
|||||||||||||+|||||||

Далее. Здесь надо аккуратно. Надо выкинуть плюсик но только после того
как оба слагаемых сконверчены в лесенку из палочек.
...
Рейтинг: 0 / 0
28.05.2020, 22:35
    #39963685
mini.weblab
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Четверговый НАМ и сложение двоичных чисел в строках
тут наверное на ассемблере было бы прикольно напрограммировать с побитовыми операциями...
ну типа прописать в память 0 и 1
но я ассемблера не знаю :(
...
Рейтинг: 0 / 0
28.05.2020, 22:41
    #39963692
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Четверговый НАМ и сложение двоичных чисел в строках
Этот топик - вообще не про Ассемблер.
...
Рейтинг: 0 / 0
28.05.2020, 23:17
    #39963725
Swa111
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Четверговый НАМ и сложение двоичных чисел в строках
mayton,

Проверил на ограниченном наборе. Правила формирования файла rule.txt: Сначала идут тестовые образцы в формате
Тест -> Ожидаемый результат
Если ожидаемый результат начинается с @ то после него идет функция получения результата от левой части
Образцы собираются до строки <<rules>>, все оставшееся это правила.
комментарии в правилах как в VB, Пустые строки игнорируются.

запуск через run.bat

Код: vbnet
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
'Двигаем очередной знак вправо
*0= -> <*=0>
*1= -> <*=1>
0>0 -> 00>
0>1 -> 10>
1>0 -> 01>
1>1 -> 11>
'выполняем сложение
00>e -> $e0
01>e -> $e1
10>e -> $e1
11>e -> ~$e0

=1>e -> =$e1
=0>e -> =$e0

'Увеличиваем правую часть при переполнении
1~ -> ~0
0~ -> 1
=~ -> =1

'Сложение завершено идем за следующим знаком
1$ -> $1
0$ -> $0

'Забираем очередной знак
0<*=$ -> <*=0>
1<*=$ -> <*=1>
<*=$ -> 

'Двигаем символ конца расчетов
e1 -> 1e
e0 -> 0e
e+ -> @e

'Символ конца на месте, начинаем счет
@ -> <*=$

'правая часть больше левой 
<*=$ -> 

'Конец, терминальное правило так как строка заканчивается на |
e| -> 
'Затравка на первом проходе
 -> e
...
Рейтинг: 0 / 0
29.05.2020, 00:13
    #39963758
Swa111
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Четверговый НАМ и сложение двоичных чисел в строках
Забавная штука....

пример с хабра Нормальный алгоритм Маркова для деления чисел . Список замен немного изменен, так в этой машине символ | - служебный. Так что вместо него следует использовать #
...
Рейтинг: 0 / 0
29.05.2020, 01:30
    #39963797
mini.weblab
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Четверговый НАМ и сложение двоичных чисел в строках
1101+111 =
1000 + 100 + 100 + 10 + 1 + 1 =
1000 + 100 + 100 + 10 + 10 =
1000 + 100 + 100 + 100 =
1000 + 1000 + 100 =
10000 + 100 = 10100
...
Рейтинг: 0 / 0
29.05.2020, 07:10
    #39963846
Swa111
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Четверговый НАМ и сложение двоичных чисел в строках
Поправил интерпретатор, что бы символ "|" не выпадал из алфавита. Обычные пары разделяются последовательностью " -> ", терминальные пары последовательностью " |-> "
...
Рейтинг: 0 / 0
29.05.2020, 07:49
    #39963851
Swa111
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Четверговый НАМ и сложение двоичных чисел в строках
В интерпретатор добавлена проверка перекрытия правил
...
Рейтинг: 0 / 0
29.05.2020, 08:31
    #39963859
crutchmaster
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Четверговый НАМ и сложение двоичных чисел в строках
mayton,
Зачем нужно terminal rule я не понял.

mayton
Об оптимизации - не думаем. Нужно любое работающее решение.

Так это элементарно. Надо просто перебрать все суммы двоичных чисел в диапазоне байта в лоб.
...
Рейтинг: 0 / 0
29.05.2020, 08:48
    #39963863
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Четверговый НАМ и сложение двоичных чисел в строках
crutchmaster,

Ну... Я-же не создатель этого языка.

Terminal rule это чтото вроде условия выхода из рекурсии.

Часть алгоритмов без него обходятся. Ну и ладно.
...
Рейтинг: 0 / 0
29.05.2020, 08:59
    #39963864
crutchmaster
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Четверговый НАМ и сложение двоичных чисел в строках
mayton,

А, дошло. Если оно срабатывает или достигнут конец списка, то всё заканчивается.
...
Рейтинг: 0 / 0
29.05.2020, 10:04
    #39963883
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Четверговый НАМ и сложение двоичных чисел в строках
Swa111, спасибо. Посмотрю.

Но есть также онлайновые вычислители. Я находил несколько работающих в браузере.
И в Розетта-Код есть имплементации почти под все языки.

https://rosettacode.org/wiki/Execute_a_Markov_algorithm

Я думаю что надо собрать 1 бинарничек на сях под Windows и выложить сюда чтоб желающие пользовались.
...
Рейтинг: 0 / 0
29.05.2020, 10:06
    #39963886
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Четверговый НАМ и сложение двоичных чисел в строках
Swa111, ты гитхабом пользуешся? Ну я имею в виду.. Учетная запись там есть? Свои репозитарии?
...
Рейтинг: 0 / 0
29.05.2020, 10:17
    #39963893
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Четверговый НАМ и сложение двоичных чисел в строках
Щас я расскажу свою идею. Вобщем я сложение заменил на инкремент.

Поскольку НАМ очень удобно дебажить. Весь state программы укладывается в 1 строчку
я просто покажу как я думал это решать. Пока без кода а в виде модификаций строки.


Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
# Наша исходная строка

|||||||||||||+|||||||

# Выкидываем знак плюс. Теперь число засечек уже равно сумме как в древних счётах.

||||||||||||||||||||

# Теперь нам нужен двоичный регистр сумматора. Я завожу два символа ^$ и между ними будет накапливаться 
# наш счетчик 

^$||||||||||||||||||||

# Далее. Тривиальные кейсы. Палочка транформируется сразу в двоичную единичку

^1$|||||||||||||||||||

Rules:
^$| -> ^1$

# Далее 1+1 = 2 мы фиксируем переполнение. Но перенесем чуть позже.

Rules:
^$| -> ^1$
1$| -> 2$

# Теперь перенос 2 в десятичной = 10 в двоичной

Rules:
^$| -> ^1$
1$| -> 2$
^2 -> ^10  # Это самый старший разряд
02 -> 10 # Это если двойка попалась в середине
12 -> 100 # Это если двойка попалась в середине 



Вот. Я это написал в уме сегодня ночью. И еще не проверял. Наверное там где-то есть зацикливание.
...
Рейтинг: 0 / 0
29.05.2020, 10:20
    #39963898
crutchmaster
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Четверговый НАМ и сложение двоичных чисел в строках
mayton,

Мы сперва переводим бинарь в палочки, но как палочки перевести обратно в бинарь? Первый кусок кода его будет блокировать же.
...
Рейтинг: 0 / 0
29.05.2020, 10:23
    #39963900
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Четверговый НАМ и сложение двоичных чисел в строках
crutchmaster
mayton,

Мы сперва переводим бинарь в палочки, но как палочки перевести обратно в бинарь? Первый кусок кода его будет блокировать же.


Мммм.... чтоб рулы не пересекались - мы служебные символы можем ввести новые.

Например между первой и второй фазой делать

Код: sql
1.
| -> *



И дальше оперировать звездочками.

Мне символов не жалко.
...
Рейтинг: 0 / 0
29.05.2020, 10:32
    #39963903
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Четверговый НАМ и сложение двоичных чисел в строках
Swa111, у меня твой алгоритм не сработал на вот этом эмуляторе http://www.cmcmsu.info/1course/alg.schema.nam.htm

Правильно ли я скопипастил?

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
*0= -> <*=0>
*1= -> <*=1>
0>0 -> 00>
0>1 -> 10>
1>0 -> 01>
1>1 -> 11>
00>e -> $e0
01>e -> $e1
10>e -> $e1
11>e -> ~$e0
=1>e -> =$e1
=0>e -> =$e0
1~ -> ~0
0~ -> 1
=~ -> =1
1$ -> $1
0$ -> $0
0<*=$ -> <*=0>
1<*=$ -> <*=1>
<*=$ -> 
e1 -> 1e
e0 -> 0e
e+ -> @e
@ -> <*=$
<*=$ -> 
e |-> 
-> e



В пошаговом режиме пишет Ни одно правило не применено, либо выполнено терминальное правило.
...
Рейтинг: 0 / 0
29.05.2020, 10:47
    #39963919
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Четверговый НАМ и сложение двоичных чисел в строках
mayton
Мне символов не жалко.

Хотя да. Я думаю что Марков пожадничал. Надо было ввести в язык поняти стека и вызва процедуры или функции.
Но он наверное как и все теоретики просто что-то на бумаге хотел доказать. Типа равна ли эта хрень Машинке Тьюринга.
...
Рейтинг: 0 / 0
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Четверговый НАМ и сложение двоичных чисел в строках / 25 сообщений из 107, страница 1 из 5
Целевая тема:
Создать новую тему:
Автор:
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]