Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2 3 4 5   вперед  Ctrl      все
 Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
Привет Котаны-Бротаны!

В уже сложившейся традиции четверговых-пятничных топиков я публикую логическую
задачу-головоломку.

Задача

Написать алгоритм сложения двух двоичных чисел в нотации Нормальных Алгоритмов Маркова (НАМ)

Input:
"1101+111"


Output code example:
 ->
 ->
 ...
 |->


Output result example:
"10100"


+ Под катом я расскажу что такое НАМ своими словами
Нормальные Алгоритмы Маркова (НАМ) - представляют собой совокупность правил (rules)
вида:
a -> b
x -> y

которые последовательно применяются к входящей строке до тех пор пока не будет достигнyто условие
применения terminal rule ( |-> ). Применение - суть строковая замена. Выражение слева от стрелки заменятеся на правое.

Пример алгоритма переводящего римскую цифру в десятичное число.
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' в конец слова.
*ab -> b*a
* |-> 
-> *


Input: abbbbb

Output: bbbbba

(обратите внимание. терминальная стрелочка стоит на второй позиции. Это важно. Если ее не там
поставить - мы получим зацикливание)

Некоторый формализм я сознательно скипал. Алфавиты и символы. И поэтому в литературе терминальная
стрелочка может рисоваться не так. Но нам пофиг.

+ Просто некоторые линки
https://en.wikipedia.org/wiki/Markov_algorithm Здесь есть пример перевода двоички в унарный код


Вот так.

Go-go думать!

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

Сообщение было отредактировано: 29 май 20, 07:36
28 май 20, 18:29    [22141543]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках.  [new]
mini.weblab
Member

Откуда:
Сообщений: 1027
Алгоритм: сложение в столбик
28 май 20, 19:50    [22141617]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках.  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
Ммм... да. Код давай.
28 май 20, 19:53    [22141624]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках.  [new]
exp98
Member

Откуда:
Сообщений: 2446
Может вопрос-таки об умножении?
28 май 20, 20:02    [22141629]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках.  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
Давайте все таки начнем со сложения.
28 май 20, 20:11    [22141633]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках.  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
mayton
Давайте все таки начнем со сложения.


1. двоичный код - в палки (для обоих слагаемых)
2. убрать плюс
3. палки - в двоичный код
28 май 20, 20:47    [22141655]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
+1

Одна процедура уже есть. Но мне кажется что обратная будет не так проста.
28 май 20, 21:19    [22141681]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
Скопипащу с вики сюда. Что б было.

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

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


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

Input:
1101+111

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

Далее. Здесь надо аккуратно. Надо выкинуть плюсик но только после того
как оба слагаемых сконверчены в лесенку из палочек.
28 май 20, 22:21    [22141727]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mini.weblab
Member

Откуда:
Сообщений: 1027
тут наверное на ассемблере было бы прикольно напрограммировать с побитовыми операциями...
ну типа прописать в память 0 и 1
но я ассемблера не знаю :(

Сообщение было отредактировано: 28 май 20, 22:35
28 май 20, 22:35    [22141743]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
Этот топик - вообще не про Ассемблер.
28 май 20, 22:41    [22141753]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Swa111
Member

Откуда:
Сообщений: 202
mayton,

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

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

'Двигаем очередной знак вправо
*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


К сообщению приложен файл (nam.zip - 1Kb) cкачать
28 май 20, 23:17    [22141808]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Swa111
Member

Откуда:
Сообщений: 202
Забавная штука....

пример с хабра Нормальный алгоритм Маркова для деления чисел . Список замен немного изменен, так в этой машине символ | - служебный. Так что вместо него следует использовать #

К сообщению приложен файл (Rule.txt - 1Kb) cкачать
29 май 20, 00:13    [22141855]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mini.weblab
Member

Откуда:
Сообщений: 1027
1101+111 =
1000 + 100 + 100 + 10 + 1 + 1 =
1000 + 100 + 100 + 10 + 10 =
1000 + 100 + 100 + 100 =
1000 + 1000 + 100 =
10000 + 100 = 10100
29 май 20, 01:30    [22141904]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Swa111
Member

Откуда:
Сообщений: 202
Поправил интерпретатор, что бы символ "|" не выпадал из алфавита. Обычные пары разделяются последовательностью " -> ", терминальные пары последовательностью " |-> "

К сообщению приложен файл (nam.zip - 2Kb) cкачать
29 май 20, 07:10    [22141958]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
Swa111
Member

Откуда:
Сообщений: 202
В интерпретатор добавлена проверка перекрытия правил

К сообщению приложен файл (nam.zip - 2Kb) cкачать
29 май 20, 07:49    [22141963]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
crutchmaster
Member

Откуда: оттуда.
Сообщений: 1543
mayton,
Зачем нужно terminal rule я не понял.

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

Так это элементарно. Надо просто перебрать все суммы двоичных чисел в диапазоне байта в лоб.
29 май 20, 08:31    [22141971]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
crutchmaster,

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

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

Часть алгоритмов без него обходятся. Ну и ладно.
29 май 20, 08:48    [22141975]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
crutchmaster
Member

Откуда: оттуда.
Сообщений: 1543
mayton,

А, дошло. Если оно срабатывает или достигнут конец списка, то всё заканчивается.
29 май 20, 08:59    [22141976]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
Swa111, спасибо. Посмотрю.

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

https://rosettacode.org/wiki/Execute_a_Markov_algorithm

Я думаю что надо собрать 1 бинарничек на сях под Windows и выложить сюда чтоб желающие пользовались.
29 май 20, 10:04    [22141996]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
Swa111, ты гитхабом пользуешся? Ну я имею в виду.. Учетная запись там есть? Свои репозитарии?
29 май 20, 10:06    [22141999]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
Щас я расскажу свою идею. Вобщем я сложение заменил на инкремент.

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


# Наша исходная строка

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

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

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

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

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

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

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

Rules:
^$| -> ^1$

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

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

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

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


Вот. Я это написал в уме сегодня ночью. И еще не проверял. Наверное там где-то есть зацикливание.
29 май 20, 10:17    [22142007]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
crutchmaster
Member

Откуда: оттуда.
Сообщений: 1543
mayton,

Мы сперва переводим бинарь в палочки, но как палочки перевести обратно в бинарь? Первый кусок кода его будет блокировать же.
29 май 20, 10:20    [22142012]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
crutchmaster
mayton,

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


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

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

| -> *


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

Мне символов не жалко.
29 май 20, 10:23    [22142016]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
Swa111, у меня твой алгоритм не сработал на вот этом эмуляторе http://www.cmcmsu.info/1course/alg.schema.nam.htm

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

*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


В пошаговом режиме пишет Ни одно правило не применено, либо выполнено терминальное правило.
29 май 20, 10:32    [22142019]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый НАМ и сложение двоичных чисел в строках  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
mayton
Мне символов не жалко.

Хотя да. Я думаю что Марков пожадничал. Надо было ввести в язык поняти стека и вызва процедуры или функции.
Но он наверное как и все теоретики просто что-то на бумаге хотел доказать. Типа равна ли эта хрень Машинке Тьюринга.
29 май 20, 10:47    [22142039]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2 3 4 5   вперед  Ctrl      все
Все форумы / Программирование Ответить