powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Четверговый НАМ и сложение двоичных чисел в строках
25 сообщений из 107, страница 1 из 5
Четверговый НАМ и сложение двоичных чисел в строках
    #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
Четверговый НАМ и сложение двоичных чисел в строках
    #39963592
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Алгоритм: сложение в столбик
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39963597
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ммм... да. Код давай.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39963601
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Может вопрос-таки об умножении?
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39963604
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Давайте все таки начнем со сложения.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39963618
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Давайте все таки начнем со сложения.


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

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

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

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

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

Input:
1101+111

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

Далее. Здесь надо аккуратно. Надо выкинуть плюсик но только после того
как оба слагаемых сконверчены в лесенку из палочек.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39963685
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
тут наверное на ассемблере было бы прикольно напрограммировать с побитовыми операциями...
ну типа прописать в память 0 и 1
но я ассемблера не знаю :(
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39963692
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Этот топик - вообще не про Ассемблер.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #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
Четверговый НАМ и сложение двоичных чисел в строках
    #39963758
Swa111
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Забавная штука....

пример с хабра Нормальный алгоритм Маркова для деления чисел . Список замен немного изменен, так в этой машине символ | - служебный. Так что вместо него следует использовать #
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #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
Четверговый НАМ и сложение двоичных чисел в строках
    #39963846
Swa111
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Поправил интерпретатор, что бы символ "|" не выпадал из алфавита. Обычные пары разделяются последовательностью " -> ", терминальные пары последовательностью " |-> "
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39963851
Swa111
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
В интерпретатор добавлена проверка перекрытия правил
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39963859
Фотография crutchmaster
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,
Зачем нужно terminal rule я не понял.

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

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

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

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

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

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

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

https://rosettacode.org/wiki/Execute_a_Markov_algorithm

Я думаю что надо собрать 1 бинарничек на сях под Windows и выложить сюда чтоб желающие пользовались.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #39963886
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Swa111, ты гитхабом пользуешся? Ну я имею в виду.. Учетная запись там есть? Свои репозитарии?
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #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
Четверговый НАМ и сложение двоичных чисел в строках
    #39963898
Фотография crutchmaster
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

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

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


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

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

Код: sql
1.
| -> *



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

Мне символов не жалко.
...
Рейтинг: 0 / 0
Четверговый НАМ и сложение двоичных чисел в строках
    #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
Четверговый НАМ и сложение двоичных чисел в строках
    #39963919
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Мне символов не жалко.

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


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